專欄介紹：

哈嘍大家好，我是野生的編程萌新，首先感謝大家的觀看。數(shù)據(jù)結(jié)構(gòu)的學習者大多有這樣的想法：數(shù)據(jù)結(jié)構(gòu)很重要，一定要學好，但數(shù)據(jù)結(jié)構(gòu)比較抽象，有些算法理解起來很困難，學的很累。我想讓大家知道的是：數(shù)據(jù)結(jié)構(gòu)非常有趣，很多算法是智慧的結(jié)晶，我希望大家在學習數(shù)據(jù)結(jié)構(gòu)的過程是一種愉悅的心情感受。因此我開創(chuàng)了《數(shù)據(jù)結(jié)構(gòu)》專欄，在這里我將把數(shù)據(jù)結(jié)構(gòu)內(nèi)容以有趣易懂的方式展現(xiàn)給大家。

1.樹

1.1樹的定義

?之前我們一直談的都是一對一的線性結(jié)構(gòu)，可現(xiàn)實中，還是有很多一對多的情況需要處理，所以我們需要研究這種一對多的數(shù)據(jù)結(jié)構(gòu)—“樹”，考慮它的各種特性，來解決我們在編程中遇到的相關(guān)問題。樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個節(jié)點組成的一個具有層次關(guān)系的集合，把它叫做樹是因為它看起來像是一棵倒掛的樹，也就是說它根是向上的，葉子是向下的。如下圖：

?n=0時被稱為空樹，在任意一棵非空樹中：1.有且僅有一個特定的根節(jié)點? 2.當n>1時，其余節(jié)點可以分為m個互不相交的有限集，其中每一個集合本身又都是一個樹，被稱為子樹。如下圖：

?上面就是兩個子樹的簡單例子，4、5組成的樹是以2為根節(jié)點的子樹，6、7組成的樹是以3為結(jié)點的子樹，對于樹的定義還需要強調(diào)兩點：

1. n>0時根節(jié)點是唯一的，不可能存在多個根節(jié)點，千萬不要和現(xiàn)實中的大樹混在一起，現(xiàn)實中的樹有很多的根須，那時真實的樹，數(shù)據(jù)結(jié)構(gòu)中的樹只有一個節(jié)點！
2. m>0時，子樹的個數(shù)沒有限制，但是他們一定是不相交互的，即同一層次的各個節(jié)點之間不相互。像下面展示的結(jié)構(gòu)就不符合樹的定義，因為他們之間有交互。

1.2樹的相關(guān)概念?

?我們一會就用下面這張圖來展開介紹樹的相關(guān)概念。

• 根節(jié)點：根節(jié)點是樹結(jié)構(gòu)中的第一個節(jié)點，也是整個樹的起點。它是樹的頂部節(jié)點。在上面的圖中A是這棵樹的根節(jié)點。一棵樹只能有一個根節(jié)點。其他節(jié)點可以通過根節(jié)點進行訪問和遍歷。根節(jié)點是樹的分支點，它可以有多個子節(jié)點。子節(jié)點通過邊或鏈接與根節(jié)點相連，形成了樹的層次結(jié)構(gòu)。
• 雙親結(jié)點/父節(jié)點：父節(jié)點是樹結(jié)構(gòu)中一個節(jié)點的上一級節(jié)點。每個節(jié)點都可以有一個父節(jié)點，除了根節(jié)點，因為根節(jié)點沒有父節(jié)點。在上圖中C就是H的父節(jié)點。父節(jié)點直接連接到其子節(jié)點，形成了樹的層次結(jié)構(gòu)。父節(jié)點是子節(jié)點的直接訪問入口。通過父節(jié)點，可以找到子節(jié)點，進而訪問和操作子節(jié)點。父節(jié)點可以有多個子節(jié)點。這使得樹結(jié)構(gòu)能夠表示復雜的分支關(guān)系，每個父節(jié)點可以連接到不同的子節(jié)點。在上圖中F就有3個子節(jié)點節(jié)點。
• 兄弟節(jié)點：兄弟節(jié)點是樹結(jié)構(gòu)中同一層級的節(jié)點之間的關(guān)系。它們的父節(jié)點是相同的，即它們有相同的父節(jié)點。兄弟節(jié)點在樹的結(jié)構(gòu)中是相鄰的，它們在同一層級的位置是相鄰的。在上圖中K、L、M就互為兄弟節(jié)點。
• 祖先節(jié)點：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點，在上圖中A是所有結(jié)點的祖先節(jié)點。
• 子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫，在上圖中所有節(jié)點都是A節(jié)點的子孫。
• 節(jié)點的度：節(jié)點的度是指該節(jié)點擁有的子節(jié)點的數(shù)量。在上圖中A節(jié)點的度為6.
• 葉節(jié)點/終端節(jié)點：葉節(jié)點是指沒有子節(jié)點的節(jié)點，即度為0的節(jié)點，在上圖中B就是一個葉節(jié)點。
• 分支節(jié)點：度不為0的節(jié)點，除根節(jié)點之外，分支節(jié)點也叫做內(nèi)部節(jié)點，在上圖中C就是一個分支節(jié)點。
• 樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度，上面這張圖中樹的度為6.

