柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu)：二叉樹(shù)與樹(shù)

http://yzkb.51969.com/

一 樹(shù)的基本概念：

1.樹(shù)的形狀：

2.樹(shù)的定義：

樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是n(n >= 0)個(gè)結(jié)點(diǎn)的有限集。當(dāng)n = 0時(shí)，稱為空樹(shù)。在任意一棵非空樹(shù)中應(yīng)滿足：

2.1 有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)。 2.2 當(dāng)n > 1時(shí)，其余結(jié)點(diǎn)可分為m(m > 0)個(gè)互不相交的有限集T1 ……Tm，其中每個(gè)集合本身又是一棵樹(shù)，并且稱為根的子樹(shù)。 顯然，樹(shù)的定義是遞歸的，即在樹(shù)的定義中又用到其自身，樹(shù)是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。樹(shù)作為一種邏輯結(jié)構(gòu)，同時(shí)也是一種分層結(jié)構(gòu)，具有以下兩點(diǎn)特點(diǎn)：

2.3 樹(shù)的根結(jié)點(diǎn)沒(méi)有前驅(qū)，除根結(jié)點(diǎn)外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)。 2.4 樹(shù)中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼。

3.樹(shù)中相關(guān)的關(guān)鍵詞概念：

3.1 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱為該節(jié)點(diǎn)的度；如上圖：A的為6

3.2 路徑：樹(shù)的路徑是指從根節(jié)點(diǎn)到樹(shù)內(nèi)特定節(jié)點(diǎn)遍歷的節(jié)點(diǎn)序列

3.3 根：樹(shù)頂端的節(jié)點(diǎn)稱為根。一棵樹(shù)只有一個(gè)根，如果要把一個(gè)節(jié)點(diǎn)和邊的集合稱為樹(shù)，那么從根到其他任何一個(gè)節(jié)點(diǎn)都必須有且只有一條路徑。A是根節(jié)點(diǎn)

3.4 父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；如上圖：A是B的父節(jié)點(diǎn)

3.5 子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；如上圖：B是A的子節(jié)點(diǎn)

3.6 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn) 如上圖：I與J就是兄弟

3.7 堂兄弟節(jié)點(diǎn)：不是相同父親的節(jié)點(diǎn)且在同一層而和相鄰的稱堂兄弟節(jié)點(diǎn) 如上圖：H與I就是堂兄弟

3.8 葉節(jié)點(diǎn)：度為0的節(jié)點(diǎn)就是葉節(jié)點(diǎn)或者說(shuō)沒(méi)有孩子的節(jié)點(diǎn)?如上圖：P和Q

3.9 分支節(jié)點(diǎn)：度不為0的點(diǎn)。列如：B、C、D、都是分支節(jié)點(diǎn)。

3.10 子樹(shù)：每個(gè)節(jié)點(diǎn)都可以作為子樹(shù)的根，它和它所有的子節(jié)點(diǎn)、子節(jié)點(diǎn)的子節(jié)點(diǎn)等都包含在子樹(shù)中。

3.11 節(jié)點(diǎn)的層次：從根開(kāi)始定義，根為第一層，根的子節(jié)點(diǎn)為第二層，以此類推。

3.12 深度 \ 高度：樹(shù)中節(jié)點(diǎn)的最大層。如圖就是4。

3.13 節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)的所經(jīng)過(guò)分支上的所有節(jié)點(diǎn)，A就是所有節(jié)點(diǎn)的祖先。

3.14 深林：互不相交的樹(shù)的集合被稱為深林。

3.15 子孫：以某節(jié)點(diǎn)為根的子樹(shù)的子樹(shù)中任一節(jié)點(diǎn)都被稱為該節(jié)點(diǎn)的子孫。列如所有節(jié)點(diǎn)都是A的子孫

4.樹(shù)的性質(zhì)：

