首页 > 代码库 > 二叉搜索树变成有序双向链表，要求不能创建新的结点，只调整指针的指向
二叉搜索树变成有序双向链表，要求不能创建新的结点，只调整指针的指向
二叉搜索树的结点有2个指针，分别指向左右孩子，双链表的每个结点也有2个指针，分别指向前后结点，所以在不创建新结点，只调整指针指向时可以将二叉搜索树变成双向链表；又由于二叉搜索树在中序遍历时是有序的，所以可以采用中序处理二叉搜索树调整指针指向将其变成有序双向链表。为了简化指针移动操作，我们让左孩子为前向指针，右孩子为后向指针。
二叉搜索树的最左结点即使整个树中最小的结点，所以首先找到最左结点，它就是链表的首结点，链表最后一个结点初始化为空。中序遍历时，当前结点的左孩子指向链表的最后一个结点，若最后一个结点不为空，则最后结点的右孩子指向当前结点，当前结点作为最后一个结点。递归的在所有子树中进行。
#include<iostream>using namespace std;class tree_node{public: class tree_node* left,*right; int data; tree_node(int d,tree_node *l=NULL,tree_node *r=NULL) { data=http://www.mamicode.com/d;" "; PrintBSTree(tree->right); }tree_node * findLeft(tree_node *root ){ if(root==NULL) return NULL; while (root->left!=NULL) { root=root->left; } return root;}void convertNode(tree_node *root,tree_node** lastnode){ if(root==NULL) return; if(root->left!=NULL) convertNode(root->left,lastnode); root->left=*lastnode; if(*lastnode!=NULL) (*lastnode)->right=root; *lastnode=root; if(root->right!=NULL) convertNode(root->right,lastnode);}tree_node * treeTolist(tree_node *root,tree_node *head,tree_node *lastnode){ if(root==NULL) return NULL; head=findLeft(root); lastnode=NULL; convertNode(root,&lastnode); return head;}void PrintDList(tree_node *h){ tree_node* curr=h; while(curr!=NULL) { cout<<curr->data<<" "; curr=curr->right; }}int main(){ tree_node* root=NULL; tree_node* DList,*head=NULL,*tail=NULL; for(int i=0;i<10;i++) { int d=rand()%100; root=insert_node(root,d); } cout<<"二叉搜索树："<<endl; PrintBSTree(root); head=treeTolist(root,head,tail); cout<<endl<<"有序双向链表"<<endl; PrintDList(head); return 0;}
二叉搜索树变成有序双向链表，要求不能创建新的结点，只调整指针的指向
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。