1.3樹的存儲結(jié)構(gòu)

說到存儲結(jié)構(gòu)，我們就會想到之前提到的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，之前我們都是一對一的結(jié)構(gòu)，現(xiàn)在變成樹這樣一對多的結(jié)構(gòu)該怎么辦呢？在這里我們要充分利用順序存儲和鏈式存儲的特點，來實現(xiàn)對樹的存儲結(jié)構(gòu)的表示。我們這里要介紹三種不同的表示方法：雙親表示法、孩子表示法、孩子兄弟表示法。

1.3.1雙親表示法

我們有的人可能因為種種原因沒有孩子，但無論誰都不可能是從石頭縫里蹦出來的。樹這種結(jié)構(gòu)也不例外，除了根節(jié)點之外，其余每個節(jié)點，不一定有子節(jié)點，但一定有且僅有一個雙親結(jié)點。我們假設(shè)以一組連續(xù)的空間存儲樹的節(jié)點，同時每個節(jié)點中，還要設(shè)置一個指針指向雙親結(jié)點的位置。也就是說，每個節(jié)點除了要知道自己是誰之外，還要知道雙親在哪里，它的結(jié)構(gòu)如下：

其中，data是數(shù)據(jù)域，存放節(jié)點的數(shù)據(jù)信息，parent是指針域，存儲該節(jié)點對應的雙親在數(shù)組中的下標?。以下是雙親表示法的節(jié)點結(jié)構(gòu)的定義代碼：

#define MAX_TREE_SIZE 100
typedef int TNDataType   //樹結(jié)點的數(shù)據(jù)類型，暫定為整型
typedef struct TreeNode
{TNDataType data;int parent;
}TNode;
typedef struct Tree
{TNode nodes[MAX_TREE_SIZE];   //節(jié)點數(shù)組int r,n;               //根節(jié)點的位置和節(jié)點數(shù)
}Tree;

有了上面的結(jié)構(gòu)定義我們就可以來實現(xiàn)雙親表示法了。由于根節(jié)點是沒有雙親的，所以我們約定根節(jié)點的位置域為-1，這就意味著，我們所有的節(jié)點都存在它的雙親的位置。下面圖中的樹結(jié)構(gòu)可以用雙親表示法來表示：

因為按照數(shù)組那種連續(xù)存儲結(jié)構(gòu)畫出來的話，圖片橫向太長不方便看，所以這里我用一個表格來表示方便觀看，又簡單明了：

下標	data	parent
0	A	-1
1	B	0
2	C	0
3	D	0
4	E	1
5	F	2
6	G	2
7	H	3
8	I	5
9	J	5
10	K	5

這樣的存儲結(jié)構(gòu)，我們可以根據(jù)節(jié)點的parent指針很容易的找到它的雙親結(jié)點，所用的時間復雜度為O(1)，直到parent為-1時，表示找到了樹結(jié)點的根?？扇绻覀円拦?jié)點的孩子是什么的話，需要遍歷整個數(shù)組才行，那我們能否改進一下呢？why not?我們增加一個指針域存放第一個孩子（一般取最左邊的子節(jié)點）在數(shù)組中的下標，這樣就很容易得到節(jié)點的孩子，如果沒有子節(jié)點的話，我們就把這個指針域設(shè)為-1。如下表表示：

