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