這幾天開學(xué)础嫡，學(xué)校還在上課氛谜，最近也是在找工作掏觉，很多天都沒有更新文章，現(xiàn)在補(bǔ)一篇二叉樹的文章值漫。
最近校招公司的筆試陸續(xù)開始澳腹，感覺算法系列的文章還更新不完就結(jié)束了，我盡量快的更新吧杨何，自己復(fù)習(xí)的同時(shí)希望能幫助讀者復(fù)習(xí)~
到了樹這一節(jié)酱塔，二叉樹較為典型。和鏈表相比危虱，樹的指針操作更復(fù)雜羊娃，而二叉樹作為一種常用的數(shù)據(jù)結(jié)構(gòu)，是要重點(diǎn)掌握的埃跷。二叉樹的遍歷是比較基礎(chǔ)的操作蕊玷，要熟悉前序遍歷邮利，中序遍歷和后序遍歷幾種遍歷方式，二叉樹的很多題目都會(huì)涉及到二叉樹的遍歷垃帅，下面是二叉樹系列第一節(jié)的題目總結(jié)延届。
- 二叉搜索樹的后序遍歷序列
- 重建二叉樹
- 二叉樹的子結(jié)構(gòu)
1.二叉搜索樹的后序遍歷序列
問題描述：輸入一個(gè)整數(shù)數(shù)組，判斷它是不是一個(gè)二叉搜索樹的后序遍歷序列贸诚，如果是則返回true方庭，否則返回false。假設(shè)輸入數(shù)組的任意2個(gè)數(shù)字互不相等酱固。
算法思想
先回顧二叉搜索樹的概念械念。
二叉搜索樹： 二叉搜索樹能保證左子樹一定小于根節(jié)點(diǎn)，右子樹一定大于根節(jié)點(diǎn)媒怯。在后序遍歷的得到的數(shù)組中订讼，最后一個(gè)數(shù)是根節(jié)點(diǎn)，數(shù)組可以分為2部分扇苞，第一部分是根節(jié)點(diǎn)的左子樹欺殿，它們都比根節(jié)點(diǎn)小，另一部分是根節(jié)點(diǎn)的右子樹鳖敷，它們都大于根節(jié)點(diǎn)脖苏。
看下面這個(gè)例子，輸入數(shù)組{5,7,6,9,11,10,8}定踱，對應(yīng)的二叉搜索樹如下棍潘。
我們這么來分析，后序遍歷結(jié)果的最后一個(gè)數(shù)字8肯定是二叉搜索樹的根節(jié)點(diǎn)崖媚。在這個(gè)數(shù)組中亦歉，前3個(gè)數(shù)5,7,6都小于8，它們是值為8的節(jié)點(diǎn)的左子樹畅哑，后3個(gè)數(shù)字9,11,10都大于8肴楷，是值為8的節(jié)點(diǎn)的右子樹。
接下來用同樣的方法來確定數(shù)組中每一部分對應(yīng)的子樹的結(jié)構(gòu)荠呐，這是一個(gè)遞歸的過程赛蔫。對于數(shù)組中的序列5,7,6構(gòu)成的子樹，根節(jié)點(diǎn)是6泥张，前一個(gè)結(jié)點(diǎn)5小于6呵恢，是值為6的節(jié)點(diǎn)的左子樹，后一個(gè)結(jié)點(diǎn)7是它的右子樹媚创。同樣渗钉，在序列9,11,10中，最后一個(gè)數(shù)是10钞钙，那么構(gòu)成的子樹的根節(jié)點(diǎn)也是10晌姚，9比10小粤剧，9就是值為10的節(jié)點(diǎn)的左子樹，11是它的右子樹挥唠。
錯(cuò)誤的結(jié)構(gòu)：
再考慮一個(gè)特殊的序列{7,4,6,5}抵恋，最后一個(gè)數(shù)是根節(jié)點(diǎn)，所以樹的根節(jié)點(diǎn)是5宝磨，由于第一個(gè)數(shù)是7弧关，大于5，所以這個(gè)節(jié)點(diǎn)沒有左子樹唤锉，那么7,4,6都是它的右子樹的節(jié)點(diǎn)世囊，但是我們發(fā)現(xiàn)4小于5，這違背了二叉搜索樹的定義窿祥，因此不存在 一個(gè)二叉樹株憾，它的后序遍歷的結(jié)果是7,4,6,5。
代碼
注意代碼中左子樹的判斷方法方法晒衩，我們不能確定這棵二叉排序樹是否是平衡的嗤瞎，不知道根節(jié)點(diǎn)的左子結(jié)點(diǎn)和右子結(jié)點(diǎn)具體有多少個(gè)，所以只能順序比較听系，將小于根節(jié)點(diǎn)的默認(rèn)為是它的左子樹贝奇，從第一個(gè)大于根節(jié)點(diǎn)的值開始，認(rèn)為其屬于右子樹（結(jié)合代碼一起分析）靠胜。
注：遞歸的時(shí)候有一個(gè)判斷,i > 0和i < length - 1掉瞳，這兩個(gè)if都是判斷左右子樹是否滿足要求的，如果遞歸到i = 0或者i = length-1的時(shí)候,說明已經(jīng)判斷到葉子節(jié)點(diǎn)了浪漠，不會(huì)再有子樹了陕习，這時(shí)不會(huì)再進(jìn)行下一次遞歸，而是直接返回ture.
//判斷輸入的序列是不是一個(gè)二叉排序樹的后序遍歷的序列址愿，如果是该镣，返回true,否則返回false
bool VerifySquenceOfBST(int sequence[], int length)
{
if (sequence == NULL || length <= 0)
{
fprintf(stderr, "Invalid parameter.\n");
return false;
}
int root = sequence[length - 1];//確定當(dāng)前子樹的根節(jié)點(diǎn)
//確定左子樹的結(jié)點(diǎn)
int i = 0;
for(;i < length - 1; i++)
{
if (sequence[i] > root)
break;
}
//確定右子樹的結(jié)點(diǎn)
int j = i;
for (; j < length - 1; j++)
{
if (sequence[j] < root)
return false;
}
//遞歸左子樹，判斷是否滿足左子樹節(jié)點(diǎn)都小于根節(jié)點(diǎn)
bool left = true;
if (i > 0)
left = VerifySquenceOfBST(sequence, i);
//遞歸右子樹必盖，判斷右子樹是否滿足所有節(jié)點(diǎn)都小于根節(jié)點(diǎn)
//判斷右子樹時(shí)拌牲，應(yīng)該從index=i開始俱饿，因?yàn)?~i-1是屬于左子樹歌粥，i~length-2屬于右子樹
bool right = true;
if (i < length - 1)
right = VerifySquenceOfBST(sequence+i, length-i-1);
return (left && right);
}
總結(jié)
我們都知道一顆二叉樹需要中序序列和后序序列，或者前序序列和中序序列才能唯一確定拍埠，而這里只用后序序列就能確定二叉樹失驶，是為什么呢？因?yàn)檫@里說的是二叉搜索樹枣购，對左右子樹的結(jié)點(diǎn)的大小是有要求的嬉探，可以將這個(gè)左子樹小于根結(jié)點(diǎn)擦耀，右子樹大于根結(jié)點(diǎn)作為附加要求。
同類題目：輸入一個(gè)整數(shù)序列涩堤，判斷該序列是否是某二叉樹前序遍歷的結(jié)果眷蜓。和上面的思想類似，只是在前序遍歷得
的序列中胎围，第一個(gè)數(shù)是根節(jié)點(diǎn)吁系。
2.重建二叉樹
問題描述：輸入二叉樹的前序遍歷和中序遍歷的結(jié)果，重建二叉樹白魂。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含有重復(fù)的數(shù)字汽纤，重建二叉樹，并輸出它的頭結(jié)點(diǎn)福荸。例如蕴坪，根據(jù)前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}確定二叉樹如下。
算法思想
這就是上面提到的前序遍歷和中序遍歷序列唯一確定一棵二叉樹敬锐。
在二叉樹的前序遍歷序列中背传，第一個(gè)數(shù)是根節(jié)點(diǎn)的值，我們可以在中序遍歷序列中找到這個(gè)數(shù)字滞造，然后確定根節(jié)點(diǎn)的位置续室。在中序遍歷序列中，根節(jié)點(diǎn)左邊的值是左子樹的節(jié)點(diǎn)谒养，根節(jié)點(diǎn)右邊的值是右子樹的節(jié)點(diǎn)挺狰。
以上面的例子來說，根節(jié)點(diǎn)是1买窟，在中序遍歷序列中丰泊，1前面有3個(gè)數(shù)字，說明左子樹有3個(gè)結(jié)點(diǎn)始绍。而在前序遍歷序列中瞳购，根節(jié)點(diǎn)后面的3個(gè)數(shù)就是左子節(jié)點(diǎn)，再后面的數(shù)就是右子樹的節(jié)點(diǎn)亏推。這樣我們就在前序遍歷和中序遍歷兩個(gè)序列中分別找到了左右子樹對應(yīng)的子序列学赛。接下來用遞歸分別對左子序列和右子序列構(gòu)建二叉樹。
代碼
二叉樹的定義吞杭。
//二叉樹定義
typedef struct BinaryTreeNode
{
int value;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
構(gòu)造二叉樹
//構(gòu)造二叉樹的核心代碼
BinaryTreeNode* ConstructCore(int *startPreorder, int *endPreorder, int *startInorder, int *endInorder);
BinaryTreeNode* Construct(int *preorder, int *inorder, int length)
{
if (preorder == NULL || inorder == NULL || length <= 0)
{
fprintf(stderr, "Invalid parameter.\n");
return NULL;
}
return ConstructCore(preorder, preorder + length - 1,
inorder, inorder + length - 1);
}
//重構(gòu)二叉樹的的核心代碼盏浇，遞歸實(shí)現(xiàn)
BinaryTreeNode* ConstructCore(int *startPreorder, int *endPreorder, int *startInorder, int *endInorder)
{
//前序遍歷的第一個(gè)是根節(jié)點(diǎn)的值
int rootValue = startPreorder[0];
BinaryTreeNode *root = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
root->value = rootValue;
root->m_pLeft = root->m_pRight = NULL;
//結(jié)束條件,遍歷到最后一個(gè)節(jié)點(diǎn)，此時(shí)前序遍歷和中序遍歷序列中剩下的值是一樣的
if (startPreorder == endPreorder)
{
//第二個(gè)判斷條件是避免中序遍歷序列和前序遍歷序列不匹配的情況
if (startInorder == endInorder && *startInorder == *startPreorder)
return root;
else
{
fprintf(stderr, "Invalid input.\n");
exit(1);
}
}
//在中序遍歷中找到根節(jié)點(diǎn)的值
int *rootInorder = startInorder;
while (rootInorder <= endInorder && *rootInorder != rootValue)
rootInorder++;
if (rootInorder == endInorder && *rootInorder != rootValue)
{
fprintf(stderr, "Invalid input.\n");
exit(1);
}
//計(jì)算右子樹有幾個(gè)節(jié)點(diǎn)芽狗，此時(shí)rootInorder是根節(jié)點(diǎn)
//注意這里绢掰，前序遍歷序列的第一個(gè)和中序遍歷序列的rootInorder是根節(jié)點(diǎn)，遞歸的時(shí)候要去掉根節(jié)點(diǎn)
int leftLength = rootInorder - startInorder;
int *leftPreorderEnd = startPreorder + leftLength;
if (leftLength > 0)
root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1);
//構(gòu)建右子樹
if (leftLength < endPreorder - startPreorder)
root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endInorder);
return root;
}
總結(jié)
在函數(shù)ConstructCore中，我們先在前序遍歷的序列中確定根節(jié)點(diǎn)滴劲，然后在中序遍歷的序列中找到根節(jié)點(diǎn)攻晒，這樣就能確定左右子樹的數(shù)目，在前序遍歷和中序遍歷的序列中劃分了左右子樹之后班挖，就可以遞歸的調(diào)用ConstructCore構(gòu)建每一個(gè)子樹鲁捏。注意遞歸的終止條件是，當(dāng)子樹序列中只有一個(gè)數(shù)字時(shí)萧芙，說明這一分支的左/右子樹已經(jīng)到葉子節(jié)點(diǎn)了碴萧，此時(shí)直接返回節(jié)點(diǎn)即可，它的左右子樹都是NULL末购。
另外破喻，在ConstructCore中，我們需要對錯(cuò)誤情況進(jìn)行判斷和處理盟榴，比如說
前序遍歷序列和中序遍歷序列不匹配的情況曹质，在兩次輸出Invalid input的地方都進(jìn)行了判斷。另外擎场，在遞歸的時(shí)候羽德，需要注意將當(dāng)前的中序遍歷和前序遍歷序列中的根節(jié)點(diǎn)排除在外。
3.二叉樹的子結(jié)構(gòu)
問題描述：輸入兩棵二叉樹a和b迅办，判斷b是不是a的子結(jié)構(gòu)宅静。如圖：A中有一部分子樹和B是一樣的，因此B是A的子結(jié)構(gòu)站欺。
算法思想
回到題目，在一棵樹中判斷它的子結(jié)構(gòu)矾策，可以分為兩步磷账，第一步，在A中找到和B的根結(jié)點(diǎn)一樣的結(jié)點(diǎn)R贾虽；第二步逃糟，判斷A中以R為根結(jié)點(diǎn)的子樹是否存在和B一樣的結(jié)構(gòu)。
以上面的例子為例蓬豁，我們現(xiàn)在A中找結(jié)點(diǎn)值為8的節(jié)點(diǎn)绰咽，先找到根節(jié)點(diǎn)，接著遍歷它的子結(jié)點(diǎn)地粪，左子結(jié)點(diǎn)為8取募，和B中的結(jié)構(gòu)不同，需要第二次找值為8的父結(jié)點(diǎn)驶忌，這次找到的是根結(jié)點(diǎn)的左子結(jié)點(diǎn)8矛辕，比較之后發(fā)現(xiàn)它的左右子樹和B的根結(jié)點(diǎn)的左右子樹相同，問題得到解決付魔。
從上面的分析我們得到聊品，這其實(shí)就是遍歷的過程，遍歷A几苍，找到B的根結(jié)點(diǎn)在A中的位置翻屈。然后在遍歷A中的結(jié)點(diǎn)，判斷結(jié)構(gòu)是否相同妻坝。而這里的遍歷方式是前序遍歷伸眶。
代碼
二叉樹結(jié)構(gòu)定義。
typedef struct BinaryTreeNode
{
int value;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
//判斷樹1中是否存在樹2
bool DoesTree1HaveTree2(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2)刽宪；
bool HasSubtree(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2)
{
int result = false;
if (pRoot1 != NULL && pRoot2 != NULL)
{
//在A中找到B的根結(jié)點(diǎn)的位置厘贼，下一步需要判斷以這個(gè)結(jié)點(diǎn)為根節(jié)點(diǎn)的子樹是否和B的結(jié)構(gòu)相同
if (pRoot1->value == pRoot2->value)
result = DoesTree1HaveTree2(pRoot1, pRoot2);
//如果出現(xiàn)結(jié)構(gòu)不匹配，需重新找到B的根結(jié)點(diǎn)對應(yīng)的A中的結(jié)點(diǎn)
if (!result)
result = HasSubtree(pRoot1->m_pLeft, pRoot2);
if (!result)
result = HasSubtree(pRoot1->m_pRight, pRoot2);
return result;
}
}
DoesTree1HaveTree2是判斷A中以R為根結(jié)點(diǎn)的子樹是否和B有相同的結(jié)構(gòu)圣拄。首先判斷A中的R結(jié)點(diǎn)和B的根結(jié)點(diǎn)的值是否相同嘴秸，我們有遞歸的方法判斷，如果不同肯定不是相同的結(jié)構(gòu)庇谆，如果相同的話岳掐，再遞歸的判斷左子樹和右子樹是否相等。遞歸的結(jié)束條件是到達(dá)B樹的葉子結(jié)點(diǎn)饭耳。
bool DoesTree1HaveTree2(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2)
{
if (pRoot2 == NULL)
return true;
if (pRoot1 == NULL)
return false;
if (pRoot1->value != pRoot2->value)
return false;
//pRoot1->value == pRoot2->value,接下來判斷左子樹和右子樹是否相等
return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft)
&& DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
}
總結(jié)
這一節(jié)二叉樹就到這里了串述，需要注意理解二叉樹的幾種遍歷方式，然后在題目中靈活運(yùn)用寞肖，二叉樹的遍歷一般是用遞歸來解決纲酗，遞歸時(shí)要注意結(jié)束條件的設(shè)置。
