目錄

1.什么是樹

1.1淺顯的理解樹

1.2 數(shù)據(jù)結(jié)構(gòu)中樹的概念

2.樹的各種結(jié)構(gòu)概念

2.1 節(jié)點(diǎn)的度

2.2 根節(jié)點(diǎn)/葉節(jié)點(diǎn)/分支節(jié)點(diǎn)

2.3 父節(jié)點(diǎn)/子節(jié)點(diǎn)

2.4祖先節(jié)點(diǎn)/子孫節(jié)點(diǎn)

?2.5兄弟節(jié)點(diǎn)

2.6樹的度

2.7節(jié)點(diǎn)的層次

2.8森林

?3. 如何用代碼表示一棵樹

3.1鏈?zhǔn)浇Y(jié)構(gòu)

3.1.1 樹節(jié)點(diǎn)的定義方式1（指針數(shù)組）

3.1.2?樹節(jié)點(diǎn)的定義方式2（左孩子右兄弟表示法）

3.2數(shù)組結(jié)構(gòu)

3.2.1 每個(gè)節(jié)點(diǎn)存父親下標(biāo)

3.2.2 完全二叉樹的數(shù)組表示法

---

1.什么是樹

1.1淺顯的理解樹

樹，其實(shí)就是我們現(xiàn)實(shí)中的樹（注意看有好多分支），但是現(xiàn)在這棵樹是一個(gè)數(shù)據(jù)結(jié)構(gòu)！

在數(shù)據(jù)結(jié)構(gòu)當(dāng)中，我們設(shè)計(jì)結(jié)構(gòu)的目的是為了存儲數(shù)據(jù)，我們所說的樹亦是一個(gè)能存數(shù)據(jù)的樹。或者更準(zhǔn)確的說，是一個(gè)一個(gè)的數(shù)據(jù)按照樹型結(jié)構(gòu)組織在了一起。那這是一種什么樣的數(shù)據(jù)結(jié)構(gòu)呢？

之前了解到的數(shù)據(jù)結(jié)構(gòu)，如順序表，鏈表等，他們都是線性的存儲結(jié)構(gòu)，即一個(gè)數(shù)據(jù)連接著下一個(gè)數(shù)據(jù)，在邏輯上上是呈現(xiàn)線性的。而樹這種數(shù)據(jù)結(jié)構(gòu)則不同，所有數(shù)據(jù)組織在一起的方式并不是一條單純的直線了，而是一個(gè)樹形。

1.2 數(shù)據(jù)結(jié)構(gòu)中樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它由一個(gè)一個(gè)的有限數(shù)量的節(jié)點(diǎn)組織形成，本質(zhì)上就是節(jié)點(diǎn)的集合。在實(shí)際coding當(dāng)中，一棵樹是一個(gè)倒掛的樹，即root樹根是在最上層，葉子在最底層。

所以實(shí)際上我們數(shù)據(jù)結(jié)構(gòu)中的樹是一棵倒掛的樹，根在最上面。

樹當(dāng)中，有一個(gè)特殊的節(jié)點(diǎn)，就是根節(jié)點(diǎn)，除了空樹，每一棵樹都有根節(jié)點(diǎn)，根節(jié)點(diǎn)是唯一的，根節(jié)點(diǎn)之上沒有其他的節(jié)點(diǎn)。

每一棵樹，都可以這樣劃分：根? 根的子樹1，子樹2，子樹3 ........ 子樹n（n是看根有多少棵直接子樹）。?

?每一棵子樹，也都是一棵樹。也可以分為子樹的根，子樹根 的 子樹1，子樹2......子樹n。

?按照這個(gè)思路，一棵樹由根 + 所有的的每一顆子樹，組成劃分的；根的每一棵子樹，也都是按 根 + 所有的每一顆子樹構(gòu)建的；所有的子樹的子樹，也都是按 根 +?所有的的每一顆子樹 方式組織的；所有的子樹的子樹的子樹（此處省去一萬字）。。。。。。

