首页 > 代码库 > 二叉树转换为双向环形链表
二叉树转换为双向环形链表
二叉树的节点与双向环形链表的节点类似,均含有两个指向不同方向的指针,因此他们之间的转化是可以实现的。下面介绍一种递归的实现方法。由于方法比较简单,就直接上代码了
二叉树的建立
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 <iostream> #include <string> #include <fstream> 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"<<endl; 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<<temp->s<<" "; temp = temp->right; } cout<<end->s<<endl; }
二叉树转换为双向环形链表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。