4.1 樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)之和加1 4.2 度為m的樹(shù)中第i層上至多有m^(i-1)個(gè)結(jié)點(diǎn)(i >= 1) 4.3 高度為h的m叉樹(shù)至多有(m^h - 1)/(m - 1)個(gè)結(jié)點(diǎn) 4.4 具有n個(gè)結(jié)點(diǎn)的m二叉的最小高度為[logm(n(m - 1) + 1)]

二 二叉樹(shù)的基本概念：

1.二叉樹(shù)的形狀：

2.二叉樹(shù)的定義：

二叉樹(shù)是另一種樹(shù)形結(jié)構(gòu)，其特點(diǎn)時(shí)每個(gè)結(jié)點(diǎn)至多只能有兩棵樹(shù)(即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn))，并且二叉樹(shù)的子樹(shù)也有左右之分，其次序不能任意顛倒。

與樹(shù)相似，二叉樹(shù)也有遞歸的形式定義。二叉樹(shù)是n(n >= 0)個(gè)結(jié)點(diǎn)的有限集合：

2.1 或者為空二叉樹(shù)，即n = 0. 2.2 或者由一個(gè)根結(jié)點(diǎn)和兩個(gè)互不相交的被稱為根的左子樹(shù)和右子樹(shù)組合。左子樹(shù)和右子樹(shù)又是分別? 是一棵二叉樹(shù) 二叉樹(shù)是有序樹(shù)，若將其左右子樹(shù)顛倒，則成為另一顆不同的二叉樹(shù)。即使樹(shù)中結(jié)點(diǎn)只有一顆子樹(shù)，也要區(qū)分它是左子樹(shù)還是右子樹(shù)。

3.二叉樹(shù)的性質(zhì)：

3.1 非空二叉樹(shù)上的葉子節(jié)點(diǎn)數(shù)等于度為2的結(jié)點(diǎn)數(shù)加1，n0 = n1 + 1 3.2 非空二叉樹(shù)上第k層上至多有2^(k-1)個(gè)結(jié)點(diǎn)(k >= 1) 3.3 高度為h二叉樹(shù)至多有2^(h - 1)個(gè)結(jié)點(diǎn)(h >= 1) 3.4 對(duì)完全二叉樹(shù)按從上到下、左到右的順序依次編號(hào)1，2……n 3.5 具有n個(gè)(n > 0)結(jié)點(diǎn)的完全二叉樹(shù)的高度為[log2(n + 1)]或[log2n] + 1

三 特殊的二叉樹(shù)：

1.滿二叉樹(shù)(FBT)：

1.1 所有非葉節(jié)點(diǎn)都擁有兩個(gè)子節(jié)點(diǎn)。

1.2 最深層的葉子節(jié)點(diǎn)從左到右依次排列，沒(méi)有空缺。

1.3 深度為 h 的完全二叉樹(shù)，具有 2^h - 1 個(gè)節(jié)點(diǎn)。

2.完全二叉樹(shù)(CBT)：

2.1 每一層都擁有最大數(shù)量的節(jié)點(diǎn)。

2.2 深度為 k 的滿二叉樹(shù)，具有 2^k - 1 個(gè)節(jié)點(diǎn)。

2.3 非葉節(jié)點(diǎn)都擁有兩個(gè)子節(jié)點(diǎn)，最底層可能存在一些空缺。

3.滿二叉樹(shù)和完全二叉樹(shù)的形狀：

四 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：

1.順序存儲(chǔ)結(jié)構(gòu)：

二叉樹(shù)的順序存儲(chǔ)是指使用一維數(shù)組來(lái)存儲(chǔ)二叉樹(shù)中的節(jié)點(diǎn)，并將節(jié)點(diǎn)的邏輯結(jié)構(gòu)映射到數(shù)組的物理結(jié)構(gòu)中。這種存儲(chǔ)方式通常用于空間受限的場(chǎng)景，因?yàn)橹恍枰粋€(gè)數(shù)組即可存儲(chǔ)整個(gè)二叉樹(shù)。