所以樹本質(zhì)上都是通過遞歸定義的。

2.樹的各種結(jié)構(gòu)概念

2.1 節(jié)點(diǎn)的度

節(jié)點(diǎn)的度，就是一個(gè)節(jié)點(diǎn)的子樹的個(gè)數(shù)，或者說，就是一個(gè)節(jié)點(diǎn)有幾個(gè)分叉。

如上面 1節(jié)點(diǎn)，它的度就是3（有3個(gè)子樹/分叉 2 3 4）；2節(jié)點(diǎn)，它的度是2（有2個(gè)子樹/分叉 5 6）；7節(jié)點(diǎn)，它的度是1（只有一個(gè)子樹/分叉）。

2.2 根節(jié)點(diǎn)/葉節(jié)點(diǎn)/分支節(jié)點(diǎn)

根節(jié)點(diǎn)：就是最開始的一個(gè)節(jié)點(diǎn)（如圖的 1節(jié)點(diǎn)），它是唯一的。從根開始找，這棵樹的所有節(jié)點(diǎn)都可以遍歷找到。所以只要找到了一棵樹的根，這棵樹就算是被我們所“掌控”。

葉子節(jié)點(diǎn)：度為0的節(jié)點(diǎn)，即往下沒有子樹/分支的節(jié)點(diǎn)。即我這個(gè)節(jié)點(diǎn)的下面就沒有任何東西了（空），我這個(gè)節(jié)點(diǎn)就是葉子節(jié)點(diǎn)。（如圖中的 5 9 10 8，是上圖中樹的葉子節(jié)點(diǎn)）。

分支節(jié)點(diǎn)：這是葉子節(jié)點(diǎn)的對立，即度不為0的節(jié)點(diǎn)，只要不是葉子節(jié)點(diǎn)，那你就是分支節(jié)點(diǎn)。

2.3 父節(jié)點(diǎn)/子節(jié)點(diǎn)

父節(jié)點(diǎn)：就是一個(gè)節(jié)點(diǎn)的父親。就是一個(gè)節(jié)點(diǎn)上面的那一個(gè)節(jié)點(diǎn)，如在下圖當(dāng)中，5的父節(jié)點(diǎn)是2，10的父節(jié)點(diǎn)是7，3的父親節(jié)點(diǎn)是1.。

這里需要著重強(qiáng)調(diào)：就像在現(xiàn)實(shí)當(dāng)中任何一個(gè)人都只有一個(gè)爹，任何一個(gè)節(jié)點(diǎn)，也都只有一個(gè)父節(jié)點(diǎn)。（除根節(jié)點(diǎn)，根節(jié)點(diǎn)沒有父親）

要找到任何一個(gè)節(jié)點(diǎn)，也只能通過父親節(jié)點(diǎn)找到。父節(jié)點(diǎn)，也只能由他的唯一的父親節(jié)點(diǎn)找到，所以其實(shí)在樹中，要找到任何一個(gè)節(jié)點(diǎn)都只有唯一的一條路徑。

相對于父節(jié)點(diǎn)，那父的兒子就是子節(jié)點(diǎn)，即父親往下可以直接找到的節(jié)點(diǎn)。就像現(xiàn)實(shí)當(dāng)中，一個(gè)爹，都可以有多個(gè)兒子，也可以有一個(gè)兒子，也可能沒有兒子，在樹當(dāng)中，任何一個(gè)節(jié)點(diǎn)，只要在我這個(gè)節(jié)點(diǎn)的下面能直接找到的節(jié)點(diǎn)，那這就是子節(jié)點(diǎn)。

如1的子節(jié)點(diǎn)，就是2 3 4節(jié)點(diǎn)；2的子節(jié)點(diǎn)，就是5 6節(jié)點(diǎn)；4的子節(jié)點(diǎn)，就只有?8節(jié)點(diǎn)。

