題目:輸入一顆二叉搜索樹，將該二叉搜索樹轉換為一個排序的雙向鏈表。要求不能創建

任何新的結點，只能調整樹種結點指針的指向。比如輸入下圖的二叉搜索樹，則輸出轉換

后的雙向排序鏈表。

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 }

運行截圖:

?

轉載于:https://www.cnblogs.com/vpoet/p/4770868.html

總結

以上是生活随笔為你收集整理的面试题27.二叉搜索树与双向链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。