?2.為什么二叉樹(shù)的順序存儲(chǔ)只能應(yīng)用于完全二叉樹(shù)？

2.1 節(jié)點(diǎn)索引與子節(jié)點(diǎn)關(guān)系： 在順序存儲(chǔ)中，節(jié)點(diǎn)的索引與它的子節(jié)點(diǎn)之間存在著固定的關(guān)系。例如，對(duì)于一個(gè)節(jié)點(diǎn) i，它的左子節(jié)點(diǎn)的索引為 2i，右子節(jié)點(diǎn)的索引為 2i + 1。這種關(guān)系依賴于完全二叉樹(shù)的結(jié)構(gòu)特點(diǎn)，即每個(gè)非葉節(jié)點(diǎn)都擁有兩個(gè)子節(jié)點(diǎn)。

2.2 空間利用率： 順序存儲(chǔ)旨在節(jié)省空間，因此需要盡可能地利用數(shù)組空間。在完全二叉樹(shù)中，所有非葉節(jié)點(diǎn)都擁有兩個(gè)子節(jié)點(diǎn)，因此數(shù)組空間可以得到充分利用。而對(duì)于非完全二叉樹(shù)，可能存在一些節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)或沒(méi)有子節(jié)點(diǎn)，導(dǎo)致數(shù)組空間浪費(fèi)。

2.3 空缺節(jié)點(diǎn)處理： 在非完全二叉樹(shù)中，可能存在空缺節(jié)點(diǎn)，即沒(méi)有實(shí)際內(nèi)容的節(jié)點(diǎn)。順序存儲(chǔ)難以有效地處理這些空缺節(jié)點(diǎn)，因?yàn)樗鼈儠?huì)破壞節(jié)點(diǎn)索引與子節(jié)點(diǎn)關(guān)系的約定。

2.4 算法復(fù)雜度： 對(duì)于非完全二叉樹(shù)，順序存儲(chǔ)需要額外的機(jī)制來(lái)處理空缺節(jié)點(diǎn)，這會(huì)導(dǎo)致算法復(fù)雜度的增加，降低效率。

3.完全二叉樹(shù)的順序存儲(chǔ)與非完全二叉樹(shù)存儲(chǔ)形狀的區(qū)別：

2.堆(Heap)：

堆的定義：

堆（Heap）是一種特殊的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，它滿足堆性質(zhì)：允許高效地檢索和刪除最大/最小元素。堆通常用于實(shí)現(xiàn)優(yōu)先隊(duì)列。

堆的性質(zhì)：

在堆中，每個(gè)非葉節(jié)點(diǎn)的值都應(yīng)該大于或等于其子節(jié)點(diǎn)的值（最大堆）或者小于或等于其子節(jié)點(diǎn)的值（最小堆）。

堆通常使用完全二叉樹(shù)來(lái)實(shí)現(xiàn)，因?yàn)橥耆鏄?shù)結(jié)構(gòu)可以保證堆性質(zhì)的有效性和空間利用率。

在最大堆中，根節(jié)點(diǎn)是堆中最大的元素；在最小堆中，根節(jié)點(diǎn)是堆中最小的元素。

堆的種類:

根據(jù)堆性質(zhì)的不同，堆可以分為兩種類型：

最大堆： 在最大堆中，每個(gè)非葉節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值。根節(jié)點(diǎn)是堆中最大的元素。

最小堆： 在最小堆中，每個(gè)非葉節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值。根節(jié)點(diǎn)是堆中最小的元素。

最大堆與最小堆的形狀：

3.順序存儲(chǔ)代碼實(shí)現(xiàn)：

堆的存儲(chǔ)結(jié)構(gòu)：

typedef int HPDataType;

typedef struct Heap

{

HPDataType* a;

int size;

int capacity;

}HP;