下標	data	parent	firstchild
0	A	-1	1
1	B	0	4
2	C	0	5
3	D	0	7
4	E	1	-1
5	F	2	8
6	G	2	-1
7	H	3	-1
8	I	5	-1
9	J	5	-1
10	K	5	-1

這樣對于有0或1個子節(jié)點的的雙親結(jié)點來說，這樣的結(jié)構(gòu)是為了解決要找子節(jié)點的問題，甚至是有多個子節(jié)點也能解決，知道了第一個子節(jié)點是誰，剩下的子節(jié)點也就一目了然了。就像上面表格中A的第一個子節(jié)點下標是1，即B節(jié)點的位置，而B第一個子節(jié)點的下標為4，所以在[1,4)區(qū)間中的所有整數(shù)在數(shù)組中所對應的下標元素就是A的子節(jié)點。

這時候又有一個新問題了，我們很關(guān)注兄節(jié)點之間的關(guān)系，雙親表示法無法體驗出這種關(guān)系，那我們該怎么辦呢？這時候我們只需要在雙親表示法的基礎(chǔ)上增加一個指針用來指向子結(jié)點中最右側(cè)的節(jié)點，即右兄弟節(jié)點，也就是說每一個節(jié)點如果它存在右兄弟，就存放右兄弟的下標，如果右兄弟不在就存放-1，如下表表示：

下標	data	parent	rightbrother
0	A	-1	-1
1	B	0	2
2	C	0	3
3	D	0	-1
4	E	1	-1
5	F	2	6
6	G	2	-1
7	H	3	-1
8	I	5	9
9	J	5	10
10	K	5	-1

存儲結(jié)構(gòu)的設(shè)計是一個非常靈活的過程，一個存儲結(jié)構(gòu)設(shè)計的是否合理，取決于基于該存儲結(jié)構(gòu)的運算是否合適、是否方便，時間復雜度好不好等。不是越多越好，有需要時再設(shè)計相應的結(jié)構(gòu)，復雜的結(jié)構(gòu)意味著更多的時間和空間的開銷，簡單的設(shè)計對應著快速的查找與刪除，我們要根據(jù)實際情況進行取舍。

1.3.2孩子表示法

我們換一種思路：由于樹中每個節(jié)點可能有多個子樹，可以考慮使用多重鏈表，即每個節(jié)點有多個指針域，其中每個指針域指向一棵子樹的根節(jié)點，我們把這種方法叫做多重鏈表表示法。不過樹的每個節(jié)點度都是不一樣的，所以可以設(shè)計兩種解決方案。

1.3.2.1方案一

一種方案就是指針域的個數(shù)等于樹的度，前面我們提到了，樹的度是各個節(jié)點度的最大值。其結(jié)構(gòu)如下表示：

其中，data就是數(shù)據(jù)域，child1~childn是指針域，用來指向該節(jié)點的孩子節(jié)點。在雙親表示法我們提到的那個樹用這種方法實現(xiàn)如下圖：

這種方法對于樹中各個節(jié)點的度相差很大，顯然是浪費空間的，因為有很多節(jié)點，它的指針域是空的。如果樹的各個節(jié)點的度相差很小的話，那就意味著開辟的空間被充分利用了，這是存儲結(jié)構(gòu)的缺點反而成了優(yōu)點。既然很多指針域為空，為什么不按需求分配空間呢？于是我們有了第二種方案。

1.3.2.2方案二?

第二種方案每個結(jié)點的指針域等于該節(jié)點的度，我們專門取一個位置來存儲節(jié)點指針域的個數(shù)，其結(jié)構(gòu)如下：

其中，data為數(shù)據(jù)域，degree為節(jié)點的度，也就是存儲該節(jié)點的子節(jié)點的個數(shù)，child1~childn為指針域，指向該節(jié)點的各個子結(jié)點。這種方法實現(xiàn)如下圖：

