【转】二元查找树转为双向链表

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。  　　比如将二元查找树                                               10                                             /      /                                           6       14                                        /   /    /　 /                                      4     8  12  16  转换成双向链表 。 4=6=8=10=12=14=16。 

声明：思想不是原创。

方法一：其思想是分别转换左右子树成双向链，再通过根节点进行连接

[cpp] view plaincopy
  1. #include <iostream>  
  2. using namespace std;  
  3. struct BSTree  
  4. {  
  5.     int num;  
  6.     BSTree* left;  
  7.     BSTree* right;  
  8.       
  9. };  
  10. BSTree *convertToLink(BSTree *tree,bool asRight)  
  11. {  
  12.     BSTree *pleft=0;//节点tree的左子树转换成的双向链表  
  13.     BSTree *pright=0;//节点tree的右子树转换成的双向链表  
  14.     //如果左子树不为空，则先转换左子树  
  15.     if(tree->left)  
  16.         pleft=convertToLink(tree->left,false);  
  17.     //如果双向左链表不为空，将此节点加到末尾  
  18.     if(pleft)  
  19.     {  
  20.         pleft->right=tree;  
  21.         tree->left=pleft;  
  22.     }  
  23.     if(tree->right)  
  24.         pright=convertToLink(tree->right,true);  
  25.     if(pright)  
  26.     {  
  27.         pright->left=tree;  
  28.         tree->right=pright;  
  29.     }  
  30.     BSTree *pTemp=tree;  
  31.     //如果当前节点tree为其根节点的右子树，则返回此树的最小节点，即为父节点的右子链表的最左节点  
  32.     if(asRight)  
  33.     {  
  34.         while(pTemp->left)  
  35.             pTemp=pTemp->left;  
  36.     }  
  37.     //否则返回最大节点，相当于父节点左子链表的最右节点  
  38.     else  
  39.     {  
  40.         while(pTemp->right)  
  41.             pTemp=pTemp->right;  
  42.     }  
  43.     return pTemp;  
  44. }  
  45. void main()  
  46. {  
  47.     BSTree *root;  
  48.     BSTree *p4 = new BSTree();  
  49.     p4->num=4;  
  50.     BSTree *p8 = new BSTree();  
  51.     p8->num=8;  
  52.       
  53.     BSTree *p6 = new BSTree();  
  54.     p6->num=6;  
  55.     p6->left=p4;  
  56.     p6->right=p8;  
  57.     BSTree *p12 = new BSTree();  
  58.     p12->num=12;  
  59.       
  60.     BSTree *p14 = new BSTree();  
  61.     p14->num=14;  
  62.     p14->left=p12;  
  63.     BSTree *p10 = new BSTree();  
  64.     p10->num=10;  
  65.     p10->left=p6;  
  66.     p10->right=p14;  
  67.     root = p10;  
  68.     root=convertToLink(root,true);  
  69.     cout<<root->num<<"=";  
  70.     while(root->right){  
  71.         root=root->right;  
  72.         cout<<root->num<<"=";  
  73.     }  
  74.     cin.get();  
  75. }  

方法二：更容易理解，中序遍历树，那依次访问的节点本身就是有序的，将节点依次加入到链表末尾即可

[cpp] view plaincopy
  1. #include <iostream>  
  2. using namespace std;  
  3. struct BSTree  
  4. {  
  5.     int num;  
  6.     BSTree* left;  
  7.     BSTree* right;  
  8.       
  9. };  
  10. /** 
  11. 中序遍历二元查找树，将节点依次加入到双向链表末尾 
  12. **/  
  13. void convertToLink2(BSTree *tree,BSTree *&lastNodeInList)  
  14. {  
  15.     if(tree->left)  
  16.         convertToLink2(tree->left,lastNodeInList);  
  17.       
  18.     if(lastNodeInList)  
  19.     {  
  20.         lastNodeInList->right=tree;  
  21.         tree->left=lastNodeInList;  
  22.         lastNodeInList=tree;  
  23.     }  
  24.     else  
  25.     {  
  26.         lastNodeInList=tree;  
  27.     }  
  28.     if(tree->right)  
  29.         convertToLink2(tree->right,lastNodeInList);  
  30. }  
  31. void main()  
  32. {  
  33.     BSTree *root;  
  34.     BSTree *p4 = new BSTree();  
  35.     p4->num=4;  
  36.   
  37.     BSTree *p8 = new BSTree();  
  38.     p8->num=8;  
  39.       
  40.     BSTree *p6 = new BSTree();  
  41.     p6->num=6;  
  42.     p6->left=p4;  
  43.     p6->right=p8;  
  44.     BSTree *p12 = new BSTree();  
  45.     p12->num=12;  
  46.   
  47.       
  48.     BSTree *p14 = new BSTree();  
  49.     p14->num=14;  
  50.     p14->left=p12;  
  51.   
  52.     BSTree *p10 = new BSTree();  
  53.     p10->num=10;  
  54.     p10->left=p6;  
  55.     p10->right=p14;  
  56.     root = p10;  
  57.     //root=convertToLink(root,true);  
  58.     //cout<<root->num<<"=";  
  59.     //while(root->right){  
  60.     //  root=root->right;  
  61.     //  cout<<root->num<<"=";  
  62.     //}  
  63.     BSTree *doubleLink=NULL;  
  64.     convertToLink2(root,doubleLink);  
  65.     while(doubleLink->left)  
  66.         doubleLink=doubleLink->left;  
  67.     cout<<doubleLink->num;  
  68.     while(doubleLink->right)  
  69.     {  
  70.         doubleLink=doubleLink->right;  
  71.         cout<<"="<<doubleLink->num;  
  72.     }  
  73.     cin.get();  
  74. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/muxiaoruo/p/3341654.html