數(shù)據(jù)結(jié)構(gòu)中二叉樹各種題型詳解及程序(共14頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上樹是一種比較重要的數(shù)據(jù)結(jié)構(gòu)，尤其是二叉樹。二叉樹是一種特殊的樹，在二叉樹中每個節(jié)點最多有兩個子節(jié)點，一般稱為左子節(jié)點和右子節(jié)點（或左孩子和右孩子），并且二叉樹的子樹有左右之分，其次序不能任意顛倒。二叉樹是遞歸定義的，因此，與二叉樹有關(guān)的題目基本都可以用遞歸思想解決，當然有些題目非遞歸解法也應(yīng)該掌握，如非遞歸遍歷節(jié)點等等。本文努力對二叉樹相關(guān)題目做一個較全的整理總結(jié)，希望對找工作的同學(xué)有所幫助。二叉樹節(jié)點定義如下：struct BinaryTreeNode    int m_nValue;    BinaryTreeNode* m

2、_pLeft;    BinaryTreeNode* m_pRight;相關(guān)鏈接：題目列表：詳細解答1. 求二叉樹中的節(jié)點個數(shù)遞歸解法：（1）如果二叉樹為空，節(jié)點個數(shù)為0（2）如果二叉樹不為空，二叉樹節(jié)點個數(shù) = 左子樹節(jié)點個數(shù) + 右子樹節(jié)點個數(shù) + 1參考代碼如下：1. int GetNodeNum(BinaryTreeNode * pRoot)  2.   3.     if(pRoot = NULL) / 遞歸出口&#

3、160; 4.         return 0;  5.     return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;  6.   2. 求二叉樹的深度遞歸解法：（1）如果二叉樹為空，二叉樹的深度為0（2）如果二叉樹不為空，二叉樹的深度 = max(左

4、子樹深度， 右子樹深度) + 1參考代碼如下：1. int GetDepth(BinaryTreeNode * pRoot)  2.   3.     if(pRoot = NULL) / 遞歸出口  4.         return 0;  5.     int d

5、epthLeft = GetDepth(pRoot->m_pLeft);  6.     int depthRight = GetDepth(pRoot->m_pRight);  7.     return depthLeft > depthRight ? (depthLeft + 1) : (depthRight

6、60;+ 1);   8.   3. 前序遍歷，中序遍歷，后序遍歷前序遍歷遞歸解法：（1）如果二叉樹為空，空操作（2）如果二叉樹不為空，訪問根節(jié)點，前序遍歷左子樹，前序遍歷右子樹參考代碼如下：1. void PreOrderTraverse(BinaryTreeNode * pRoot)  2.   3.     if(pRoot = NULL)  4.   

7、0;     return;  5.     Visit(pRoot); / 訪問根節(jié)點  6.     PreOrderTraverse(pRoot->m_pLeft); / 前序遍歷左子樹  7.     PreOrderTraverse(pRoot->m_pRight); / 前序遍歷右子樹

8、  8.   中序遍歷遞歸解法（1）如果二叉樹為空，空操作。（2）如果二叉樹不為空，中序遍歷左子樹，訪問根節(jié)點，中序遍歷右子樹參考代碼如下：1. void InOrderTraverse(BinaryTreeNode * pRoot)  2.   3.     if(pRoot = NULL)  4.         retur

9、n;  5.     InOrderTraverse(pRoot->m_pLeft); / 中序遍歷左子樹  6.     Visit(pRoot); / 訪問根節(jié)點  7.     InOrderTraverse(pRoot->m_pRight); / 中序遍歷右子樹  8.   后序遍歷遞歸解法（1）如

10、果二叉樹為空，空操作（2）如果二叉樹不為空，后序遍歷左子樹，后序遍歷右子樹，訪問根節(jié)點參考代碼如下：1. void PostOrderTraverse(BinaryTreeNode * pRoot)  2.   3.     if(pRoot = NULL)  4.         return;  5.    

11、60;PostOrderTraverse(pRoot->m_pLeft); / 后序遍歷左子樹  6.     PostOrderTraverse(pRoot->m_pRight); / 后序遍歷右子樹  7.     Visit(pRoot); / 訪問根節(jié)點  8.   4.分層遍歷二叉樹（按層次從上往下，從左往右）相當于廣度優(yōu)先搜索，使用隊列實現(xiàn)。隊列初始化，

12、將根節(jié)點壓入隊列。當隊列不為空，進行如下操作：彈出一個節(jié)點，訪問，若左子節(jié)點或右子節(jié)點不為空，將其壓入隊列。1. void LevelTraverse(BinaryTreeNode * pRoot)  2.   3.     if(pRoot = NULL)  4.         return;  5.    

13、60;queue<BinaryTreeNode *> q;  6.     q.push(pRoot);  7.     while(!q.empty()  8.       9.         BinaryTreeNode * pNode = 

14、q.front();  10.         q.pop();  11.         Visit(pNode); / 訪問節(jié)點  12.         if(pNode->m_pLeft != NULL)  13.  

15、;           q.push(pNode->m_pLeft);  14.         if(pNode->m_pRight != NULL)  15.             q.push(pNode-&g

16、t;m_pRight);  16.       17.     return;  18.   5. 將二叉查找樹變?yōu)橛行虻碾p向鏈表要求不能創(chuàng)建新節(jié)點，只調(diào)整指針。例如如下的二叉搜索樹，若采用中序遍歷，其遍歷順序為1-2-3-4-5-6-7，通過適當?shù)闹羔樧儞Q操作，可變成的雙向有序鏈表如下：遞歸解法：（1）如果二叉樹查找樹為空，不需要轉(zhuǎn)換，對應(yīng)雙向鏈表的第一個節(jié)點是NULL，最后一個節(jié)點是NULL（2）如果二叉查找樹不為空：如果左子樹為空