?這種方法克服了浪費空間的缺點，對空間的利用率很高了，但是由于各個節(jié)點的鏈表是不相同的結(jié)構(gòu)，加上要維護節(jié)點的度的數(shù)值，在運算上就會帶來時間上的損耗，能否有更好的方法，既可以減少空指針的浪費又能使結(jié)點的結(jié)構(gòu)相同。仔細觀察，我們?yōu)榱艘闅v整棵樹，把每個節(jié)點放在一個順序存儲結(jié)構(gòu)的數(shù)組中是合理的，但每個結(jié)點的孩子有多少是不確定的，所以我們在對每個結(jié)點的孩子建立一個單鏈表體現(xiàn)他們的關(guān)系。

這就是我們要講的孩子表示法。具體辦法是：把每個節(jié)點的子節(jié)點排列起來，以單鏈表作為存儲結(jié)構(gòu)，則n個節(jié)點有n個子鏈表，如果是葉子節(jié)點則此單鏈表為空，然后n個頭指針又組成一個線性表，采用順序存儲結(jié)構(gòu)，存放在一個一維數(shù)組中。如下圖：

為此我們設(shè)計兩個節(jié)點結(jié)構(gòu)，一個是子鏈表的子節(jié)點，如下表表示：

?

?其中，child是數(shù)據(jù)域，用于存儲某個節(jié)點在表頭數(shù)組中的下標；next是指針域，用來存儲指向某節(jié)點的下一個子節(jié)點的指針。另一個是表頭數(shù)組的表頭結(jié)點，如下表表示：

其中，data是數(shù)據(jù)域，存儲某節(jié)點的數(shù)據(jù)信息；firstchild是頭指針域，存放該節(jié)點的子鏈表的頭指針。以下是我們的孩子表示法的結(jié)構(gòu)定義代碼：

#define MAX_TREE_SIZE 100
typedef int TNDatatype
typedef struct ChildNode
{int child;struct ChildNode* next;
}CNode;
typedef struct TreeNode
{TNDataType data;CNode* firstchild;
}TNode;
typedef struct Tree
{TNode nodes[MAX_TREE_SIZE];int r,n;
}Tree;

?這樣的結(jié)構(gòu)對于我們要查找某個節(jié)點的某個孩子，或者某個節(jié)點的兄弟，只需要查找這個節(jié)點的子鏈表即可。對于遍歷整棵樹也是非常方便的，對頭結(jié)點的數(shù)組循環(huán)即可。

1.3.3左孩子右兄弟表示法

剛才我們分別從雙親的角度和孩子的角度研究樹的存儲結(jié)構(gòu)，如果我們從樹節(jié)點的兄弟角度考慮會如何呢？當然對于樹這樣的層級結(jié)構(gòu)來說，之研究節(jié)點的兄弟是不行的，我們觀察后發(fā)現(xiàn)：任何一顆樹，他的結(jié)點的的第一個孩子如果i存在就是唯一的，同理它的右兄弟如果存在也是唯一的。因此，我們設(shè)置兩個指針，分別指向該節(jié)點的第一個孩子和它的右兄弟。這個方法我們成為左孩子右兄弟表示法。這個表示法在我們學習二叉樹時常用到，是一個非常重要的知識點。節(jié)點結(jié)構(gòu)如下：

其中，data是數(shù)據(jù)域，firstchild為指針域，存放該節(jié)點的第子節(jié)點的存儲地址，rightbrother也是指針域，存儲該節(jié)點的右兄弟節(jié)點的存儲地址，結(jié)構(gòu)定義代碼如下：

?

typedef struct TreeNode
{TNDataType data;struct TreeNode* firstchild;struct TreeNode* rightbrother;
}TNode;

對于上面的樹來說，這種實現(xiàn)方法示意圖如下：

這種表示法，給查找某個節(jié)點的某個孩子帶來了方便，只需要通過firstchild找到此節(jié)點的第一個孩子，然后再通過第一個子節(jié)點的rightbrother找到他的兄弟，按照這樣一直下去，直到找到具體的孩子。其實這個表示法的最大好處就是把他從一棵復雜的樹變成了一棵二叉樹。在下一篇再詳細介紹二叉樹。?