二叉树的节点与双向环形链表的节点类似，均含有两个指向不同方向的指针，因此他们之间的转化是可以实现的。下面介绍一种递归的实现方法。由于方法比较简单，就直接上代码了

二叉树的建立

node* create(const string& s)
{
?node* res = new node;
?res->left = nullptr;
?res->right = nullptr;
?res->s = s;
?return res;
}
node* insert(node* root, const string& s)
{
?if(root == nullptr)
?{
? root = create(s);
? return root;
?}
?node* temp = root;
?while(temp!=nullptr)
?{
? if(temp->s > s)
? {
? ?if(temp->left == nullptr)
? ?{
? ? temp->left = create(s);
? ? return root;
? ?}
? ?else
? ? temp = temp->left;
? }
? else
? {
? ?if(temp->right == nullptr)
? ?{
? ? temp->right = create(s);
? ? return root;
? ?}
? ?temp = temp->right;
? }
?}
}

二叉树转换为链表

node* join_two_cycle(node* first, node* second)
{
?if(first == nullptr)
? return second;
?if(second == nullptr)
? return first;
?node* rail_first = first->left;
?node* rail_second = second->left;
?rail_first->right = second;
?second->left = rail_first;
?rail_second->right = first;
?first->left = rail_second;
?return first;
}
node* merge_to_list(node* x)
{
?if(x == nullptr)
? return nullptr;
?node* head_left = merge_to_list(x->left);
?node* head_right = merge_to_list(x->right);
?x->left = x;
?x->right = x;
?head_left = join_two_cycle(head_left,x);
?head_left = join_two_cycle(head_left,head_right);
?return head_left;
}

测试代码

#include
#include
#include
using namespace std;
struct node
{
?string s;
?node* left;
?node* right;
};
node* insert(node* root, const string& s);
node* merge_to_list(node* x);
void main()
{
?ifstream in("data.txt");
?if(!in.good())
?{
? cout<<"Error"<? exit(0);
?}
?node* root = nullptr;
?while(!in.eof())
?{
? string s;
? in>>s;
? root = insert(root,s);
?}
?node* head;
?head = merge_to_list(root);
?node* end = head->left;
?node* temp = head;
?while(temp != end)
?{
? cout<s<<" ";
? temp = temp->right;
?}
?cout<s<}