????文中代碼源文件已上傳：數(shù)據(jù)結(jié)構(gòu)源碼 ?<-上一篇 初級數(shù)據(jù)結(jié)構(gòu)（四）——隊列 ? ? ? ?|????????NULL 下一篇->

1、樹結(jié)構(gòu)（Tree）

1.1、樹結(jié)構(gòu)的特點

? ? ? ? 自然界中的樹由根部開始向上生長，隨機長出分支，分支之上又可長出分支，層層遞進，直至長出葉子則此分支結(jié)束。

????????數(shù)據(jù)結(jié)構(gòu)中“樹”的概念便是借鑒大自然中的樹，將下圖垂直鏡像翻轉(zhuǎn)便是如此，只是在畫結(jié)構(gòu)圖時往往更習(xí)慣由上向下畫。它從根節(jié)點開始不斷長出分支，直至終端。與自然中的樹不同點在于，隨著數(shù)據(jù)后續(xù)插入，樹結(jié)構(gòu)的葉子節(jié)點也可能變?yōu)榉种Ч?jié)點。

? ? ? ? 尤其需要注意，不同分支上的節(jié)點不可互相交織。下圖中紅色線條連接到其他分支的節(jié)點，這就不屬于樹結(jié)構(gòu)：

? ? ? ? 總之，樹是若干個節(jié)點的有限集，有且僅有一個根節(jié)點。樹的分支數(shù)量可以任意多，也可以不包含分支僅有一個根節(jié)點甚至沒有節(jié)點（沒有節(jié)點的樹稱為空樹）。不同分支的節(jié)點互不相交。

1.2、常用名詞

? ? ? ? ?在了解樹結(jié)構(gòu)特點的同時，為了后續(xù)使用該結(jié)構(gòu)時方便描述，還應(yīng)了解幾個名詞。

? ? ? ? 節(jié)點（ Node ）：樹中的每一個元素稱為節(jié)點，上圖中每個圓圈都代表一個節(jié)點；

????????根節(jié)點（ Root ）：最初的節(jié)點稱為根節(jié)點，如上圖中的 A ；

? ? ? ? 子樹（ Subtree ）：每個節(jié)點除開自身，將下一級節(jié)點當(dāng)作新的根節(jié)點，從新的根節(jié)點往下所有節(jié)點的集合稱為該節(jié)點的子樹。上圖中 B 及往后的節(jié)點是 A 的子樹， F 又是 B 的子樹（所以樹是遞歸結(jié)構(gòu)）；

? ? ? ? 分支節(jié)點（ Branch ）：能夠延申出其他節(jié)點的節(jié)點（度不為 0 的節(jié)點）都稱作分支節(jié)點，如上圖中紅色及藍色標(biāo)識的節(jié)點都屬于分支節(jié)點；

? ? ? ? 終端節(jié)點、葉子節(jié)點（ Leaf ）：不包含任何分支節(jié)點的節(jié)點（度為 0 的節(jié)點）稱為終端節(jié)點或者葉子節(jié)點。上圖中綠色標(biāo)識的節(jié)點屬于葉子節(jié)點；

? ? ? ? 度（ Degree ）：一個節(jié)點的分支數(shù)量叫作該節(jié)點的度，如上圖 E 有兩個分支 K 和 L ，所以 E 的度是 2 。一棵樹中所有節(jié)點的度的最大值就是這棵樹的度，上圖中度最大的節(jié)點是 J ， 有 4 個度，所以這棵樹的度也是 4 ；

? ? ? ? 層次（ Level ）：從樹或者子樹的頂層到最底層的順序進行排序。在這個順序中，每個節(jié)點都被視為位于樹的某個層次上。最頂上可以視為第 0 層，也可以視作第 1 層。

? ? ? ? 深度、高度（Depth）：最大層次稱為這棵樹的深度或者高度。如圖中的樹從根節(jié)點開始向下，最多可經(jīng) A、D、J、O、S 這 5 個節(jié)點（ 5 個層次），所以這棵樹的深度為 5 ；

? ? ? ? 父節(jié)點、雙親節(jié)點（ Parent ）：一個節(jié)點的上一級節(jié)點稱為該節(jié)點的父節(jié)點或者雙親節(jié)點。如圖中 E 是 K 的父節(jié)點，A 是 B 的父節(jié)點；

? ? ? ? 子節(jié)點（ Child?）：一個節(jié)點的下一級節(jié)點稱為該節(jié)點的子節(jié)點。圖中的 O、P、Q、R 都是 J 的子節(jié)點；