2.4祖先節(jié)點(diǎn)/子孫節(jié)點(diǎn)

祖先節(jié)點(diǎn)：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)，都是祖先節(jié)點(diǎn)。類比現(xiàn)實(shí)，你爹是你的祖先，你爺爺是你的祖先，你太爺爺是你的祖先……你的太太太太太太太爺爺都是你的祖先。（當(dāng)然這里我們也可以知道，根節(jié)點(diǎn)一定是所有節(jié)點(diǎn)的祖先節(jié)點(diǎn)）

如6節(jié)點(diǎn)的祖先節(jié)點(diǎn)是2 1節(jié)點(diǎn)；如9節(jié)點(diǎn)的祖先節(jié)點(diǎn)是6 2 1節(jié)點(diǎn)；如8節(jié)點(diǎn)的祖先是4 1節(jié)點(diǎn)。

子孫節(jié)點(diǎn)：祖先是從根節(jié)點(diǎn)找到該節(jié)點(diǎn)路徑上的所有點(diǎn)，而子孫，其實(shí)就是我這個(gè)節(jié)點(diǎn)能被某個(gè)節(jié)點(diǎn)所找到！！！即只要，我這個(gè)節(jié)點(diǎn)只要能往下找到你，我就是祖先，你就是子孫。如2節(jié)點(diǎn)作為祖先節(jié)點(diǎn)，那5 6 9這三個(gè)節(jié)點(diǎn)就都是子孫節(jié)點(diǎn)。

?2.5兄弟節(jié)點(diǎn)

兄弟節(jié)點(diǎn)：（必須是親兄弟！！！）有同一個(gè)的父節(jié)點(diǎn)，我們才是兄弟節(jié)點(diǎn)！！！

如下圖當(dāng)中5和6才是兄弟節(jié)點(diǎn)，6和7就不是兄弟節(jié)點(diǎn)，7和8就不是兄弟節(jié)點(diǎn)。

2.6樹的度

是一棵樹中，所有節(jié)點(diǎn)的最大度，稱之為樹的度。就是所有的節(jié)點(diǎn)的度中，挑出其中最大的節(jié)點(diǎn)度。PS：最大的節(jié)點(diǎn)度，不一定是根節(jié)點(diǎn)的度，我們要求的是有最多分支的節(jié)點(diǎn)。

?如這棵樹，它的度就是3：即7這個(gè)節(jié)點(diǎn)的度，是所有節(jié)點(diǎn)當(dāng)中度最大的（3，其余節(jié)點(diǎn)的度都是2或1或0），所以這棵樹的度就是3。

2.7節(jié)點(diǎn)的層次

從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層。節(jié)點(diǎn)的層次也叫樹的高度/深度。

當(dāng)然也有些地方根是第0層，根的子節(jié)點(diǎn)為第1層，即上圖分為0 1 2 3層，這樣也說的過去。

不過我們還是推薦 1 2 3 4?（如上圖畫的那樣），這樣方便理解：

空樹是沒有根節(jié)點(diǎn)，如果我們算根節(jié)點(diǎn)為第1層，這樣空樹的高度我們就可以換定義為0了，更加符合我們的觀感！

2.8森林

有N（N>0）棵樹，即至少一棵 互不相交的樹 的集合稱為森林。

如并查集這個(gè)數(shù)據(jù)結(jié)構(gòu)就是森林（就是有多棵樹嘛）。

?3. 如何用代碼表示一棵樹

剛才我們只是從抽象圖上表征了樹，那落實(shí)到代碼當(dāng)中，一棵樹如何用代碼來表示呢?我們可以用鏈?zhǔn)浇Y(jié)構(gòu)來表示一棵樹，也可以用數(shù)組結(jié)構(gòu)來表示一棵樹。

3.1鏈?zhǔn)浇Y(jié)構(gòu)