堆的所有接口：

//初始化、銷毀

void HPInit(HP* php);

void HPDestroy(HP* php);

// 插入

void HPPush(HP* php, HPDataType x);

//獲取堆頂元素、堆的有效數(shù)據(jù)個(gè)數(shù)

HPDataType HPTop(HP* php);

HPDataType HPsize(HP* php);

// 刪除堆頂?shù)臄?shù)據(jù)

void HPPop(HP* php);

//判斷堆是否為空

bool HPEmpty(HP* php);

堆的初始化：

void HPInit(HP* php)

{

assert(php);

php->a = NULL;

php->capacity = php->size = 0;

}

輸出：

堆的銷毀：

void HPDestroy(HP* php)

{

assert(php);

free(php->a);

php->a = NULL;

php->capacity = php->size = 0;

}

輸出：

插入：

void HPPush(HP* php, HPDataType x)

{

assert(php);

//擴(kuò)容數(shù)組

if (php->capacity == php->size)

{

HPDataType Newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;

HPDataType* Ptmp = (HPDataType*)realloc(php->a , sizeof(HPDataType) * Newcapacity);

if (Ptmp == NULL)

{

perror("calloc error");

exit(-1);

}

php->a = Ptmp;

php->capacity = Newcapacity;

}

php->a[php->size] = x;

php->size++;

//向上調(diào)整

AdjustUp(php->a, php->size - 1); //因?yàn)閜hp->size最后是指向最后數(shù)據(jù)的后面一個(gè)所以傳要減一

}

輸出：

向上調(diào)整(建小堆)：

void AdjustUp(HPDataType* a , HPDataType child)

{

HPDataType parents = (child - 1) / 2;//找父節(jié)點(diǎn)

while (child > 0)//當(dāng)child走到首節(jié)點(diǎn)時(shí)就會(huì)停止循環(huán)

{

if (a[child] < a[parents])

{

Swap(&a[child] , &a[parents]);//交換數(shù)據(jù)

child = parents;

parents = (parents - 1) / 2;//改變父親指針的指向，讓父親指針往上指

}

else

{

break;

}

}

}

交換父子數(shù)據(jù)：

void Swap(HPDataType* x , HPDataType* y)

{

int tmp = *x;

*x = *y;

*y = tmp;

}

當(dāng)堆(小堆)要插入新數(shù)據(jù)時(shí)在邏輯層面上是在堆的最右下方插入一個(gè)值而在物理層面上是直接在添加在數(shù)組的后面，而我們插入一個(gè)值必然會(huì)改變小堆(大堆)的性質(zhì)所以需要向上調(diào)整以此來(lái)保持，所以當(dāng)插入32時(shí)首先需要找到父親節(jié)點(diǎn)然后再跟它比下大小如果新插入的節(jié)點(diǎn)比它小那就需要調(diào)整，把數(shù)據(jù)互相交換然后讓孩子指向父親然后再讓父親指向父親同時(shí)要查看數(shù)據(jù)的大小，當(dāng)child小于0時(shí)就可以退出了

獲取堆頂(最大或最小)的元素：

HPDataType HPTop(HP* php)

{

assert(php);

return php->a[0];

}

輸出：

獲取堆的數(shù)據(jù)個(gè)數(shù)：

HPDataType HPsize(HP* php)

{

assert(php);

return php->size;

}

輸出：

刪除堆頂?shù)臄?shù)據(jù)：

void HPPop(HP* php)

{

assert(php);

assert(php->size > 0);

Swap(&php->a[0] , &php->a[php->size-1]);//先首尾交換

php->size--;//刪除尾部數(shù)據(jù)(實(shí)際上是隱藏交換之后的尾部數(shù)據(jù))

AdjustDown(php->a , php->size ,0);//向下調(diào)整

}

輸出：