? ? ? ? 兄弟節(jié)點（ Sibling ）：與某個節(jié)點有同一個父節(jié)點的節(jié)點稱為兄弟節(jié)點。如圖 E、F 都是 G 的兄弟節(jié)點；

? ? ? ? 祖先節(jié)點（ Ancestry ）：某個節(jié)點上數(shù)若干級直到根節(jié)點，經(jīng)過的這些節(jié)點都稱為祖先節(jié)點。圖中 A、C、H 都是 M 或者 N 的祖先節(jié)點；
? ? ? ? 子孫節(jié)點（ Descendant ）：一個節(jié)點往下的所有節(jié)點都稱為該節(jié)點的子孫節(jié)點。如圖中 I、J、O、P、Q、R、S 都是 D 的子孫節(jié)點；

? ? ? ? 堂兄弟節(jié)點（ Cousin ）：與某個節(jié)點同一層次除了自身和兄弟節(jié)點外其他所有節(jié)點稱為該節(jié)點的堂兄弟節(jié)點。如圖中 H、I、J 都是 E、F、G 的堂兄弟節(jié)點；

? ? ? ? 森林（ Forest ）：若干顆互不相交的樹稱為森林。圖中剔除 A 節(jié)點后， B、C、D 子樹則構(gòu)成森林；

? ? ? ? 有序樹（ Ordered Tree ）：一棵樹中各子樹按照一定規(guī)律排序不可互換，則稱為有序樹。如圖中如果將這棵樹的 A、B、C …… 當(dāng)作一種順序，那么可視為有序樹；

? ? ? ? 無序樹（ Unordered Tree ）：有序樹之外的樹都稱作無序樹。

1.3、樹的存儲方式

????????如上圖的樹結(jié)構(gòu)，如果要在代碼中定義其結(jié)構(gòu)體，常規(guī)能想到的是除了定義一個儲存數(shù)據(jù)的成員變量外，定義若干個子節(jié)點指針。而由于子節(jié)點的數(shù)量是不確定的，因此將其定義為數(shù)組。

typedef int DATATYPE;
typedef struct Node
{DATATYPE data;            //存儲數(shù)據(jù)size_t childCount;        //子節(jié)點個數(shù)size_t capacity;          //已開辟空間大小struct Node* child[0];    //子節(jié)點指針數(shù)組
}Node;

? ? ? ? 若要找到圖中 1-2-2 節(jié)點則執(zhí)行：

root->child[0]->child[1]->child[1];

? ? ? ? 但這對于有序樹這種不可隨意交換節(jié)點位置的結(jié)構(gòu)還好，如果是無序樹，而且在經(jīng)常需要交換節(jié)點的情況下，?頻繁挪動數(shù)組元素顯得十分不靈活。因此，還有一種儲存方式，每個節(jié)點僅儲存第一個子節(jié)點和其下一個兄弟節(jié)點的指針。

? ? ? ? 在結(jié)構(gòu)體創(chuàng)建上也顯得簡單，而且無需每次添加數(shù)據(jù)都檢查空間：

typedef int DATATYPE;
typedef struct Node
{DATATYPE data;struct Node* sibling;struct Node* child;
}Node;

????????同樣是找到 1-2-2 節(jié)點：

root->child->child->sibling->child->sibling;

? ? ? ? 看似更為復(fù)雜，但整個結(jié)構(gòu)在增刪數(shù)據(jù)或者交換數(shù)據(jù)的操作上跟之前的結(jié)構(gòu)完全不是一個量級。具體過程這里就不展開贅述，實際上就是對鏈表和順序表在增刪數(shù)據(jù)或者交換數(shù)據(jù)操作上的區(qū)別。

2、二叉樹（ Binary Tree ）

2.1、節(jié)點基本形態(tài)

????????二叉樹是一種特殊的樹，每個節(jié)點的子節(jié)點不超過 2 個，它的度最大為 2? 。此外，二叉樹是有序樹。一般其節(jié)點的結(jié)構(gòu)體類型如下（二叉節(jié)點）：

typedef int DATATYPE;
typedef struct Node
{DATATYPE data;struct Node* left;struct Node* right;
}

????????還有一種三叉節(jié)點的結(jié)構(gòu)體定義方式，即將父節(jié)點的地址也包含在結(jié)構(gòu)體內(nèi)：

typedef int DATATYPE;
typedef struct Node
{DATATYPE data;struct Node* parent;struct Node* left;struct Node* right;
}