要用鏈?zhǔn)浇Y(jié)構(gòu)來實(shí)現(xiàn)樹，我們就要首先定義出來一個(gè)節(jié)點(diǎn)類，因?yàn)槲覀円欢ㄊ?strong>把一個(gè)一個(gè)的節(jié)點(diǎn)鏈起來組成的一棵樹（當(dāng)然節(jié)點(diǎn)與節(jié)點(diǎn)之間的鏈接，我們是通過指針來實(shí)現(xiàn)的）。節(jié)點(diǎn)是組成樹的基礎(chǔ)。那如何定義節(jié)點(diǎn)類呢？

3.1.1 樹節(jié)點(diǎn)的定義方式1（指針數(shù)組）

我們節(jié)點(diǎn)TreeNode要存一個(gè)數(shù)據(jù)data，這個(gè)毋庸置疑，然后就是要存儲指針，即鏈接到子節(jié)點(diǎn)的鏈子。那這樣就有一個(gè)問題，我每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的數(shù)量是不一定的，要使用的鏈子（指針）數(shù)量也是不一定的，所以我們要存儲多個(gè)節(jié)點(diǎn)指針。

一種方法是讓每個(gè)節(jié)點(diǎn)存儲一個(gè)指針數(shù)組，這個(gè)指針數(shù)組可以是一個(gè)定長的。

struct TreeNode
{int data;struct TreeNode* *pSonNode[N];
};

但是這種情況是存在缺陷的，如果你知道了這個(gè)樹的度（即一個(gè)節(jié)點(diǎn)，最大所能有的分叉數(shù)量），或者你規(guī)定這個(gè)樹是固定有多少個(gè)叉的，那這個(gè)N是可以確定的，可是如果沒有給這個(gè)度，那N存多大就很難確定了：如果N給大了，那就會(huì)造成很多的空間浪費(fèi)。如果N給小了，有可能導(dǎo)致有的節(jié)點(diǎn)，所能鏈接到的節(jié)點(diǎn)數(shù)量受限。

所以我們通常是存一個(gè)可以動(dòng)態(tài)增長的數(shù)組指針，按需給相應(yīng)大小數(shù)量的指針。

struct TreeNode
{int data;vector<struct TreeNode*> pTreeSon;
};

上面的方法，在指定了這是幾叉樹 / 該樹的度確定，這兩種情況下，在節(jié)點(diǎn)中直接存儲指向孩子的指針，這的確是一種很好的表示樹的方法。但是現(xiàn)實(shí)中，樹的情況是很復(fù)雜的，對于度不確定的這種樹，我們不推崇上面這個(gè)方法，我們有一個(gè)也是很好的方法---左孩子右兄弟表示法。

3.1.2?樹節(jié)點(diǎn)的定義方式2（左孩子右兄弟表示法）

struct TreeNode
{int data;struct TreeNode* Left_FirstChild;struct TreeNode* Right_NextBrother;
};

每一個(gè)節(jié)點(diǎn)，只存，鏈接到 最左的孩子（即我的第一個(gè)孩子）的指針，以及鏈接到 右邊的兄弟（即我旁邊的那個(gè)親兄弟節(jié)點(diǎn)）的指針。

舉個(gè)例子：如下圖，2節(jié)點(diǎn)，我只存儲兩個(gè)指針：我的Left_FirstChild為指向最左邊的即第一個(gè)孩子5，我的Right_NextBrother為指向我右邊的即旁邊的親兄弟3。

再如下圖的6節(jié)點(diǎn)：我的Left_FirstChild，指向的是第一個(gè)孩子9。而我Right_NextBrother，旁邊右邊的第一個(gè)親兄弟，是空！這里注意哦，兄弟指代的是親兄弟哦！你只能說6和7是堂兄弟的關(guān)系。反正我7節(jié)點(diǎn)的右邊是沒有親兄弟的，所以Right_NextBrother存NULL。

那這樣存為什么能夠表示整棵樹呢？ 畫個(gè)圖你就明白了：比如我們要用這個(gè)左孩子右兄弟法表示下面這棵樹：

