本章介紹樹(shù)的遍歷（BFS和DFS）、完全二叉樹(shù)、二叉查找樹(shù)、并查集等，重點(diǎn)主要是掌握上述知識(shí)點(diǎn)的代碼實(shí)現(xiàn)。

有關(guān)樹(shù)的常見(jiàn)問(wèn)題有：1）根據(jù)序列創(chuàng)建二叉樹(shù)；2）最近公共祖先問(wèn)題。

樹(shù)的結(jié)點(diǎn)的定義

樹(shù)的結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外，還要有一些指向子節(jié)點(diǎn)的指針。然而，由于每個(gè)子結(jié)點(diǎn)數(shù)可能不同，需要使用一個(gè)vector來(lái)存儲(chǔ)這些指針，可以用一個(gè)類(lèi)來(lái)表示這樣一個(gè)結(jié)點(diǎn)：

樹(shù)的深度優(yōu)先遍歷

樹(shù)的先序遍歷，代碼如下：

樹(shù)的后序遍歷，代碼如下：

樹(shù)的廣度優(yōu)先遍歷（層次遍歷）

樹(shù)的層次遍歷需要使用一個(gè)隊(duì)列來(lái)實(shí)現(xiàn)，其代碼實(shí)現(xiàn)如下：

若希望逐層處理樹(shù)的不同結(jié)點(diǎn)，如在每層的結(jié)點(diǎn)輸出之后加一個(gè)換行符，代碼如下：

樹(shù)的靜態(tài)寫(xiě)法

樹(shù)的結(jié)點(diǎn)類(lèi)定義的靜態(tài)寫(xiě)法如下：

因?yàn)閿?shù)組下標(biāo)不可能是負(fù)數(shù)，因此用-1表示結(jié)點(diǎn)為空結(jié)點(diǎn)。

樹(shù)的靜態(tài)寫(xiě)法下的先序、后序、層次遍歷代碼如下：

?

二叉樹(shù)與二叉樹(shù)的遍歷

二叉樹(shù)結(jié)點(diǎn)的定義，代碼如下：

二叉樹(shù)的遍歷（先序、中序、后序遍歷，層次遍歷），代碼如下：

完全二叉樹(shù)

判斷一棵樹(shù)是否是完全二叉樹(shù)？（核心是層次遍歷）若二叉樹(shù)有N個(gè)結(jié)點(diǎn)，根節(jié)點(diǎn)編號(hào)為1，對(duì)該二叉樹(shù)進(jìn)行層次遍歷后，若給定二叉樹(shù)是完全二叉樹(shù)，那么遍歷得到的結(jié)點(diǎn)編號(hào)必然會(huì)逐一覆蓋1~N的N個(gè)數(shù)字。根據(jù)這一點(diǎn)，只需定義一個(gè)i從1~N枚舉，而后對(duì)二叉樹(shù)進(jìn)行層次遍歷，判斷遍歷的當(dāng)前節(jié)點(diǎn)是否等于i，即可判斷是否完全二叉樹(shù)。代碼如下：

二叉查找樹(shù)（或稱(chēng)二叉搜索樹(shù)、二叉排序樹(shù)）

由于二叉查找樹(shù)的數(shù)據(jù)域滿(mǎn)足左子樹(shù)≤根結(jié)點(diǎn)＜右子樹(shù)，因此二叉查找樹(shù)的中序遍歷一定是為升序排列的。

二叉查找樹(shù)的插入：

二叉查找樹(shù)的查找：

根據(jù)遍歷序列創(chuàng)建二叉樹(shù)的問(wèn)題

只要給出中序遍歷序列和其他任意一種遍歷序列，就可以唯一確定一棵二叉樹(shù)。

①給出中序遍歷和先序遍歷，創(chuàng)建二叉樹(shù)：

輸出后序遍歷序列：

②給出中序遍歷和后序遍歷，創(chuàng)建二叉樹(shù)：

輸出先序遍歷序列：

—————————————————————————————————————————

建立二叉查找樹(shù)時(shí)，只需知道前序遍歷序列或者后序遍歷序列即可（中序遍歷一定是升序）。

③給出先序遍歷序列，創(chuàng)建二叉查找樹(shù)：?

輸出二叉查找樹(shù)的后序遍歷：

④給出后序遍歷序列，創(chuàng)建二叉查找樹(shù)：?

需要注意的是，左右子樹(shù)根節(jié)點(diǎn)應(yīng)該是從右往左找第一個(gè)，用rbegin查找到后還需post的大小來(lái)得到根結(jié)點(diǎn)位置，因此可以將post反轉(zhuǎn)后再操作（就不用傳post大小，而且是從左到右順序查找）。

?輸出二叉查找樹(shù)的先序遍歷：

最近公共祖先問(wèn)題（Lowest Common Ancestor，LCA）

指尋找兩個(gè)結(jié)點(diǎn)所有公共祖先中距離這兩個(gè)結(jié)點(diǎn)最近的祖先節(jié)點(diǎn)的問(wèn)題。

①找到普通二叉樹(shù)中的p、q結(jié)點(diǎn)的LCA，代碼如下：

或簡(jiǎn)寫(xiě)作：

（妙）根據(jù)中根遍歷和后根遍歷建立樹(shù)并查找兩個(gè)節(jié)點(diǎn)的最近公共祖先：

②找到二叉樹(shù)查找中的p、q結(jié)點(diǎn)的LCA，代碼如下：

或簡(jiǎn)寫(xiě)為：

（妙）根據(jù)先序序列建二叉查找樹(shù)并找到樹(shù)中兩節(jié)點(diǎn)的最近公共祖先：

并查集

是一種維護(hù)集合的數(shù)據(jù)結(jié)構(gòu)，它的名字源于合并（union）、查找（find）、集合（set）三個(gè)名詞。并查集支持兩種效率很高的操作：①快速查詢(xún)兩個(gè)元素是否在一個(gè)集合中；②快速合并兩個(gè)元素所代表的不同集合。

通常用一個(gè)數(shù)組ufs來(lái)實(shí)現(xiàn)并查集。數(shù)組下標(biāo)表示節(jié)點(diǎn)的編號(hào)，所對(duì)應(yīng)的數(shù)組元素的值作為這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)。初始情況下，每個(gè)節(jié)點(diǎn)都是一個(gè)集合，即每個(gè)結(jié)點(diǎn)所在樹(shù)的根結(jié)點(diǎn)都是它本身，有ufs[i]=i?？梢酝ㄟ^(guò)遞歸查找結(jié)點(diǎn)的父節(jié)點(diǎn)最終找到根結(jié)點(diǎn)。

1.初始化并查集：

2.查找給定節(jié)點(diǎn)所在樹(shù)的樹(shù)根結(jié)點(diǎn)：

3.合并兩個(gè)結(jié)點(diǎn)所在集合為同一集合（判斷兩節(jié)點(diǎn)的樹(shù)根是否相同，相同則無(wú)需合并，不相同則遵循靠左原則）：

4.路徑壓縮（即查找時(shí)更關(guān)注根結(jié)點(diǎn)（所在的集合）而非其父節(jié)點(diǎn)），只需找到根結(jié)點(diǎn)后將ufs[x]改為根結(jié)點(diǎn)即可，代碼如下：

構(gòu)建并查集的全部代碼如下：