? ? ? ? 不論是二叉節(jié)點還是三叉節(jié)點，二叉樹均只存在以下五種基本形態(tài)：?

????????其中，由于二叉樹是有序樹，所以左分支形態(tài)和右分支形態(tài)不是同一種結(jié)構(gòu)，代碼的表現(xiàn)上也完全不同：

//空
root = NULL;
//無分支
root->left = NULL;
root->right = NULL;
//左分支
root->left = &nodeLeft;
root->right = NULL;
//右分支
root->left = NULL;
root->right = &nodeRight;
//雙分支
root->left = &nodeLeft;
root->right = &nodeRight;

2.2、二叉樹的特殊形態(tài)

2.2.1、斜二叉樹

? ? ? ? 所有節(jié)點的左或者右節(jié)點全為空的二叉樹稱為斜二叉樹。斜二叉樹每一層有且只有一個節(jié)點，節(jié)點數(shù)等于樹的深度。如圖。

? ? ? ? 斜二叉樹可看作是一種非環(huán)狀單鏈表，使用上也與單鏈表無差異。

2.2.2、完全二叉樹

? ? ? ? 如果二叉樹的深度為 n ，根節(jié)點處于第 0 層，除了最底層節(jié)點，其余每一層中第 L 層節(jié)點個數(shù)? 都滿足??，且底層最右側(cè)節(jié)點滿足其父節(jié)點的左子節(jié)點不為空，其堂兄弟節(jié)點的父節(jié)點度都為 2 ，則這類二叉樹稱為完全二叉樹。如下圖。

? ? ? ? 上面的描述可能有點過于抽象，可以觀察圖片，然后用另一種方式概括：

? ? ? ? ????????a、完全二叉樹的葉子節(jié)點僅存在該二叉樹的最底層和次底層；

? ? ? ? ????????b、最底層的葉子節(jié)點無空隙地緊密排列在左邊部分，右邊部分可以為空；

? ? ? ? ????????c、次底層的葉子節(jié)點無空隙地緊密排列在這一層右側(cè)；

? ? ? ? ????????d、次底層節(jié)點的度為 1 時，該節(jié)點沒有右子節(jié)點。

? ? ? ? ?在同樣節(jié)點數(shù)的二叉樹中，不存在其他形態(tài)的二叉樹深度小于完全二叉樹。

2.2.3、滿二叉樹

????????滿二叉樹是一種特殊的完全二叉樹，如圖。

? ? ? ? 滿二叉樹的葉子節(jié)點只能出現(xiàn)在最下層，每個非葉子節(jié)點的分支節(jié)點度都為 2 。在所有同深度的二叉樹中，滿二叉樹的節(jié)點最多。

2.3、二叉樹規(guī)律

2.3.1、節(jié)點數(shù)規(guī)律

????????二叉樹的葉子節(jié)點數(shù)量總是比度為 2 的節(jié)點數(shù)多 1 個。

? ? ? ? 根據(jù)上圖可知，葉子節(jié)點數(shù)量增加總是伴隨著度為 2 的節(jié)點數(shù)增加，而起初只有根節(jié)點時，葉子節(jié)點數(shù)為 1 ，度為 2 的節(jié)點數(shù)為 0 。因此無論如何增加節(jié)點，葉子節(jié)點數(shù)總是比度為 2 的節(jié)點數(shù)多 1 個。

2.3.2、完全二叉樹標(biāo)號規(guī)律

? ? ? ? 將完全二叉樹節(jié)點如下圖從?1 開始自左向右自上向下編號：

? ? ? ? ?由于整型運算 1 / 2 = 0 ，因此會發(fā)現(xiàn)完全二叉樹父子間的編號關(guān)系如下列代碼：

parent = child / 2;
leftChild = parent * 2;
rightChild = parent * 2 + 1;

? ? ? ? ?而如果從 0 開始編號：

?????????則滿足以下代碼：

parent = (child - 1) / 2;
leftChild = parent * 2 + 1;
rightChild = parent * 2 + 2;

? ? ? ? 這一特性特別重要，在下一篇關(guān)于堆的內(nèi)容中會用到。

2.3.3、完全二叉樹深度

? ? ? ? 已知完全二叉樹節(jié)點數(shù)為 n ，其深度為??。

????????根據(jù)以下代碼可以計算出完全二叉樹的深度：

#include <math.h>
#include <stdio.h>int main()
{int nodeCount;scanf("%d", &nodeCount);int depth = (int)(log(nodeCount) / log(2)) + 1;printf("Depth = %d\n", depth);return 0;
}