深入淺出：二叉樹詳解（含C代碼）

【導讀】：樹是數(shù)據(jù)結(jié)構(gòu)中的重中之重，尤其以各類二叉樹為學習的難點。在面試環(huán)節(jié)中，二叉樹也是必考的模塊。本文主要講二叉樹操作的相關知識，梳理面試?？嫉膬?nèi)容。請大家跟隨小編一起來復習吧。

本文針對面試中常見的二叉樹操作做個總結(jié)：

1. 前序遍歷，中序遍歷，后序遍歷；
2. 層次遍歷；
3. 求樹的結(jié)點數(shù)；
4. 求樹的葉子數(shù)；
5. 求樹的深度；
6. 求二叉樹第k層的結(jié)點個數(shù)；
7. 判斷兩棵二叉樹是否結(jié)構(gòu)相同；
8. 求二叉樹的鏡像；
9. 求兩個結(jié)點的最低公共祖先結(jié)點；
10. 求任意兩結(jié)點距離；
11. 找出二叉樹中某個結(jié)點的所有祖先結(jié)點；
12. 不使用遞歸和棧遍歷二叉樹；
13. 二叉樹前序中序推后序；
14. 判斷二叉樹是不是完全二叉樹；
15. 判斷是否是二叉查找樹的后序遍歷結(jié)果；
16. 給定一個二叉查找樹中的結(jié)點，找出在中序遍歷下它的后繼和前驅(qū)；
17. 二分查找樹轉(zhuǎn)化為排序的循環(huán)雙鏈表；
18. 有序鏈表轉(zhuǎn)化為平衡的二分查找樹；
19. 判斷是否是二叉查找樹。

1 前序遍歷，中序遍歷，后序遍歷；

1.1 前序遍歷

對于當前結(jié)點，先輸出該結(jié)點，然后輸出它的左孩子，最后輸出它的右孩子。以上圖為例，遞歸的過程如下：

1. 輸出 1，接著左孩子；
2. 輸出 2，接著左孩子；
3. 輸出 4，左孩子為空，再接著右孩子；
4. 輸出 6，左孩子為空，再接著右孩子；
5. 輸出 7，左右孩子都為空，此時 2 的左子樹全部輸出，2 的右子樹為空，此時 1 的左子樹全部輸出，接著 1 的右子樹；
6. 輸出 3，接著左孩子；
7. 輸出 5，左右孩子為空，此時 3 的左子樹全部輸出，3 的右子樹為空，至此 1 的右子樹全部輸出，結(jié)束。

而非遞歸版本只是利用 stack 模擬上述過程而已，遞歸的過程也就是出入棧的過程。

/*?前序遍歷遞歸版?*/
void?PreOrderRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;
????cout?<data?<"?";???//?先輸出當前結(jié)點???
????PreOrderRec(node->left);?????//?然后輸出左孩子
????PreOrderRec(node->right);????//?最后輸出右孩子
}

/*?前序遍歷非遞歸版?*/
void?PreOrderNonRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;

????stack?S;
????cout?<data?<"?";
????S.push(node);
????node?=?node->left;

????while?(!S.empty()?||?node)
????{
????????while?(node)
????????{
????????????cout?<data?<"?";?//?先輸出當前結(jié)點??
????????????S.push(node);
????????????node?=?node->left;?????????//?然后輸出左孩子
????????}??????????????????????????????//?while?結(jié)束意味著左孩子已經(jīng)全部輸出

????????node?=?S.top()->right;?????????//?最后輸出右孩子
????????S.pop();
????}
}


1.2 中序遍歷

對于當前結(jié)點，先輸出它的左孩子，然后輸出該結(jié)點，最后輸出它的右孩子。以（1.1）圖為例：

1. 1-->2-->4，4 的左孩子為空，輸出 4，接著右孩子；
2. 6 的左孩子為空，輸出 6，接著右孩子；
3. 7 的左孩子為空，輸出 7，右孩子也為空，此時 2 的左子樹全部輸出，輸出 2，2 的右孩子為空，此時 1 的左子樹全部輸出，輸出 1，接著 1 的右孩子；
4. 3-->5，5 左孩子為空，輸出 5，右孩子也為空，此時 3 的左子樹全部輸出，而 3 的右孩子為空，至此 1 的右子樹全部輸出，結(jié)束。

/*?中序遍歷遞歸版?*/
void?InOrderRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;

????InOrderRec(node->left);?????//?先輸出左孩子
????cout?<data?<"?";??//?然后輸出當前結(jié)點
????InOrderRec(node->right);????//?最后輸出右孩子
}

/*?前序遍歷非遞歸版?*/
void?InOrderNonRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;

????stack?S;
????S.push(node);
????node?=?node->left;

????while?(!S.empty()?||?node)
????{
????????while?(node)
????????{
????????????S.push(node);
????????????node?=?node->left;
????????}?????????????????????????????//?while?結(jié)束意味著左孩子為空

????????cout?<data?<"?";?//?左孩子已經(jīng)全部輸出，接著輸出當前結(jié)點
????????node?=?S.top()->right;????????//?左孩子全部輸出，當前結(jié)點也輸出后，最后輸出右孩子
????????S.pop();
????}
}


1.3 后序遍歷

對于當前結(jié)點，先輸出它的左孩子，然后輸出它的右孩子，最后輸出該結(jié)點。依舊以（1.1）圖為例：

1. 1->2->4->6->7，7 無左孩子，也無右孩子，輸出 7，此時 6 無左孩子，而 6 的右子樹也全部輸出，輸出 6，此時 4 無左子樹，而 4 的右子樹已全部輸出，接著輸出 4，此時 2 的左子樹全部輸出，且 2 無右子樹，輸出 2，此時 1 的左子樹全部輸出，接著轉(zhuǎn)向右子樹；
2. 3->5，5 無左孩子，也無右孩子，輸出 5，此時 3 的左子樹全部輸出，且 3 無右孩子，輸出 3，此時 1 的右子樹全部輸出，輸出 1，結(jié)束。

非遞歸版本中，對于一個結(jié)點，如果我們要輸出它，只有它既沒有左孩子也沒有右孩子或者它有孩子但是它的孩子已經(jīng)被輸出（由此設置 pre 變量）。若非上述兩種情況，則將該結(jié)點的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候,先依次遍歷左子樹和右子樹。

/*?后序遍歷遞歸版?*/
void?PostOrderRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;

????PostOrderRec(node->left);???//?先輸出左孩子
????PostOrderRec(node->right);??//?然后輸出右孩子
????cout?<data?<"?";??//?最后輸出當前結(jié)點
}

/*?后序遍歷非遞歸版?*/
void?PostOrderNonRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;

????Node?*?pre?=?nullptr;
????stack?S;
????S.push(node);

????while?(!S.empty())
????{
????????node?=?S.top();

????????if?((!node->left?