17、，對應(yīng)雙向有序鏈表的第一個節(jié)點是根節(jié)點，左邊不需要其他操作；如果左子樹不為空，轉(zhuǎn)換左子樹，二叉查找樹對應(yīng)雙向有序鏈表的第一個節(jié)點就是左子樹轉(zhuǎn)換后雙向有序鏈表的第一個節(jié)點，同時將根節(jié)點和左子樹轉(zhuǎn)換后的雙向有序鏈表的最后一個節(jié)點連接；如果右子樹為空，對應(yīng)雙向有序鏈表的最后一個節(jié)點是根節(jié)點，右邊不需要其他操作；如果右子樹不為空，對應(yīng)雙向有序鏈表的最后一個節(jié)點就是右子樹轉(zhuǎn)換后雙向有序鏈表的最后一個節(jié)點，同時將根節(jié)點和右子樹轉(zhuǎn)換后的雙向有序鏈表的第一個節(jié)點連接。參考代碼如下：1. /* 2. 參數(shù)： 3. pRoot: 二叉查找樹根節(jié)點指針 4. pFirstNo

18、de: 轉(zhuǎn)換后雙向有序鏈表的第一個節(jié)點指針 5. pLastNode: 轉(zhuǎn)換后雙向有序鏈表的最后一個節(jié)點指針 6. */  7. void Convert(BinaryTreeNode * pRoot,   8.              BinaryTreeNode * & pFirstNode, 

19、BinaryTreeNode * & pLastNode)  9.   10.     BinaryTreeNode *pFirstLeft, *pLastLeft, * pFirstRight, *pLastRight;  11.     if(pRoot = NULL)   12.    

20、;   13.         pFirstNode = NULL;  14.         pLastNode = NULL;  15.         return;  16.     

21、;  17.   18.     if(pRoot->m_pLeft = NULL)  19.       20.         / 如果左子樹為空，對應(yīng)雙向有序鏈表的第一個節(jié)點是根節(jié)點  21.         pFir

22、stNode = pRoot;  22.       23.     else  24.       25.         Convert(pRoot->m_pLeft, pFirstLeft, pLastLeft);  26.   