雖然50 32還是顯示但是我們靠自減已經(jīng)將他們?cè)谶壿媽用娼o刪除了但是再物理層面上還是帶顯示的

向下調(diào)整(逐個(gè)刪除每個(gè)數(shù)據(jù))：

void AdjustDown(HPDataType* a , HPDataType n , HPDataType parents)

{

HPDataType child = (parents * 2) + 1;

while (child < n)

{

//假設(shè)child指向左孩子

if (child + 1 < n && a[child] > a[child + 1])//選出左右孩子誰(shuí)大誰(shuí)小

{

child++;//如果右孩子小那就讓child指針自增指向右孩指就行

}

if (a[child] < a[parents])

{

Swap(&a[child], &a[parents]);

child = parents;

child = (parents * 2) + 1;

}

else

{

break;

}

}

}

判斷堆是否為空：

bool HPEmpty(HP* php)

{

assert(php);

if (php->size == 0)

{

return false;

}

return true;

//return php->size == 0;

}

輸出：

打印堆：

4.鏈表存儲(chǔ)結(jié)構(gòu)：

鏈?zhǔn)蕉鏄?shù)是一種非線性數(shù)據(jù)結(jié)構(gòu)，它使用鏈接而不是連續(xù)的內(nèi)存布局來(lái)表示元素之間的層次關(guān)系。與將節(jié)點(diǎn)存儲(chǔ)在數(shù)組中的傳統(tǒng)二叉樹(shù)不同，鏈?zhǔn)蕉鏄?shù)使用指針來(lái)連接節(jié)點(diǎn)，從而為節(jié)點(diǎn)分配和動(dòng)態(tài)內(nèi)存管理提供了靈活性。

二叉樹(shù)的前序，中序，后序遍歷:

二叉樹(shù)遍歷是指對(duì)二叉樹(shù)中的每個(gè)節(jié)點(diǎn)恰好訪問(wèn)一次的系統(tǒng)過(guò)程。它是探索和操作二叉樹(shù)的基本技術(shù)。三種常見(jiàn)的遍歷方法是前序、中序、后序。

前序遍歷：

在前序遍歷中，首先訪問(wèn)根結(jié)點(diǎn)，然后訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)?如上圖：

遍歷順序：

首先訪問(wèn)根節(jié)點(diǎn) 1 ，然后再訪問(wèn)根節(jié)點(diǎn) 1 的左子樹(shù) 2 最后再訪問(wèn)以 2 為根節(jié)點(diǎn)的左子樹(shù) 4，接下來(lái)就是訪問(wèn)以 4 為根節(jié)點(diǎn)的左子樹(shù) NULL 與 右子樹(shù) NULL?

1 2 4 NULL NULL

當(dāng)右子樹(shù)是NULL那就需要向上返回 ，先是返回到 4 但因 4 已經(jīng)遍歷過(guò)了所以需要再次向上返回，返回到 2 但因 2 已經(jīng)遍歷過(guò)了但以它為根節(jié)點(diǎn)的右子樹(shù)并沒(méi)有被遍歷過(guò)所以就先訪問(wèn) 以 2 為根節(jié)點(diǎn)的右子樹(shù) 5 ，最后訪問(wèn)以5為根的左子樹(shù) NULL 和右子樹(shù) NULL

5 NULL NULL

這里需要直接返回到 1 這里就不過(guò)多解釋了思想和上面一樣，遍歷以 1 為根節(jié)點(diǎn)的右子樹(shù) 3 然后再遍歷以 3 為根節(jié)點(diǎn)的左子樹(shù) 6 然后再訪問(wèn)以 3 為根節(jié)點(diǎn)的左子樹(shù) NULL 和 右子樹(shù) NULL，接下來(lái)需要返回到 以 3 為根節(jié)點(diǎn)的右子樹(shù) 7最后訪問(wèn)以 7 為根節(jié)點(diǎn)的左子樹(shù) NULL 和 右子樹(shù) NULL

