转载

面试题27.二叉搜索树与双向链表

题目:输入一颗二叉搜索树，将该二叉搜索树转换为一个排序的双向链表。要求不能创建

任何新的结点，只能调整树种结点指针的指向。比如输入下图的二叉搜索树，则输出转换

后的双向排序链表。

1             10 2           /    / 3         6      14 4        /  /    /  / 5       4   8   12  16

转换后的双向排序链表为:

1 4<--->6<--->8<--->10<--->12<--->14<--->16

首先要明白二叉搜索树是根结点大于左子结点，小于右子结点

然而要让转换后的双向链表基本有序,则应该中序遍历该二叉树

遍历的时候将树看成三部分:值为10的根结点，根结点值为6的左

子树，根结点值为14的右子树。根据排序链表的定义。值为10的

结点将和左子树的最大的结点链接起来，同时该结点还要和右子树

最小的结点链接起来。

然而对于左子树和右子树，递归上述步骤即可。

代码实现如下:

  1 #include <iostream>   2 using namespace std;   3    4 struct BinaryTreeNode   5 {   6     int        m_nValue;   7     BinaryTreeNode* m_pLeft;   8     BinaryTreeNode* m_pRight;   9 };  10   11 void ConvertNode(BinaryTreeNode* pNode,BinaryTreeNode** pLastNodeInlist)  12 {  13     if(pNode==NULL)  14         return;  15   16     BinaryTreeNode *pCurrent = pNode;  17   18     if(pCurrent->m_pLeft!=NULL)  19         ConvertNode(pCurrent->m_pLeft,pLastNodeInlist);  20   21     pCurrent->m_pLeft=*pLastNodeInlist;  22   23     if(*pLastNodeInlist!=NULL)  24         (*pLastNodeInlist)->m_pRight=pCurrent;  25   26     *pLastNodeInlist=pCurrent;  27   28     if(pCurrent->m_pRight!=NULL)  29         ConvertNode(pCurrent->m_pRight,pLastNodeInlist);  30 }  31   32   33   34 BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)  35 {  36     BinaryTreeNode *pLastNodeInList = NULL;  37     ConvertNode(pRootOfTree,&pLastNodeInList);  38   39     BinaryTreeNode *pHeadOfList = pLastNodeInList;  40     while(pHeadOfList != NULL&&pHeadOfList->m_pLeft!=NULL)  41         pHeadOfList = pHeadOfList->m_pLeft;  42   43     return pHeadOfList;  44 }  45   46 void CreateTree(BinaryTreeNode** Root)  47 {  48      int data;  49      cin>>data;  50      if(data==0)  51      {  52         *Root=NULL;  53          return ;  54      }  55      else  56      {  57          *Root=(BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));  58          (*Root)->m_nValue=data;  59          CreateTree(&((*Root)->m_pLeft));      60          CreateTree(&((*Root)->m_pRight));  61      }  62 }  63   64 void PrintTreeInOrder(BinaryTreeNode* Root)  65 {  66     if(Root==NULL)  67     {  68         return;  69     }  70     cout<<Root->m_nValue<<" ";  71     PrintTreeInOrder(Root->m_pLeft);  72     PrintTreeInOrder(Root->m_pRight);  73   74 }  75   76 void PrintTheLinkList(BinaryTreeNode *Head)  77 {  78     cout<<"从前往后变量该双向链表: ";  79     while(Head->m_pRight!=NULL)  80     {  81         cout<<Head->m_nValue<<" ";  82         Head=Head->m_pRight;  83     }  84     cout<<Head->m_nValue<<" ";  85     cout<<endl;  86     BinaryTreeNode *Last=Head;  87     cout<<"从后往前变量该双向链表: ";  88     while(Last!=NULL)  89     {  90         cout<<Last->m_nValue<<" ";  91         Last=Last->m_pLeft;  92     }  93 }  94   95 int main()  96 {  97     BinaryTreeNode* Root;  98     CreateTree(&Root);  99     cout<<"The InOrderOfTree: "; 100     PrintTreeInOrder(Root); 101     cout<<endl; 102     BinaryTreeNode* HeadOfLinkList; 103     HeadOfLinkList=Convert(Root); 104     cout<<endl; 105     PrintTheLinkList(HeadOfLinkList); 106     cout<<endl; 107     system("pause"); 108     return 0; 109 }