總結(jié)了19個(gè)常見(jiàn)的二叉樹(shù)操作（附C代碼）
[導(dǎo)讀]關(guān)注、星標(biāo)公眾號(hào)，直達(dá)精彩內(nèi)容文章來(lái)源：segmentfault作者：Ethson【導(dǎo)讀】：樹(shù)是數(shù)據(jù)結(jié)構(gòu)中的重中之重，尤其以各類(lèi)二叉樹(shù)為學(xué)習(xí)的難點(diǎn)。在面試環(huán)節(jié)中，二叉樹(shù)也是必考的模塊。本文主要講二叉樹(shù)操作的相關(guān)知識(shí)，梳理面試?？嫉膬?nèi)容。請(qǐng)大家跟隨小編一起來(lái)復(fù)習(xí)吧。本文針對(duì)面試中常...
文章來(lái)源：segmentfault
- 前序遍歷，中序遍歷，后序遍歷；
- 層次遍歷；
- 求樹(shù)的結(jié)點(diǎn)數(shù)；
- 求樹(shù)的葉子數(shù)；
- 求樹(shù)的深度；
- 求二叉樹(shù)第k層的結(jié)點(diǎn)個(gè)數(shù)；
- 判斷兩棵二叉樹(shù)是否結(jié)構(gòu)相同；
- 求二叉樹(shù)的鏡像；
- 求兩個(gè)結(jié)點(diǎn)的最低公共祖先結(jié)點(diǎn)；
- 求任意兩結(jié)點(diǎn)距離；
- 找出二叉樹(shù)中某個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)；
- 不使用遞歸和棧遍歷二叉樹(shù)；
- 二叉樹(shù)前序中序推后序；
- 判斷二叉樹(shù)是不是完全二叉樹(shù)；
- 判斷是否是二叉查找樹(shù)的后序遍歷結(jié)果；
- 給定一個(gè)二叉查找樹(shù)中的結(jié)點(diǎn)，找出在中序遍歷下它的后繼和前驅(qū)；
- 二分查找樹(shù)轉(zhuǎn)化為排序的循環(huán)雙鏈表；
- 有序鏈表轉(zhuǎn)化為平衡的二分查找樹(shù)；
- 判斷是否是二叉查找樹(shù)。
1 前序遍歷，中序遍歷，后序遍歷；
1.1 前序遍歷
對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出該結(jié)點(diǎn)，然后輸出它的左孩子，最后輸出它的右孩子。以上圖為例，遞歸的過(guò)程如下：
- 輸出 1，接著左孩子；
- 輸出 2，接著左孩子；
- 輸出 4，左孩子為空，再接著右孩子；
- 輸出 6，左孩子為空，再接著右孩子；
- 輸出 7，左右孩子都為空，此時(shí) 2 的左子樹(shù)全部輸出，2 的右子樹(shù)為空，此時(shí) 1 的左子樹(shù)全部輸出，接著 1 的右子樹(shù)；
- 輸出 3，接著左孩子；
- 輸出 5，左右孩子為空，此時(shí) 3 的左子樹(shù)全部輸出，3 的右子樹(shù)為空，至此 1 的右子樹(shù)全部輸出，結(jié)束。
/* 前序遍歷遞歸版 */
void PreOrderRec(Node * node)
{
if (node == nullptr)
return;
cout << node->data << " "; // 先輸出當(dāng)前結(jié)點(diǎn)
PreOrderRec(node->left); // 然后輸出左孩子
PreOrderRec(node->right); // 最后輸出右孩子
}
/* 前序遍歷非遞歸版 */
void PreOrderNonRec(Node * node)
{
if (node == nullptr)
return;
stack S;
cout << node->data << " ";
S.push(node);
node = node->left;
while (!S.empty() || node)
{
while (node)
{
cout << node->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 的左子樹(shù)全部輸出，輸出 2，2 的右孩子為空，此時(shí) 1 的左子樹(shù)全部輸出，輸出 1，接著 1 的右孩子；
-
3-->5，5 左孩子為空，輸出 5，右孩子也為空，此時(shí) 3 的左子樹(shù)全部輸出，而 3 的右孩子為空，至此 1 的右子樹(shù)全部輸出，結(jié)束。
/* 中序遍歷遞歸版 */
void InOrderRec(Node * node)
{
if (node == nullptr)
return;
InOrderRec(node->left); // 先輸出左孩子
cout << node->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 << S.top()->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 無(wú)左孩子，也無(wú)右孩子，輸出 7，此時(shí) 6 無(wú)左孩子，而 6 的右子樹(shù)也全部輸出，輸出 6，此時(shí) 4 無(wú)左子樹(shù)，而 4 的右子樹(shù)已全部輸出，接著輸出 4，此時(shí) 2 的左子樹(shù)全部輸出，且 2 無(wú)右子樹(shù)，輸出 2，此時(shí) 1 的左子樹(shù)全部輸出，接著轉(zhuǎn)向右子樹(shù)；
-
3->5，5 無(wú)左孩子，也無(wú)右孩子，輸出 5，此時(shí) 3 的左子樹(shù)全部輸出，且 3 無(wú)右孩子，輸出 3，此時(shí) 1 的右子樹(shù)全部輸出，輸出 1，結(jié)束。
非遞歸版本中，對(duì)于一個(gè)結(jié)點(diǎn)，如果我們要輸出它，只有它既沒(méi)有左孩子也沒(méi)有右孩子或者它有孩子但是它的孩子已經(jīng)被輸出（由此設(shè)置 pre 變量）。若非上述兩種情況，則將該結(jié)點(diǎn)的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時(shí)候,先依次遍歷左子樹(shù)和右子樹(shù)。
/* 后序遍歷遞歸版 */
void PostOrderRec(Node * node)
{
if (node == nullptr)
return;
PostOrderRec(node->left); // 先輸出左孩子
PostOrderRec(node->right); // 然后輸出右孩子
cout << node->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 
下載文檔