3 6 NULL NULL 7 NULL NULL

它的完整順序就是 1 2 4 NULL NULL? 5 NULL NULL 3 6 NULL NULL 7 NULL NULL

中序遍歷：

在中序遍歷中，首先訪問(wèn)左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)?如上圖：

遍歷順序：

首先是訪問(wèn) 根節(jié)點(diǎn)的左子樹(shù) 2 然后再訪問(wèn)以 2 為根節(jié)點(diǎn)的左子樹(shù) 4最后再訪問(wèn)以 4 為根節(jié)點(diǎn)的左子樹(shù) NULL當(dāng)碰到NULL就可以返回到根節(jié)點(diǎn) 4 最后再訪問(wèn)以 4 為根節(jié)點(diǎn)的右子樹(shù) NULL

?NULL 4 NULL

訪問(wèn)完以 4 為根節(jié)點(diǎn)的左樹(shù)右樹(shù)那就需要繼續(xù)向上返回到根節(jié)點(diǎn) 2 因只遍歷過(guò)以根節(jié)點(diǎn)的 2 的左子樹(shù)但右子樹(shù)并沒(méi)有遍歷所以現(xiàn)在需要遍歷右子樹(shù) ，先遍歷以根節(jié)點(diǎn) 5 的左子樹(shù) NULL然后再遍歷根節(jié)點(diǎn) 5 最后需遍歷以根節(jié)點(diǎn) 5 的右子樹(shù) NULL

2 NULL 5 NULL

當(dāng)以根節(jié)點(diǎn) 1 的左子樹(shù)全部遍歷完所以就需要遍歷根節(jié)點(diǎn) 1 了? 那么遍歷完左子樹(shù) 根節(jié)點(diǎn)那就需要遍歷右子樹(shù)了。先訪問(wèn)以根節(jié)點(diǎn) 1 的右子樹(shù) 3然后再訪問(wèn)以根節(jié)點(diǎn) 3 的左子樹(shù) 6 然后再遍歷以根節(jié)點(diǎn) 6 的左子樹(shù) NULL當(dāng)碰到 NULL 那這個(gè)程序就需要返回到根節(jié)點(diǎn) 6 然后向右訪問(wèn) NULL碰到NULL那就需要再次返回到根節(jié)點(diǎn) 3 ，以3的左子樹(shù)已經(jīng)全部訪問(wèn)完所以就需要向右訪問(wèn)以此循環(huán)

1?NULL 6 NULL 3?NULL?7 NULL

它的完整順序就是 NULL 4 NULL 2 NULL 5 NULL 1?NULL 6 NULL 3?NULL?7 NULL

后序遍歷：

在后序遍歷中，首先訪問(wèn)左子樹(shù)，然后訪問(wèn)右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)?如上圖：

遍歷順序：

首先是訪問(wèn) 根節(jié)點(diǎn)的左子樹(shù) 2 然后再訪問(wèn)以 2 為根節(jié)點(diǎn)的左子樹(shù) 4最后再訪問(wèn)以 4 為根節(jié)點(diǎn)的左子樹(shù) NULL當(dāng)碰到NULL就可以返回到根節(jié)點(diǎn) 4 但是根節(jié)點(diǎn)是最后才訪問(wèn)的所以現(xiàn)在不能訪問(wèn) 4 而是先訪問(wèn)以 4 為根節(jié)點(diǎn)的右子樹(shù) NULL最后再訪問(wèn)以 4 為根節(jié)點(diǎn)

NULL NULL 4

訪問(wèn)完根節(jié)點(diǎn) 4 之后就需要向上返回到以 2?為根節(jié)點(diǎn)但是后序的訪問(wèn)順序是先訪問(wèn)左 右最后再訪問(wèn)根節(jié)點(diǎn)的 所以我們需要向以 2 為根節(jié)點(diǎn)的右遍歷左子樹(shù)與右子樹(shù) NULL最后再訪問(wèn)根節(jié)點(diǎn) 5。