23、;      / 二叉查找樹對應(yīng)雙向有序鏈表的第一個節(jié)點就是左子樹轉(zhuǎn)換后雙向有序鏈表的第一個節(jié)點  27.         pFirstNode = pFirstLeft;  28.         / 將根節(jié)點和左子樹轉(zhuǎn)換后的雙向有序鏈表的最后一個節(jié)點連接  29.  

24、;       pRoot->m_pLeft = pLastLeft;  30.         pLastLeft->m_pRight = pRoot;  31.       32.   33.     if(pRoot->m_p

25、Right = NULL)  34.       35.         / 對應(yīng)雙向有序鏈表的最后一個節(jié)點是根節(jié)點  36.         pLastNode = pRoot;  37.       38.

26、     else  39.       40.         Convert(pRoot->m_pRight, pFirstRight, pLastRight);  41.         / 對應(yīng)雙向有序鏈表的最后一個節(jié)點就是右子樹轉(zhuǎn)換后雙向有序鏈表的最后一

27、個節(jié)點  42.         pLastNode = pLastRight;  43.         / 將根節(jié)點和右子樹轉(zhuǎn)換后的雙向有序鏈表的第一個節(jié)點連接  44.         pRoot->m_pRight = pFirstRi

28、ght;  45.         pFirstRight->m_pLeft= pRoot;  46.       47.   48.     return;  49.   6. 求二叉樹第K層的節(jié)點個數(shù)遞歸解法：（1）如果二叉樹為空或者k<1返回0（2）如果二叉樹不為空并且k=1，返回1（3）如

29、果二叉樹不為空且k>1，返回左子樹中k-1層的節(jié)點個數(shù)與右子樹k-1層節(jié)點個數(shù)之和參考代碼如下：1. int GetNodeNumKthLevel(BinaryTreeNode * pRoot, int k)  2.   3.     if(pRoot = NULL | k < 1)  4.        

30、 return 0;  5.     if(k = 1)  6.         return 1;  7.     int numLeft = GetNodeNumKthLevel(pRoot->m_pLeft, k-1); / 左子樹中k-1層的節(jié)點個數(shù)

31、60; 8.     int numRight = GetNodeNumKthLevel(pRoot->m_pRight, k-1); / 右子樹中k-1層的節(jié)點個數(shù)  9.     return (numLeft + numRight);  10.   7. 求二叉樹中葉子節(jié)點的個數(shù)遞歸解法：（1）如果二叉樹為空，返回0（2）如果二叉樹不為空且左右子

32、樹為空，返回1（3）如果二叉樹不為空，且左右子樹不同時為空，返回左子樹中葉子節(jié)點個數(shù)加上右子樹中葉子節(jié)點個數(shù)參考代碼如下：1. int GetLeafNodeNum(BinaryTreeNode * pRoot)  2.   3.     if(pRoot = NULL)  4.         return 0;  5.  &

33、#160;  if(pRoot->m_pLeft = NULL && pRoot->m_pRight = NULL)  6.         return 1;  7.     int numLeft = GetLeafNodeNum(pRoot->m_pLeft); /&#

34、160;左子樹中葉節(jié)點的個數(shù)  8.     int numRight = GetLeafNodeNum(pRoot->m_pRight); / 右子樹中葉節(jié)點的個數(shù)  9.     return (numLeft + numRight);  10.   8. 判斷兩棵二叉樹是否結(jié)構(gòu)相同不考慮數(shù)據(jù)內(nèi)容。結(jié)構(gòu)相同意味著對應(yīng)的左子樹和對應(yīng)的右子樹都結(jié)構(gòu)相同

35、。遞歸解法：（1）如果兩棵二叉樹都為空，返回真（2）如果兩棵二叉樹一棵為空，另一棵不為空，返回假（3）如果兩棵二叉樹都不為空，如果對應(yīng)的左子樹和右子樹都同構(gòu)返回真，其他返回假參考代碼如下：1. bool StructureCmp(BinaryTreeNode * pRoot1, BinaryTreeNode * pRoot2)  2.   3.     if(pRoot1 = NULL && pRoo

36、t2 = NULL) / 都為空，返回真  4.         return true;  5.     else if(pRoot1 = NULL | pRoot2 = NULL) / 有一個為空，一個不為空，返回假  6.     &

