深入淺出：二叉樹詳解（含C代碼）
[導(dǎo)讀]【導(dǎo)讀】：樹是數(shù)據(jù)結(jié)構(gòu)中的重中之重，尤其以各類二叉樹為學(xué)習(xí)的難點(diǎn)。在面試環(huán)節(jié)中，二叉樹也是必考的模塊。本文主要講二叉樹操作的相關(guān)知識(shí)，梳理面試?？嫉膬?nèi)容。請(qǐng)大家跟隨小編一起來復(fù)習(xí)吧。本文針對(duì)面試中常見的二叉樹操作做個(gè)總結(jié)：前序遍歷，中序遍歷，后序遍歷；層次遍歷；求樹的結(jié)點(diǎn)數(shù)；求樹...
【導(dǎo)讀】：樹是數(shù)據(jù)結(jié)構(gòu)中的重中之重，尤其以各類二叉樹為學(xué)習(xí)的難點(diǎn)。在面試環(huán)節(jié)中，二叉樹也是必考的模塊。本文主要講二叉樹操作的相關(guān)知識(shí)，梳理面試常考的內(nèi)容。請(qǐng)大家跟隨小編一起來復(fù)習(xí)吧。
本文針對(duì)面試中常見的二叉樹操作做個(gè)總結(jié)：
- 前序遍歷，中序遍歷，后序遍歷；
- 層次遍歷；
- 求樹的結(jié)點(diǎn)數(shù)；
- 求樹的葉子數(shù)；
- 求樹的深度；
- 求二叉樹第k層的結(jié)點(diǎn)個(gè)數(shù)；
- 判斷兩棵二叉樹是否結(jié)構(gòu)相同；
- 求二叉樹的鏡像；
- 求兩個(gè)結(jié)點(diǎn)的最低公共祖先結(jié)點(diǎn)；
- 求任意兩結(jié)點(diǎn)距離；
- 找出二叉樹中某個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)；
- 不使用遞歸和棧遍歷二叉樹；
- 二叉樹前序中序推后序；
- 判斷二叉樹是不是完全二叉樹；
- 判斷是否是二叉查找樹的后序遍歷結(jié)果；
- 給定一個(gè)二叉查找樹中的結(jié)點(diǎn)，找出在中序遍歷下它的后繼和前驅(qū)；
- 二分查找樹轉(zhuǎn)化為排序的循環(huán)雙鏈表；
- 有序鏈表轉(zhuǎn)化為平衡的二分查找樹；
- 判斷是否是二叉查找樹。
1 前序遍歷，中序遍歷，后序遍歷；
1.1 前序遍歷
對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出該結(jié)點(diǎn)，然后輸出它的左孩子，最后輸出它的右孩子。以上圖為例，遞歸的過程如下：- 輸出 1，接著左孩子；
- 輸出 2，接著左孩子；
- 輸出 4，左孩子為空，再接著右孩子；
- 輸出 6，左孩子為空，再接著右孩子；
- 輸出 7，左右孩子都為空，此時(shí) 2 的左子樹全部輸出，2 的右子樹為空，此時(shí) 1 的左子樹全部輸出，接著 1 的右子樹；
- 輸出 3，接著左孩子；
- 輸出 5，左右孩子為空，此時(shí) 3 的左子樹全部輸出，3 的右子樹為空，至此 1 的右子樹全部輸出，結(jié)束。
/*?前序遍歷遞歸版?*/
void?PreOrderRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;
????cout?<data?<"?";???//?先輸出當(dāng)前結(jié)點(diǎn)???
????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?<"?";?//?先輸出當(dāng)前結(jié)點(diǎn)??
????????????S.push(node);
????????????node?=?node->left;?????????//?然后輸出左孩子
????????}??????????????????????????????//?while?結(jié)束意味著左孩子已經(jīng)全部輸出
????????node?=?S.top()->right;?????????//?最后輸出右孩子
????????S.pop();
????}
}
1.2 中序遍歷
對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出它的左孩子，然后輸出該結(jié)點(diǎn)，最后輸出它的右孩子。以（1.1）圖為例：- 1-->2-->4，4 的左孩子為空，輸出 4，接著右孩子；
- 6 的左孩子為空，輸出 6，接著右孩子；
- 7 的左孩子為空，輸出 7，右孩子也為空，此時(shí) 2 的左子樹全部輸出，輸出 2，2 的右孩子為空，此時(shí) 1 的左子樹全部輸出，輸出 1，接著 1 的右孩子；
- 3-->5，5 左孩子為空，輸出 5，右孩子也為空，此時(shí) 3 的左子樹全部輸出，而 3 的右孩子為空，至此 1 的右子樹全部輸出，結(jié)束。
/*?中序遍歷遞歸版?*/
void?InOrderRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;
????InOrderRec(node->left);?????//?先輸出左孩子
????cout?<data?<"?";??//?然后輸出當(dāng)前結(jié)點(diǎn)
????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)全部輸出，接著輸出當(dāng)前結(jié)點(diǎn)
????????node?=?S.top()->right;????????//?左孩子全部輸出，當(dāng)前結(jié)點(diǎn)也輸出后，最后輸出右孩子
????????S.pop();
????}
}
1.3 后序遍歷
對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出它的左孩子，然后輸出它的右孩子，最后輸出該結(jié)點(diǎn)。依舊以（1.1）圖為例：- 1->2->4->6->7，7 無左孩子，也無右孩子，輸出 7，此時(shí) 6 無左孩子，而 6 的右子樹也全部輸出，輸出 6，此時(shí) 4 無左子樹，而 4 的右子樹已全部輸出，接著輸出 4，此時(shí) 2 的左子樹全部輸出，且 2 無右子樹，輸出 2，此時(shí) 1 的左子樹全部輸出，接著轉(zhuǎn)向右子樹；
- 3->5，5 無左孩子，也無右孩子，輸出 5，此時(shí) 3 的左子樹全部輸出，且 3 無右孩子，輸出 3，此時(shí) 1 的右子樹全部輸出，輸出 1，結(jié)束。
/*?后序遍歷遞歸版?*/
void?PostOrderRec(Node?*?node)
{
????if?(node?==?nullptr)
????????return;
????PostOrderRec(node->left);???//?先輸出左孩子
????PostOrderRec(node->right);??//?然后輸出右孩子
????cout?<data?<"?";??//?最后輸出當(dāng)前結(jié)點(diǎn)
}
/*?后序遍歷非遞歸版?*/
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? 
下載文檔