NULL NULL 5

訪問(wèn)完以 2 為根節(jié)點(diǎn)的左子樹(shù)與右子樹(shù)那么就可以訪問(wèn)根節(jié)點(diǎn)了但是根節(jié)點(diǎn) 2 也是也是以 1 為根節(jié)點(diǎn)的左子樹(shù)，現(xiàn)在以 1 為左子樹(shù)已經(jīng)訪問(wèn)完那就可以訪問(wèn)以 1 為根節(jié)點(diǎn)的右子樹(shù)了所以我們現(xiàn)在向右遍歷 直到遍歷到以 6 為根節(jié)點(diǎn)的左子樹(shù) NULL 然后就需開(kāi)始返回到 根節(jié)點(diǎn) 6 然后再向右子樹(shù) NULL 最后再訪問(wèn) 根節(jié)點(diǎn) 6

NULL NULL 6

訪問(wèn)根節(jié)點(diǎn) 6 之后就和以 根節(jié)點(diǎn) 1 為左子樹(shù)的 2 一樣這里我就不重新贅述了 最后訪問(wèn)完以 1 為右子樹(shù)就需要訪問(wèn) 根節(jié)點(diǎn) 1 了

NULL NULL 7 3 1

它的完整順序就是 NULL NULL 4 NULL NULL 5 2 NULL NULL 6 NULL NULL 7 3 1

4.鏈?zhǔn)酱鎯?chǔ)代碼實(shí)現(xiàn)：

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：

typedef int BTDataType;

typedef struct BinaryTree

{

struct BinaryTree* left;//左子樹(shù)

struct BinaryTree* right;//右子樹(shù)

BTDataType data;

}BT;

鏈?zhǔn)酱鎯?chǔ)所有接口：

//二叉樹(shù)的初始化

BT* CreatTreeNode(int x);

//二叉樹(shù)的銷毀

void DestroyBinaryTree(BT* root);

//前序遍歷、中序遍歷、后序遍歷

void PrevOrder(BT* root);

void InOrder(BT* root);

void PostOrder(BT* root);

//獲取二叉樹(shù)相關(guān)個(gè)數(shù)

int BinaryTreeSize(BT* root);

//獲取葉子節(jié)點(diǎn)相關(guān)個(gè)數(shù)

int BinaryTreeleafSize(BT* root);

//獲取樹(shù)的高度

int BinaryTreeHeight(BT* root);

//計(jì)算第K層節(jié)點(diǎn)個(gè)數(shù)

int BinaryTreeKcount(BT* root, BTDataType k);

鏈?zhǔn)酱鎯?chǔ)初始化：

BT* CreatTreeNode(int x)

{

BT* Newnode = (BT*)malloc(sizeof(BT));

if (Newnode == NULL)

{

perror("malloc error");

return NULL;

}

Newnode->data = x;

Newnode->left = NULL;

Newnode->right = NULL;

return Newnode;

}

輸出：

鏈?zhǔn)酱鎯?chǔ)銷毀：

void DestroyBinaryTree(BT* root)

{

if (root == NULL)

{

return;

}

DestroyBinaryTree(root->left);

DestroyBinaryTree(root->right);

free(root);

}

輸出：

前序遍歷：

void PrevOrder(BT* root)

{

if (root == NULL)

{

printf("NULL ");

return;

}

printf("%d ", root->data);

PrevOrder(root->left);

PrevOrder(root->right);

}

輸出：

中續(xù)遍歷：

void InOrder(BT* root)

{

if (root == NULL)

{

printf("NULL ");

return;

}

InOrder(root->left);

printf("%d ", root->data);

InOrder(root->right);

}

輸出：

后續(xù)遍歷：

void PostOrder(BT* root)