37、#160;   return false;  7.     bool resultLeft = StructureCmp(pRoot1->m_pLeft, pRoot2->m_pLeft); / 比較對應(yīng)左子樹   8.     bool resultRight = StructureCmp(pRoot1->m_pRig

38、ht, pRoot2->m_pRight); / 比較對應(yīng)右子樹  9.     return (resultLeft && resultRight);  10.    9. 判斷二叉樹是不是平衡二叉樹遞歸解法：（1）如果二叉樹為空，返回真（2）如果二叉樹不為空，如果左子樹和右子樹都是AVL樹并且左子樹和右子樹高度相差不大于1，返回真，其他返回假參考代碼：1. bool IsAVL(Binary

39、TreeNode * pRoot, int & height)  2.   3.     if(pRoot = NULL) / 空樹，返回真  4.       5.         height = 0;  6.

40、60;       return true;  7.       8.     int heightLeft;  9.     bool resultLeft = IsAVL(pRoot->m_pLeft, heightLeft);  10.  

41、0;  int heightRight;  11.     bool resultRight = IsAVL(pRoot->m_pRight, heightRight);  12.     if(resultLeft && resultRight && abs(heightLeft - heightRight)

42、 <= 1) / 左子樹和右子樹都是AVL，并且高度相差不大于1，返回真  13.       14.         height = max(heightLeft, heightRight) + 1;  15.         return

43、 true;  16.       17.     else  18.       19.         height = max(heightLeft, heightRight) + 1;  20.    

44、     return false;  21.       22.   10. 求二叉樹的鏡像遞歸解法：（1）如果二叉樹為空，返回空（2）如果二叉樹不為空，求左子樹和右子樹的鏡像，然后交換左子樹和右子樹參考代碼如下：1. BinaryTreeNode * Mirror(BinaryTreeNode * pRoot)  2.   3.   

45、  if(pRoot = NULL) / 返回NULL  4.         return NULL;  5.     BinaryTreeNode * pLeft = Mirror(pRoot->m_pLeft); / 求左子樹鏡像  6.    &

46、#160;BinaryTreeNode * pRight = Mirror(pRoot->m_pRight); / 求右子樹鏡像  7.         / 交換左子樹和右子樹  8.     pRoot->m_pLeft = pRight;  9.     pRoot->

