深入浅出！二叉树详解，包含C语言代码
【導(dǎo)讀】：樹是數(shù)據(jù)結(jié)構(gòu)中的重中之重，尤其以各類二叉樹為學(xué)習(xí)的難點(diǎn)。在考研中，二叉樹也是常考的模塊。本文主要講二叉樹操作的相關(guān)知識(shí)。請(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é)束。
而非遞歸版本只是利用 stack 模擬上述過程而已，遞歸的過程也就是出入棧的過程。
/*?前序遍歷遞歸版?*/ 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<Node*>?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 的左子樹全部輸出，輸出 2，2 的右孩子為空，此時(shí) 1 的左子樹全部輸出，輸出 1，接著 1 的右孩子；
3-->5，5 左孩子為空，輸出 5，右孩子也為空，此時(shí) 3 的左子樹全部輸出，而 3 的右孩子為空，至此 1 的右子樹全部輸出，結(jié)束。
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é)束。
非遞歸版本中，對(duì)于一個(gè)結(jié)點(diǎn)，如果我們要輸出它，只有它既沒有左孩子也沒有右孩子或者它有孩子但是它的孩子已經(jīng)被輸出（由此設(shè)置 pre 變量）。若非上述兩種情況，則將該結(jié)點(diǎn)的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時(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<Node*>?S;S.push(node);while?(!S.empty()){node?=?S.top();if?((!node->left?&&?!node->right)?||????????????????????//?第一個(gè)輸出的必是無左右孩子的葉子結(jié)點(diǎn)，只要第一個(gè)結(jié)點(diǎn)輸出，(pre &&?(pre == node->left || pre == node->right)))?//?以后的 pre 就不會(huì)是空。此處的判斷語句加入一個(gè) pre，只是用來{???????????????????????????????????????????????????????//?確保可以正確輸出第一個(gè)結(jié)點(diǎn)。cout?<<?node->data?<<?"?";??//?左右孩子都全部輸出，再輸出當(dāng)前結(jié)點(diǎn)pre?=?node;S.pop();}else{if?(node->right)S.push(node->right);??//?先進(jìn)右孩子，再進(jìn)左孩子，取出來的才是左孩子if?(node->left)S.push(node->left);}} }2 層次遍歷
void?LevelOrder(Node?*?node) {Node?*?p?=?node;queue<Node*>?Q;??//?隊(duì)列Q.push(p);while?(!Q.empty()){p?=?Q.front();cout?<<?p->data?<<?"?";Q.pop();if?(p->left)Q.push(p->left);??//?注意順序，先進(jìn)左孩子if?(p->right)Q.push(p->right);} }3 求樹的結(jié)點(diǎn)數(shù)
int?CountNodes(Node?*?node) {if?(node?==?nullptr)return?0;return?CountNodes(node->left)?+?CountNodes(node->right)?+?1; }4 求樹的葉子數(shù)
int?CountLeaves(Node?*?node) {if?(node?==?nullptr)return?0;if?(!node->left?&&?!node->right)return?1;return?CountLeaves(node->left)?+?CountLeaves(node->right); }5 求樹的深度
int?GetDepth(Node?*?node) {if?(node?==?nullptr)return?0;int?left_depth?=?GetDepth(node->left)?+?1;int?right_depth?=?GetDepth(node->right)?+?1;return?left_depth?>?right_depth???left_depth?:?right_depth; }6 求二叉樹第k層的結(jié)點(diǎn)個(gè)數(shù)
int?GetKLevel(Node?*?node,?int?k) {if?(node?==?nullptr)return?0;if?(k?==?1)return?1;return?GetKLevel(node->left,?k?-?1)?+?GetKLevel(node->right,?k?-?1); }7 判斷兩棵二叉樹是否結(jié)構(gòu)相同
不考慮數(shù)據(jù)內(nèi)容。結(jié)構(gòu)相同意味著對(duì)應(yīng)的左子樹和對(duì)應(yīng)的右子樹都結(jié)構(gòu)相同。
bool?StructureCmp(Node?*?node1,?Node?*?node2) {if?(node1?==?nullptr?&&?node2?==?nullptr)return?true;else?if?(node1?==?nullptr?||?node2?==?nullptr)return?false;return?StructureCmp(node1->left,?node2->left)?&&?Str1uctureCmp(node1->right,?node2->right); }8 求二叉樹的鏡像
對(duì)于每個(gè)結(jié)點(diǎn)，我們交換它的左右孩子即可。
void?Mirror(Node?*?node) {if?(node?==?nullptr)return;Node?*?temp?=?node->left;node->left?=?node->right;node->right?=?temp;Mirror(node->left);Mirror(node->right); }9 求兩個(gè)結(jié)點(diǎn)的最低公共祖先結(jié)點(diǎn)
最低公共祖先，即 LCA（Lowest Common Ancestor），見下圖：結(jié)點(diǎn) 3 和結(jié)點(diǎn) 4 的最近公共祖先是結(jié)點(diǎn) 2，即 LCA(3,4)=2。在此，需要注意到當(dāng)兩個(gè)結(jié)點(diǎn)在同一棵子樹上的情況，如結(jié)點(diǎn) 3 和結(jié)點(diǎn) 2 的最近公共祖先為 2，即 LCA(3,2)=2。同理 LCA(5,6)=4，LCA(6,10)=1。
Node?*?FindLCA(Node?*?node,?Node?*?target1,?Node?*?target2) {if?(node?==?nullptr)return?nullptr;if?(node?==?target1?||?node?==?target2)return?node;Node?*?left?=?FindLCA(node->left,?target1,?target2);Node?*?right?=?FindLCA(node->right,?target1,?target2);if?(left?&&?right)??//?分別在左右子樹return?node;return?left???left?:?right;??//?都在左子樹或右子樹 }10 求任意兩結(jié)點(diǎn)距離
首先找到兩個(gè)結(jié)點(diǎn)的 LCA，然后分別計(jì)算 LCA 與它們的距離，最后相加即可。
int?FindLevel(Node?*?node,?Node?*?target) {if?(node?==?nullptr)return?-1;if?(node?==?target)return?0;int?level?=?FindLevel(node->left,?target);??//?先在左子樹找if?(level?==?-1)level?=?FindLevel(node->right,?target);??//?如果左子樹沒找到，在右子樹找if?(level?!=?-1)??//?找到了，回溯return?level?+?1;return?-1;??//?如果左右子樹都沒找到 }int?DistanceNodes(Node?*?node,?Node?*?target1,?Node?*?target2) {Node?*?lca?=?FindLCA(node,?target1,?target2);??//?找到最低公共祖先結(jié)點(diǎn)int?level1?=?FindLevel(lca,?target1);?int?level2?=?FindLevel(lca,?target2);return?level1?+?level2; }11 找出二叉樹中某個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)
如果給定結(jié)點(diǎn) 5，則其所有祖先結(jié)點(diǎn)為 4,2,1。
bool?FindAllAncestors(Node?*?node,?Node?*?target) {if?(node?==?nullptr)return?false;if?(node?==?target)return?true;if?(FindAllAncestors(node->left,?target)?||?FindAllAncestors(node->right,?target))??//?找到了{(lán)cout?<<?node->data?<<?"?";return?true;??//?回溯}return?false;??//?如果左右子樹都沒找到 }12 不使用遞歸和棧遍歷二叉樹
1968 年，高德納（Donald Knuth）提出一個(gè)問題：是否存在一個(gè)算法，它不使用棧也不破壞二叉樹結(jié)構(gòu)，但是可以完成對(duì)二叉樹的遍歷？隨后 1979 年，James H. Morris 提出了二叉樹線索化，解決了這個(gè)問題。（根據(jù)這個(gè)概念我們又提出了一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，即線索二叉樹，因線索二叉樹不是本文要介紹的內(nèi)容，所以有興趣的朋友請(qǐng)移步線索二叉樹）
前序，中序，后序遍歷，不管是遞歸版本還是非遞歸版本，都用到了一個(gè)數(shù)據(jù)結(jié)構(gòu)--棧，為何要用棧？那是因?yàn)槠渌姆绞經(jīng)]法記錄當(dāng)前結(jié)點(diǎn)的 parent,而如果在每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)里面加個(gè) parent 分量顯然是不現(xiàn)實(shí)的，而線索化正好解決了這個(gè)問題，其含義就是利用結(jié)點(diǎn)的右孩子空指針，指向該結(jié)點(diǎn)在中序序列中的后繼。下面具體來看看如何使用線索化來完成對(duì)二叉樹的遍歷。先看前序遍歷，步驟如下：
如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則輸出當(dāng)前結(jié)點(diǎn)并將其右孩子作為當(dāng)前結(jié)點(diǎn)；
如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，在當(dāng)前結(jié)點(diǎn)的左子樹中找到當(dāng)前結(jié)點(diǎn)在中序遍歷下的前驅(qū)結(jié)點(diǎn)；
2.1如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，輸出當(dāng)前結(jié)點(diǎn)并把當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；
2.2如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，將它的右孩子重新設(shè)為空，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；
重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點(diǎn)為空。
再來看中序遍歷，和前序遍歷相比只改動(dòng)一句代碼，步驟如下：
如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則輸出當(dāng)前結(jié)點(diǎn)并將其右孩子作為當(dāng)前結(jié)點(diǎn)；
如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，在當(dāng)前結(jié)點(diǎn)的左子樹中找到當(dāng)前結(jié)點(diǎn)在中序遍歷下的前驅(qū)結(jié)點(diǎn)；
2.1. 如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；
2.2. 如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，將它的右孩子重新設(shè)為空，輸出當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；
重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點(diǎn)為空。
最后看下后序遍歷，后序遍歷有點(diǎn)復(fù)雜，需要建立一個(gè)虛假根結(jié)點(diǎn) dummy，令其左孩子是 root。并且還需要一個(gè)子過程，就是倒序輸出某兩個(gè)結(jié)點(diǎn)之間路徑上的各個(gè)結(jié)點(diǎn)。步驟如下：
如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則將其右孩子作為當(dāng)前結(jié)點(diǎn)；
如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，在當(dāng)前結(jié)點(diǎn)的左子樹中找到當(dāng)前結(jié)點(diǎn)在中序遍歷下的前驅(qū)結(jié)點(diǎn)；
2.1. 如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；
2.2. 如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，將它的右孩子重新設(shè)為空，倒序輸出從當(dāng)前結(jié)點(diǎn)的左孩子到該前驅(qū)結(jié)點(diǎn)這條路徑上的所有結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；
重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點(diǎn)為空。
dummy 用的非常巧妙，建議讀者配合上面的圖模擬下算法流程。
13 二叉樹前序中序推后序
| 前序 | [1 2 4 7 3 5 8 9 6] |
| 中序 | [4 7 2 1 8 5 9 3 6] |
| 后序 | [7 4 2 8 9 5 6 3 1] |
以上面圖表為例，步驟如下：
根據(jù)前序可知根結(jié)點(diǎn)為1；
根據(jù)中序可知 4 7 2 為根結(jié)點(diǎn) 1 的左子樹和 8 5 9 3 6 為根結(jié)點(diǎn) 1 的右子樹；
遞歸實(shí)現(xiàn)，把 4 7 2 當(dāng)做新的一棵樹和 8 5 9 3 6 也當(dāng)做新的一棵樹；
在遞歸的過程中輸出后序。
當(dāng)然我們也可以根據(jù)前序和中序構(gòu)造出二叉樹，進(jìn)而求出后序。
/*?該函數(shù)返回二叉樹的根結(jié)點(diǎn)?*/ Node?*?Create(int?pos1,?int?pos2,?int?n) {Node?*?p?=?nullptr;for?(int?i?=?0;?i?<?n;?i++){if?(pre_order_arry[pos1]?==?in_order_arry[pos2?+?i]){p?=?new?Node(pre_order_arry[pos1]);p->left?=?Create(pos1?+?1,?pos2,?i);p->right?=?Create(pos1?+?i?+?1,?pos2?+?i?+?1,?n?-?i?-?1);return?p;}}return?p; }14 判斷二叉樹是不是完全二叉樹
若設(shè)二叉樹的深度為 h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹（Complete Binary Tree）。如下圖：
首先若一個(gè)結(jié)點(diǎn)只有右孩子，肯定不是完全二叉樹；其次若只有左孩子或沒有孩子，那么接下來的所有結(jié)點(diǎn)肯定都沒有孩子，否則就不是完全二叉樹，因此設(shè)置 flag 標(biāo)記變量。
bool?IsCBT(Node?*?node) {bool?flag?=?false;queue<Node*>?Q;Q.push(node);while?(!Q.empty()){Node?*?p?=?Q.front();Q.pop();if?(flag){if?(p->left?||?p->right)return?false;}else{if?(p->left?&&?p->right){Q.push(p->left);Q.push(p->right);}else?if?(p->right)??//?只有右結(jié)點(diǎn)return?false;else?if?(p->left)???//?只有左結(jié)點(diǎn){Q.push(p->left);flag?=?true;}else??//?沒有結(jié)點(diǎn)flag?=?true;}}return?true; }15 判斷是否是二叉查找樹的后序遍歷結(jié)果
在后續(xù)遍歷得到的序列中，最后一個(gè)元素為樹的根結(jié)點(diǎn)。從頭開始掃描這個(gè)序列，比根結(jié)點(diǎn)小的元素都應(yīng)該位于序列的左半部分；從第一個(gè)大于跟結(jié)點(diǎn)開始到跟結(jié)點(diǎn)前面的一個(gè)元素為止，所有元素都應(yīng)該大于跟結(jié)點(diǎn)，因?yàn)檫@部分元素對(duì)應(yīng)的是樹的右子樹。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認(rèn)序列的左、右兩部分是不是都是二元查找樹。
int?array[n];??//?長(zhǎng)度為?n?的序列，注意?begin?和?end?遵循的是左閉右閉原則bool?IsSequenceOfBST(int?begin,?int?end) {if?(end?-?begin?<=?0)return?true;int?root_data?=?array[end];??//?數(shù)組尾元素為根結(jié)點(diǎn)int?i?=?begin;for?(;?array[i]?<?root_data;?i++)?//?取得左子樹;int?j?=?i;for?(;?j?<?end;?j++)if?(array[j]?< root_data)??//?此時(shí)右子樹應(yīng)該都大于根結(jié)點(diǎn)；若存在小于，直接?return?falsereturn?false;return?IsSequenceOfBST(begin,?i?-?1)?&&?IsSequenceOfBST(i,?end?-?1);??//?左右子樹是否都滿足 }16 給定一個(gè)二叉查找樹中的結(jié)點(diǎn)（存在一個(gè)指向父親結(jié)點(diǎn)的指針），找出在中序遍歷下它的后繼和前驅(qū)
一棵二叉查找樹的中序遍歷序列，正好是升序序列。假如根結(jié)點(diǎn)的父結(jié)點(diǎn)為 nullptr，則：
如果當(dāng)前結(jié)點(diǎn)有右孩子，則后繼結(jié)點(diǎn)為這個(gè)右孩子的最左孩子；
如果當(dāng)前結(jié)點(diǎn)沒有右孩子；
2.1. 當(dāng)前結(jié)點(diǎn)為根結(jié)點(diǎn)，返回 nullptr；
2.2. 當(dāng)前結(jié)點(diǎn)只是個(gè)普通結(jié)點(diǎn)，也就是存在父結(jié)點(diǎn)；
2.2.1. 當(dāng)前結(jié)點(diǎn)是父親結(jié)點(diǎn)的左孩子，則父親結(jié)點(diǎn)就是后繼結(jié)點(diǎn)；
2.2.2. 當(dāng)前結(jié)點(diǎn)是父親結(jié)點(diǎn)的右孩子，沿著父親結(jié)點(diǎn)往上走，直到 n-1 代祖先是 n 代祖先的左孩子，則后繼為 n 代祖先或遍歷到根結(jié)點(diǎn)也沒找到符合的，則當(dāng)前結(jié)點(diǎn)就是中序遍歷的最后一個(gè)結(jié)點(diǎn)，返回 nullptr。
仔細(xì)觀察上述代碼，總覺得有點(diǎn)啰嗦。比如，過多的 return，步驟 2 的層次太多。綜合考慮所有情況，改進(jìn)代碼如下：
Node?*?Increment(Node?*?node) {if?(node->right){node?=?node->right;while?(node->left)node?=?node->left;}else{Node?*?p?=?node->parent;while?(p?&&?p->right?==?node){node?=?p;p?=?p->parent;}node?=?p;}return?node; }上述的代碼是基于結(jié)點(diǎn)有 parent 指針的，若題意要求沒有 parent 呢？網(wǎng)上也有人給出了答案，個(gè)人覺得沒有什么價(jià)值，有興趣的朋友可以到這里查看。
而求前驅(qū)結(jié)點(diǎn)的話，只需把上述代碼的 left 與 right 互調(diào)即可，很簡(jiǎn)單。
17 二分查找樹轉(zhuǎn)化為排序的循環(huán)雙鏈表
二分查找樹的中序遍歷即為升序排列，問題就在于如何在遍歷的時(shí)候更改指針的指向。一種簡(jiǎn)單的方法時(shí)，遍歷二分查找樹，將遍歷的結(jié)果放在一個(gè)數(shù)組中，之后再把該數(shù)組轉(zhuǎn)化為雙鏈表。如果題目要求只能使用 O(1)O(1) 內(nèi)存，則只能在遍歷的同時(shí)構(gòu)建雙鏈表，即進(jìn)行指針的替換。
我們需要用遞歸的方法來解決，假定每個(gè)遞歸調(diào)用都會(huì)返回構(gòu)建好的雙鏈表，可把問題分解為左右兩個(gè)子樹。由于左右子樹都已經(jīng)是有序的，當(dāng)前結(jié)點(diǎn)作為中間的一個(gè)結(jié)點(diǎn)，把左右子樹得到的鏈表連接起來即可。
/*?合并兩個(gè)?a,?b?兩個(gè)循環(huán)雙向鏈表?*/ Node?*?Append(Node?*?a,?Node?*?b) {if?(a?==?nullptr)?return?b;if?(b?==?nullptr)?return?a;//?分別得到兩個(gè)鏈表的最后一個(gè)元素Node?*?a_last?=?a->left;Node?*?b_last?=?b->left;//?將兩個(gè)鏈表頭尾相連??a_last->right?=?b;b->left?=?a_last;a->left?=?b_last;b_last->right?=?a;return?a; }/*?遞歸的解決二叉樹轉(zhuǎn)換為雙鏈表?*/ Node?*?TreeToList(Node?*?node) {if?(node?==?nullptr)?return?nullptr;//?遞歸解決子樹Node?*?left_list?=?TreeToList(node->left);Node?*?right_list?=?TreeToList(node->right);//?把根結(jié)點(diǎn)轉(zhuǎn)換為一個(gè)結(jié)點(diǎn)的雙鏈表，方便后面的鏈表合并??node->left?=?node;node->right?=?node;//?合并之后即為升序排列l(wèi)eft_list?=?Append(left_list,?node);left_list?=?Append(left_list,?right_list);return?left_list; }18 有序鏈表轉(zhuǎn)化為平衡的二分查找樹（Binary Search Tree）
我們可以采用自頂向下的方法。先找到中間結(jié)點(diǎn)作為根結(jié)點(diǎn)，然后遞歸左右兩部分。所以我們需要先找到中間結(jié)點(diǎn)，對(duì)于單鏈表來說，必須要遍歷一邊，可以使用快慢指針加快查找速度。
struct?TreeNode {int?data;TreeNode?*?left;TreeNode?*?right;TreeNode(int?data_)?{?data?=?data_;?left?=?right?=?nullptr;?} };struct?ListNode {int?data;ListNode?*?next;ListNode(int?data_)?{?data?=?data_;?next?=?nullptr;?} };TreeNode?*?SortedListToBST(ListNode?*??list_node) {if?(!list_node)?return?nullptr;if?(!list_node->next)?return?(new?TreeNode(list_node->data));//?用快慢指針找到中間結(jié)點(diǎn)??ListNode?*?pre_slow?=?nullptr;??//?記錄慢指針的前一個(gè)結(jié)點(diǎn)ListNode?*?slow?=?list_node;????//?慢指針ListNode?*?fast?=?list_node;????//?快指針while?(fast?&&?fast->next){pre_slow?=?slow;slow?=?slow->next;fast?=?fast->next->next;}TreeNode?*?mid?=?new?TreeNode(slow->data);//?分別遞歸左右兩部分if?(pre_slow){pre_slow->next?=?nullptr;mid->left?=?SortedListToBST(list_node);}mid->right?=?SortedListToBST(slow->next);return?mid; }由 f(n)=2f(\frac n2)+\frac n2f(n)=2f(2n)+2n 得，所以上述算法的時(shí)間復(fù)雜度為 O(nlogn)O(nlogn)。
不妨換個(gè)思路，采用自底向上的方法：
TreeNode?*?SortedListToBSTRec(ListNode?*&?list,?int?start,?int?end) {if?(start?>?end)?return?nullptr;int?mid?=?start?+?(end?-?start)?/?2;TreeNode?*?left_child?=?SortedListToBSTRec(list,?start,?mid?-?1);??//?注意此處傳入的是引用TreeNode?*?parent?=?new?TreeNode(list->data);parent->left?=?left_child;list?=?list->next;parent->right?=?SortedListToBSTRec(list,?mid?+?1,?end);return?parent; }TreeNode?*?SortedListToBST(ListNode?*?node) {int?n?=?0;ListNode?*?p?=?node;while?(p){n++;p?=?p->next;}return?SortedListToBSTRec(node,?0,?n?-?1); }如此，時(shí)間復(fù)雜度降為 O(n)O(n)。
19 判斷是否是二叉查找樹
我們假定二叉樹沒有重復(fù)元素，即對(duì)于每個(gè)結(jié)點(diǎn)，其左右孩子都是嚴(yán)格的小于和大于。
下面給出兩個(gè)方法：
方法 1：
bool?IsBST(Node?*?node,?int?min,?int?max) {if?(node?==?nullptr)return?true;if?(node->data?<=?min?||?node->data?>=?max)return?false;return?IsBST(node->left,?min,?node->data)?&&?IsBST(node->right,?node->data,?max); }IsBST(node,?INT_MIN,?INT_MAX);方法 2：
利用二叉查找樹中序遍歷時(shí)元素遞增來判斷。
bool?IsBST(Node?*?node) {static?int?pre?=?INT_MIN;if?(node?==?nullptr)return?true;if?(!IsBST(node->left))return?false;if?(node->data?<?pre)return?false;pre?=?node->data;return?IsBST(node->right); }來源 https://segmentfault.com/a/1190000008850005
鏈接：Ethson
您還可以在以下平臺(tái)找到我們
你點(diǎn)的每個(gè)在看，我都認(rèn)真當(dāng)成了喜歡
總結(jié)
以上是生活随笔為你收集整理的深入浅出！二叉树详解，包含C语言代码的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Domain Generalizatio
- 下一篇： 抖音矩阵系统，抖音矩阵系统源码，抖音SE