{

if (root == NULL)

{

printf("NULL ");

return;

}

PostOrder(root->left);

PostOrder(root->right);

printf("%d ", root->data);

}

輸出：

獲取二叉樹(shù)相關(guān)個(gè)數(shù)：

int BinaryTreeSize(BT* root)

{

if (root == NULL)

{

return 0;

}

return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);

}

輸出：

獲取葉子節(jié)點(diǎn)相關(guān)個(gè)數(shù)：

int BinaryTreeleafSize(BT* root)

{

if (root->left == NULL && root->right == NULL)

{

return 1;

}

if (root == NULL)

{

return 0;

}

else

{

return BinaryTreeleafSize(root->left) + BinaryTreeleafSize(root->right);

}

}

輸出：

獲取樹(shù)的高度：

int BinaryTreeHeight(BT* root)

{

if (root == NULL)

{

return 0;

}

BTDataType Tleft = BinaryTreeHeight(root->left);

BTDataType Tright = BinaryTreeHeight(root->right);

return Tleft > Tright ? Tleft + 1 : Tright + 1;

}

輸出：

計(jì)算第K層節(jié)點(diǎn)個(gè)數(shù)：

int BinaryTreeKcount(BT* root, BTDataType k)

{

if (root == NULL || k < 1)

{

return 0;

}

if (k == 1)

{

return 1;

}

return BinaryTreeKcount(root->left, k - 1) + BinaryTreeKcount(root->right, k - 1);

}

輸出：

五 樹(shù)與二叉樹(shù)的區(qū)別：

1. 子節(jié)點(diǎn)數(shù)量

樹(shù)：一個(gè)節(jié)點(diǎn)可以擁有任意多個(gè)子節(jié)點(diǎn)。二叉樹(shù)：一個(gè)節(jié)點(diǎn)最多只能擁有兩個(gè)子節(jié)點(diǎn)，通常稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。

2. 子節(jié)點(diǎn)的順序

樹(shù)：樹(shù)的子節(jié)點(diǎn)可以任意排列，沒(méi)有左右之分。二叉樹(shù)：二叉樹(shù)的子節(jié)點(diǎn)必須嚴(yán)格按照左右順序排列。

3. 應(yīng)用場(chǎng)景

樹(shù)：樹(shù)常用于表示具有層次關(guān)系的數(shù)據(jù)結(jié)構(gòu)，例如文件目錄樹(shù)、組織機(jī)構(gòu)圖等。二叉樹(shù)：二叉樹(shù)由于其結(jié)構(gòu)簡(jiǎn)單、易于實(shí)現(xiàn)，在計(jì)算機(jī)科學(xué)中有著廣泛的應(yīng)用，例如二叉查找樹(shù)、二叉堆、表達(dá)式樹(shù)等。

4.形象比喻

樹(shù)可以想象成一棵樹(shù)木，每個(gè)節(jié)點(diǎn)代表一個(gè)樹(shù)枝，子節(jié)點(diǎn)代表樹(shù)枝的分叉。樹(shù)枝可以任意分叉，沒(méi)有左右之分。二叉樹(shù)可以想象成一棵只有左右兩個(gè)分支的樹(shù)，每個(gè)節(jié)點(diǎn)代表一個(gè)樹(shù)枝，左子節(jié)點(diǎn)代表樹(shù)枝的左邊分支，右子節(jié)點(diǎn)代表樹(shù)枝的右邊分支。

六 總結(jié)：

樹(shù)和二叉樹(shù)都是重要的數(shù)據(jù)結(jié)構(gòu)，但它們?cè)谧庸?jié)點(diǎn)數(shù)量、子節(jié)點(diǎn)順序和應(yīng)用場(chǎng)景等方面存在著差異。選擇哪種數(shù)據(jù)結(jié)構(gòu)取決于具體的應(yīng)用需求。

柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu)：二叉樹(shù)與樹(shù)

http://yzkb.51969.com/

相關(guān)文章