47、;m_pRight = pLeft;  10.     return pRoot;  11.   11. 求二叉樹中兩個節(jié)點的最低公共祖先節(jié)點參考代碼如下：1. bool FindNode(BinaryTreeNode * pRoot, BinaryTreeNode * pNode)  2.   3.     if(pRoot&

48、#160;= NULL | pNode = NULL)  4.         return false;  5.   6.     if(pRoot = pNode)  7.         return true; 

49、 8.   9.     bool found = FindNode(pRoot->m_pLeft, pNode);  10.     if(!found)  11.         found = FindNode(pRoot->m_pRight, pNode);  

50、;12.   13.     return found;  14.   15.   16. BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot,   17.               

51、60;                      BinaryTreeNode * pNode1,   18.                   &

52、#160;                  BinaryTreeNode * pNode2)  19.   20.     if(FindNode(pRoot->m_pLeft, pNode1)  21.       22

53、.         if(FindNode(pRoot->m_pRight, pNode2)  23.             return pRoot;  24.         else  25.   

54、0;         return GetLastCommonParent(pRoot->m_pLeft, pNode1, pNode2);  26.       27.     else  28.       29.     

55、60;   if(FindNode(pRoot->m_pLeft, pNode2)  30.             return pRoot;  31.         else  32.        

56、0;    return GetLastCommonParent(pRoot->m_pRight, pNode1, pNode2);  33.       34.   遞歸解法效率很低，有很多重復(fù)的遍歷，下面看一下非遞歸解法。非遞歸解法：先求從根節(jié)點到兩個節(jié)點的路徑，然后再比較對應(yīng)路徑的節(jié)點就行，最后一個相同的節(jié)點也就是他們在二叉樹中的最低公共祖先節(jié)點參考代碼如下：1. bool GetNodePath(Bin

57、aryTreeNode * pRoot, BinaryTreeNode * pNode,   2.                  list<BinaryTreeNode *> & path)  3.   4.     

58、;if(pRoot = pNode)  5.         return true;  6.     if(pRoot = NULL)  7.         return false;  8.     path.pu

59、sh_back(pRoot);  9.     bool found = false;  10.     found = GetNodePath(pRoot->m_pLeft, pNode, path);  11.     if(!found)  12.      

60、0;  found = GetNodePath(pRoot->m_pRight, pNode, path);  13.     if(!found)  14.         path.pop_back();  15.     return found;  16.  

61、60;17. BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot,   18.                                 

62、;     BinaryTreeNode * pNode1,   19.                                    

63、60; BinaryTreeNode * pNode2)  20.   21.     if(pRoot = NULL | pNode1 = NULL | pNode2 = NULL)  22.         return NULL;  23.  

64、 24.     list<BinaryTreeNode*> path1;  25.     GetNodePath(pRoot, pNode1, path1);  26.     list<BinaryTreeNode*> path2;  27.     GetNodePath(pRoot, 

65、pNode2, path2);  28.   29.     BinaryTreeNode * pLast = NULL;  30.     list<BinaryTreeNode*>:const_iterator iter1 = path1.begin();  31.     list<Binary

66、TreeNode*>:const_iterator iter2 = path2.begin();  32.     while(iter1 != path1.end() && iter2 != path2.end()  33.       34.         if

67、(*iter1 = *iter2)  35.             pLast = *iter1;  36.         else  37.             brea

68、k;  38.         iter1+;  39.         iter2+;  40.       41.   42.     return pLast;  43.   在上述算法的基礎(chǔ)上稍加變化即

69、可求二叉樹中任意兩個節(jié)點的距離了。12. 求二叉樹中節(jié)點的最大距離即二叉樹中相距最遠的兩個節(jié)點之間的距離。遞歸解法：（1）如果二叉樹為空，返回0，同時記錄左子樹和右子樹的深度，都為0（2）如果二叉樹不為空，最大距離要么是左子樹中的最大距離，要么是右子樹中的最大距離，要么是左子樹節(jié)點中到根節(jié)點的最大距離+右子樹節(jié)點中到根節(jié)點的最大距離，同時記錄左子樹和右子樹節(jié)點中到根節(jié)點的最大距離。參考代碼如下：1. int GetMaxDistance(BinaryTreeNode * pRoot, int & maxLeft, i

70、nt & maxRight)  2.   3.     / maxLeft, 左子樹中的節(jié)點距離根節(jié)點的最遠距離  4.     / maxRight, 右子樹中的節(jié)點距離根節(jié)點的最遠距離  5.     if(pRoot = NULL)  6.    

71、0;  7.         maxLeft = 0;  8.         maxRight = 0;  9.         return 0;  10.      

72、0;11.     int maxLL, maxLR, maxRL, maxRR;  12.     int maxDistLeft, maxDistRight;  13.     if(pRoot->m_pLeft != NULL)  14.       15. 

73、0;       maxDistLeft = GetMaxDistance(pRoot->m_pLeft, maxLL, maxLR);  16.         maxLeft = max(maxLL, maxLR) + 1;  17.       1

74、8.     else  19.       20.         maxDistLeft = 0;  21.         maxLeft = 0;  22.       2

75、3.     if(pRoot->m_pRight != NULL)  24.       25.         maxDistRight = GetMaxDistance(pRoot->m_pRight, maxRL, maxRR);  26.      

76、;   maxRight = max(maxRL, maxRR) + 1;  27.       28.     else  29.       30.         maxDistRight = 0; &#

77、160;31.         maxRight = 0;  32.       33.     return max(max(maxDistLeft, maxDistRight), maxLeft+maxRight);  34.   13. 由前序遍歷序列和中序遍歷序列重建二叉樹二叉樹前序遍歷序列中，第一個

78、元素總是樹的根節(jié)點的值。中序遍歷序列中，左子樹的節(jié)點的值位于根節(jié)點的值的左邊，右子樹的節(jié)點的值位于根節(jié)點的值的右邊。遞歸解法：（1）如果前序遍歷為空或中序遍歷為空或節(jié)點個數(shù)小于等于0，返回NULL。（2）創(chuàng)建根節(jié)點。前序遍歷的第一個數(shù)據(jù)就是根節(jié)點的數(shù)據(jù)，在中序遍歷中找到根節(jié)點的位置，可分別得知左子樹和右子樹的前序和中序遍歷序列，重建左右子樹。1. BinaryTreeNode * RebuildBinaryTree(int* pPreOrder, int* pInOrder, int nodeNum)  

79、2.   3.     if(pPreOrder = NULL | pInOrder = NULL | nodeNum <= 0)  4.         return NULL;  5.     BinaryTreeNode * pRoot&

80、#160;= new BinaryTreeNode;  6.     / 前序遍歷的第一個數(shù)據(jù)就是根節(jié)點數(shù)據(jù)  7.     pRoot->m_nValue = pPreOrder0;  8.     pRoot->m_pLeft = NULL;  9.     pRoot-&

81、gt;m_pRight = NULL;  10.     / 查找根節(jié)點在中序遍歷中的位置，中序遍歷中，根節(jié)點左邊為左子樹，右邊為右子樹  11.     int rootPositionInOrder = -1;  12.     for(int i = 0; i < nodeNum;

82、60;i+)  13.         if(pInOrderi = pRoot->m_nValue)  14.           15.             rootPositionInOrder = i;

83、  16.             break;  17.           18.     if(rootPositionInOrder = -1)  19.       20.  &#

84、160;      throw std:exception("Invalid input.");  21.       22.     / 重建左子樹  23.     int nodeNumLeft = rootPositionInOrder;  24. &

85、#160;   int * pPreOrderLeft = pPreOrder + 1;  25.     int * pInOrderLeft = pInOrder;  26.     pRoot->m_pLeft = RebuildBinaryTree(pPreOrderLeft, pInOrderLeft,

86、 nodeNumLeft);  27.     / 重建右子樹  28.     int nodeNumRight = nodeNum - nodeNumLeft - 1;  29.     int * pPreOrderRight = pPreOrder + 1

87、60;+ nodeNumLeft;  30.     int * pInOrderRight = pInOrder + nodeNumLeft + 1;  31.     pRoot->m_pRight = RebuildBinaryTree(pPreOrderRight, pInOrderRight, nodeNumRight); 

88、; 32.     return pRoot;  33.   同樣，有中序遍歷序列和后序遍歷序列，類似的方法可重建二叉樹，但前序遍歷序列和后序遍歷序列不同恢復(fù)一棵二叉樹，證明略。14.判斷二叉樹是不是完全二叉樹若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1h-1) 的結(jié)點數(shù)都達到最大個數(shù)，第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹。有如下算法，按層次（從上到下，從左到右）遍歷二叉樹，當遇到一個節(jié)點的左子樹為空時，則該節(jié)點右子樹必須為空，且后面遍歷的節(jié)點左右子樹都必須為空，否則

89、不是完全二叉樹。1. bool IsCompleteBinaryTree(BinaryTreeNode * pRoot)  2.   3.     if(pRoot = NULL)  4.         return false;  5.     queue<BinaryTreeNode&#

90、160;*> q;  6.     q.push(pRoot);  7.     bool mustHaveNoChild = false;  8.     bool result = true;  9.     while(!q.empty()  10.       11.         BinaryTreeNode * pNode = q.front();  12.         q.pop();  13.         if(mustHave