那么如果我們用左孩子右兄弟法，組織節(jié)點(diǎn)，組織成這棵樹：

你可以看到，這種方法其實(shí)是把每一個(gè)節(jié)點(diǎn)都建立了被鏈接關(guān)系，即我總是能通過某條路徑找到這個(gè)節(jié)點(diǎn)，我們可以根據(jù)左孩子右兄弟法這些安插的鏈子，找到所有節(jié)點(diǎn)。

（只要可以找到/遍歷到任何節(jié)點(diǎn)，那這就是一種成功的表示樹的方法）

例如要找H節(jié)點(diǎn)，我們可以通過A的左孩子找到B，然后通過B的右兄弟找到C，然后通過C的左孩子找到H節(jié)點(diǎn)；

再例如要找到G節(jié)點(diǎn)，我們可以通過A的左孩子找到B，然后通過B的左孩子找到E，然后通過E的右兄弟找到F，然后通過F的右兄弟找到G節(jié)點(diǎn)。.

這種方法，相比第一種方法，對于任意樹的構(gòu)建，是沒有空間浪費(fèi)的，而且可以全部遍歷找到，非常優(yōu)！！！

3.2數(shù)組結(jié)構(gòu)

沒錯(cuò)，我們用一個(gè)數(shù)組，也可以組織表示一棵樹哦！（后面寫并查集的時(shí)候，一個(gè)數(shù)組甚至能夠表示一個(gè)森林，也就是多棵樹）是不是很神奇！？下面我們具體看一下如何實(shí)現(xiàn)。

3.2.1 每個(gè)節(jié)點(diǎn)存父親下標(biāo)

我們每個(gè)節(jié)點(diǎn)，即每個(gè)節(jié)點(diǎn)的數(shù)據(jù)都存儲在一個(gè)數(shù)組的一個(gè)格子當(dāng)中，這樣每一個(gè)數(shù)據(jù)就都有了一個(gè)存儲下標(biāo)index，然后這個(gè)數(shù)組每個(gè)格子，不止存數(shù)據(jù)，還存儲著該數(shù)據(jù)節(jié)點(diǎn)的父親的所在下標(biāo)（根節(jié)點(diǎn)沒有父親，存-1）。這種方法也可以表示整棵樹，也即可以遍歷到/找到任意的一個(gè)節(jié)點(diǎn)。何出此言？

struct TreeNode
{int data;    //節(jié)點(diǎn)存儲的數(shù)據(jù)int parent_i;//我這個(gè)節(jié)點(diǎn)的父親的在數(shù)組的下標(biāo)
};

如果我們要找到任意一個(gè)節(jié)點(diǎn)，可以選擇遍歷這個(gè)數(shù)組，從而找到這個(gè)節(jié)點(diǎn)；然后如何找到這個(gè)從根到這個(gè)節(jié)點(diǎn)的路徑呢？其實(shí)我們可以通過這個(gè)數(shù)組每個(gè)格子里面存儲的父親的下標(biāo)，一直往父親跳，一直跳到根即可，記錄每個(gè)跳到的節(jié)點(diǎn)，其實(shí)這就是從根到該節(jié)點(diǎn)的路

徑。

如上面這棵樹，我們用數(shù)組存儲父親下標(biāo)法，就是這樣組織出這棵樹的：

?

3.2.2 完全二叉樹的數(shù)組表示法

完全二叉樹由于其特殊性，在數(shù)組中存儲表示可以也是非常方便的，而且也會(huì)有很多的性質(zhì)使用，這個(gè)我們會(huì)放在后面一篇博客，關(guān)于數(shù)據(jù)結(jié)構(gòu)堆的實(shí)現(xiàn)上具體講解（想了解的話就關(guān)注我吧~），這種方法來表示完全二叉樹也是非常優(yōu)秀，非常的勁爆！！！