樹概念及結構

樹的概念

樹的相關概念

樹的表示

樹在實際中的運用（表示檔案系統的目錄樹結構）

二叉樹概念及結構

概念

現實中的二叉樹

特殊的二叉樹

二叉樹的性質

二叉樹的存盤結構

二叉樹的順序結構及實作

二叉樹的順序結構

堆的概念及結構

堆的實作

堆的初始化

堆的銷毀

堆的列印

堆的插入

堆的洗掉

堆的判空

堆的資料個數

取堆頂資料

堆的應用

堆排序

TOP-K問題

二叉樹鏈式結構的實作

前置說明

二叉樹的遍歷

前序、中序以及后序遍歷

層序遍歷

節點個數以及高度等

判斷二叉樹是否是完全二叉樹

二叉樹銷毀

樹概念及結構

樹的概念

樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫

做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，

有一個特殊的結點，稱為根結點，根節點沒有前驅結點，
除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集Ti(1<= i<= m)又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼，
因此，樹是遞回定義的，

注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構

樹的相關概念

節點的度：一個節點含有的子樹的個數稱為該節點的度；如上圖：A的為6

葉節點或終端節點：度為0的節點稱為葉節點；如上圖：B、C、H、I...等節點為葉節點

非終端節點或分支節點：度不為0的節點；如上圖：D、E、F、G...等節點為分支節點

雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點；如上圖：A是B的父節點

孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；如上圖：B是A的孩子節點

兄弟節點：具有相同父節點的節點互稱為兄弟節點；如上圖：B、C是兄弟節點

樹的度：一棵樹中，最大的節點的度稱為樹的度；如上圖：樹的度為6

節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；

樹的高度或深度：樹中節點的最大層次；如上圖：樹的高度為4

堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點

節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先

子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫

森林：由m（m>0）棵互不相交的樹的集合稱為森林；

樹的表示

樹結構相對線性表就比較復雜了，要存盤表示起來就比較麻煩了，既然保存值域，也要保存結點和結點之間的關系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等，

我們這里就簡單的了解其中最常用的孩子兄弟表示法，

typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // 第一個孩子結點
    struct Node* _pNextBrother; // 指向其下一個兄弟結點
    DataType _data; // 結點中的資料域
};

即這樣表示：

樹在實際中的運用（表示檔案系統的目錄樹結構）

二叉樹概念及結構

概念

一棵二叉樹是結點的一個有限集合，該集合:
1. 或者為空
2. 由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成

從上圖可以看出：

二叉樹不存在度大于2的結點
二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

注意：對于任意的二叉樹都是由以下幾種情況復合而成的：

現實中的二叉樹

特殊的二叉樹

1. 滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是結點總數是 2^k-1，則它就是滿二叉樹，

2. 完全二叉樹：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 要注意的是滿二叉樹是一種特殊的完全二叉樹，

二叉樹的性質

1. 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有 2^(i-1)個結點.
2. 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是2^h-1 .
3. 對任何一棵二叉樹, 如果度為0其葉結點個數為 , 度為2的分支結點個數為 ,則有 n0＝ n2＋1
4. 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h= . (ps：是log以2為底，n+1為對數)
5. 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的陣列順序對所有節點從0開始編號，則對于序號為i的結點有：

若i>0，i位置節點的雙親序號：(i-1)/2；i=0，i為根節點編號，無雙親節點
若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子
若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子

練習題：

1. 某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（）
A 不存在這樣的二叉樹
B 200
C 198
D 199 提示：n0 = n2+1
2.下列資料結構中，不適合采用順序存盤結構的是（ A）
A 非完全二叉樹
B 堆
C 佇列
D 堆疊
3.在具有 2n 個結點的完全二叉樹中，葉子結點個數為（）
A n
B n+1
C n-1
D n/2
4.一棵完全二叉樹的節點數位為531個，那么這棵樹的高度為（）
A 11
B 10
C 8
D 12
5.一個具有767個節點的完全二叉樹，其葉子節點個數為（）
A 383
B 384
C 385
D 386
答案：
1.B
2.A
3.A
4.B
5.B

二叉樹的存盤結構

二叉樹一般可以使用兩種結構存盤，一種順序結構，一種鏈式結構，

1. 順序存盤
順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，

而現實中使用中只有堆才會使用陣列來存盤，關于堆我們后面的章節會專門講解，

二叉樹順序存盤在物理上是一個陣列，在邏輯上是一顆二叉樹，

2. 鏈式存盤
二叉樹的鏈式存盤結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系，

通常的方法是鏈表中每個結點由三個域組成，資料域和左右指標域，左右指標分別用來給出該結點左孩子和右孩子所在的鏈結點的存盤地址，

鏈式結構又分為二叉鏈和三叉鏈，當前我們學習中一般都是二叉鏈，后面學到高階資料結構如紅黑樹等會用到三叉鏈，

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft; // 指向當前節點左孩子
    struct BinTreeNode* _pRight; // 指向當前節點右孩子
    BTDataType _data; // 當前節點值域
}

// 三叉鏈
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向當前節點的雙親
    struct BinTreeNode* _pLeft; // 指向當前節點左孩子
    struct BinTreeNode* _pRight; // 指向當前節點右孩子
    BTDataType _data; // 當前節點值域
}；

二叉樹的順序結構及實作

二叉樹的順序結構

普通的二叉樹是不適合用陣列來存盤的，因為可能會存在大量的空間浪費，

而完全二叉樹更適合使用順序結構存盤，

現實中我們通常把堆(一種二叉樹)使用順序結構的陣列來存盤，需要注意的是這里的堆和作業系統虛擬行程地址空間中的堆是兩回事，一個是資料結構，一個是作業系統中管理記憶體的一塊區域分段，

堆的概念及結構

如果有一個關鍵碼的集合K = { ，，，…， }，把它的所有元素按完全二叉樹的順序存盤方式存盤
在一個一維陣列中，并滿足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，則稱為小堆(或大堆)，

將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆，

堆的性質：

堆中某個節點的值總是不大于或不小于其父節點的值；
堆總是一棵完全二叉樹，

大堆：

小堆：

練習：

1.下列關鍵字序列為堆的是：（）
A 100,60,70,50,32,65
B 60,70,65,50,32,100
C 65,100,70,32,50,60
D 70,65,100,32,50,60
E 32,50,100,70,65,60
F 50,100,70,65,60,32
2.已知小根堆為8,15,10,21,34,16,12，洗掉關鍵字 8 之后需重建堆，在此程序中，關鍵字之間的比較次
數是（），
A 1
B 2
C 3
D 4
3.一組記錄排序碼為(5 11 7 2 3 17),則利用堆排序方法建立的初始堆為
A(11 5 7 2 3 17)
B(11 5 7 2 17 3)
C(17 11 7 2 3 5)
D(17 11 7 5 3 2)
E(17 7 11 3 5 2)
F(17 7 11 3 2 5)
4.最小堆[0,3,2,5,7,4,6,8],在洗掉堆頂元素0之后，其結果是（）
A[3，2，5，7，4，6，8]
B[2，3，5，7，4，6，8]
C[2，3，4，5，7，8，6]
D[2，3，4，5，6，7，8]

答案：

1.A
2.C
3.C
4.C

堆的實作

堆的實作基于順序表，所以一些地方與順序表類似，所以就不再重點講解，

這里以實作小堆為例，

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;//避免空間不夠，使用動態順序表
	int size;
	int capacity;
}HP;



//初始化堆
void HeapInit(HP* hp);

//銷毀堆
void HeapDestroy(HP* hp);

//列印堆
void HeapPrint(HP* hp);

//堆的插入
void HeapPush(HP* hp, HPDataType x);

//堆的洗掉
void HeapPop(HP* hp);

//向上調整
void AdjustUp(int* a, int size);

//向下調整
void AdjustDown(int* a, int size, int parent);
void Swap(int* a, int* b);

//堆的判空
bool HeapEmpty(HP* hp);

// 堆的資料個數
int HeapSize(HP* hp);

//取堆頂的資料
int HeapTop(HP* hp);

堆的初始化

void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

堆的銷毀

void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->capacity = hp->size = 0;
}

堆的列印

void HeapPrint(HP* hp)
{
	assert(hp);
	int i = 0;
	for (i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

堆的插入

首先插入資料就必須要檢查空間是否足夠，不夠需要擴容，

其次堆與順序表不同的是，將資料插入到到末尾之后，為了使堆的結構保持不變需要將堆中的元素調整，

代碼如下：

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		int* tmp = (int*)realloc(hp->a ,sizeof(int) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}

	hp->a[hp->size] = x;
	hp->size++;

	AdjustUp(hp->a, hp->size - 1);
}

void AdjustUp(int* a, int size)//引數為陣列地址，需要調整下標位置
{
	assert(a);
	int child = size;//記錄孩子位置
	int parent = (child - 1) / 2;//記錄父親位置
	while (child > 0)//調整到只剩一個根節點或者不再小于父親為止
	{
		if (a[child] < a[parent])
		{
            //交換
			Swap(a + child, a + parent);
            //迭代
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}


void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

堆的洗掉

洗掉元素時不能隨意位置洗掉，只能洗掉堆頂，

但又與順序表頭刪不同，洗掉堆頂后如果將后面的資料向左移動，可能整個堆的結構全部會被破壞掉，

所以這里我們采用的方法是：

將堆頂元素和最后一個元素交換，
洗掉掉最后一個元素，
將堆頂資料向下調整，

void HeapPop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));//保證堆不為空
	Swap(hp->a, hp->a + hp->size - 1);//交換首尾
	hp->size--;//洗掉末尾
	AdjustDown(hp->a, hp->size, 0);//向下調整
}


void AdjustDown(int* a, int size, int parent)//引數為陣列地址，陣列大小，調整位置
{
	assert(a);
	int child = parent * 2 + 1;//記錄孩子位置
	while (child < size)//調整結束條件為調整到末尾或者不再大于孩子
	{
		if (child + 1 < size && a[child + 1] < a[child])//如果有孩子存在且右孩子<左孩子
		{
			child++;//記錄較小孩子的位置
		}

		if (a[child] < a[parent])
		{
			Swap(a + child, a + parent);//交換
			parent = child;//迭代
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

堆的判空

bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

堆的資料個數

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

取堆頂資料

int HeapTop(HP* hp)
{
	assert(hp);
	return hp->a[0];
}

堆的應用

堆排序

堆排序即利用堆的思想來進行排序，總共分為兩個步驟：
1. 建堆

升序：建大堆
降序：建小堆

2. 利用堆洗掉思想來進行排序
建堆和堆洗掉中都用到了向下調整，因此掌握了向下調整，就可以完成堆排序，

這里以升序為例：

首先應該建一個大堆，不能直接使用堆來實作，

可以將需要排序的陣列看作是一個堆，但需要將陣列結構變成堆，

我們可以從堆從下往上的第二行最右邊開始依次向下調整直到調整到堆頂，這樣就可以將陣列調整成一個堆，且如果建立的是大堆，堆頂元素為最大值，

然后按照堆刪的思想將堆頂和堆底的資料交換，但不同的是這里不洗掉最后一個元素，

這樣最大元素就在最后一個位置，然后從堆頂向下調整到倒數第二個元素，這樣次大的元素就在堆頂，重復上述步驟直到只剩堆頂時停止，

如圖：

代碼如下：

void HeapSort(int* arr,int n)
{
	int i = 0;
	//       1.創建大堆找出最大元素
	//       2.交換首尾元素
	//       3.選出次大元素，即將前n-1個數再向下調整
	//       4.重復上述步驟直到只剩堆頂就不需調整

	for (i = (n-1-1)/ 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}

	for (i = n-1; i > 0; i--)
	{
		Swap(arr + i, arr);
		AdjustDown(arr, i, 0);
	}

	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	
}

TOP-K問題

TOP-K問題：即求資料結合中前K個最大的元素或者最小的元素，一般情況下資料量都比較大，

比如：專業前10名、世界500強、富豪榜、游戲中前100的活躍玩家等，

對于Top-K問題，能想到的最簡單直接的方式就是排序，但是：如果資料量非常大，排序就不太可

取了(可能資料都不能一下子全部加載到記憶體中)，最佳的方式就是用堆來解決，基本思路如下：

1. 用資料集合中前K個元素來建堆

前k個最大的元素，則建小堆
前k個最小的元素，則建大堆
2. 用剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素
將剩余N-K個元素依次與堆頂元素比完之后，堆中剩余的K個元素就是所求的前K個最小或者最大的元素，

void Topk()
{
	//TopK問題：在一組資料中找到最大(小)的k個數
	//方法:  創建容量為k的堆(找最大的數就創建小堆，反之就創建大堆)，
	//       (例如這里我們找最大的資料，創建小堆是確保每一個比堆頂大的資料能夠沉到堆底去)
	//       將剩余的n-k個數依次與堆頂的資料相比，比他大就替換掉堆頂，然后向下調整；
	//       直到將所有資料比較完，

	HP hp;
	HeapInit(&hp);
	int arr[] = { 1,6,8,9,7,5,10,20 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int k = 3;
	int i = 0;
	for (i = 0; i < k; i++)
	{
		HeapPush(&hp, arr[i]);
	}

	for (i = k; i < sz; i++)
	{
		if (arr[i] > HeapTop(&hp))
		{
			hp.a[0] = arr[i];
			AdjustDown(hp.a, hp.size, 0);
		}
	}

	HeapPrint(&hp);
	HeapDestroy(&hp);

}

二叉樹鏈式結構的實作

前置說明

在學習二叉樹的基本操作前，需先要創建一棵二叉樹，然后才能學習其相關的基本操作，由于現在對二叉樹結構掌味訓不夠深入，為了降低學習成本，此處手動快速創建一棵簡單的二叉樹，快速進入二叉樹操作學習，等二叉樹結構了解的差不多時，我們反過頭再來研究二叉樹真正的創建方式，

typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType _data;
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
}BTNode;
BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    node1->_left = node2;
    node1->_right = node4;
    node2->_left = node3;
    node4->_left = node5;
    node4->_right = node6;
    return node1;
}

注意：上述代碼并不是創建二叉樹的方式，真正創建二叉樹方式后序詳解重點講解，
再看二叉樹基本操作前，再回顧下二叉樹的概念，二叉樹是：
1. 空樹
2. 非空：根節點，根節點的左子樹、根節點的右子樹組成的，

從概念中可以看出，二叉樹定義是遞回式的，因此后序基本操作中基本都是按照該概念實作的，

二叉樹的遍歷

前序、中序以及后序遍歷

學習二叉樹結構，最簡單的方式就是遍歷，所謂二叉樹遍歷(Traversal)是按照某種特定的規則，依次對二叉樹中的節點進行相應的操作，并且每個節點只操作一次，訪問結點所做的操作依賴于具體的應用問題，遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎，

按照規則，二叉樹的遍歷有：前序/中序/后序的遞回結構遍歷：

前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點的操作發生在遍歷其左右子樹之前，
中序遍歷(Inorder Traversal)——訪問根結點的操作發生在遍歷其左右子樹之中（間），
后序遍歷(Postorder Traversal)——訪問根結點的操作發生在遍歷其左右子樹之后，

由于被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹，NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷，

// 二叉樹前序遍歷
void PreOrder(BTNode* root);
// 二叉樹中序遍歷
void InOrder(BTNode* root);
// 二叉樹后序遍歷
void PostOrder(BTNode* root);

前序遍歷遞回圖解：

中序遍歷和后序遍歷類似，只是訪問根結點的順序不同，中序遍歷是左根右，后序遍歷是左右根，這里就不再細說，直接上代碼吧：

// 二叉樹前序遍歷
void PreOrder(BTNode* root)
{
	if (root == NULL)//如果左右子樹是空樹就列印NULL
	{
		printf("NULL ");
		return;
	}

	printf("%c ", root->data);//先訪問根結點
	PreOrder(root->left);
	PreOrder(root->right);
}
// 二叉樹中序遍歷
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	
	InOrder(root->left);
	printf("%c ", root->data);//中間訪問根結點
	InOrder(root->right);
}
// 二叉樹后序遍歷
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);//最后訪問根結點
}

層序遍歷

層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷，設二叉樹的根節點所在層數為1，層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然后從左到右訪問第2層上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問樹的結點的程序就是層序遍歷，

層序遍歷是逐層遍歷，所以遞回就不再適用了，

這里的方法是使用佇列來做，

方法：

先將根節點入隊，
如果佇列不為空，就將隊頭出隊，出隊的同時將隊頭的左右子節點(不為空)入隊，
直到佇列為空結束，

注意：佇列使用鏈表實作的，這里我為了方便畫圖表示，將他看作了整體，

且佇列中的每個結點如果存放該樹根節點的資料，這樣就找不到左右子樹；所以應該存該根節點，

在佇列的頭檔案中改變節點資料型別時須在前面前置宣告該二叉樹結構體，

代碼如下：

// 層序遍歷
void LevelOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	Queue q;//創建佇列
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->data);

        //如果左右子節點不為空則入隊
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}

	}

	printf("\n");
	QueueDestroy(&q);
}

節點個數以及高度等

// 二叉樹節點個數
int BinaryTreeSize(BTNode* root);
// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉樹的深度
int BinaryTreeDeepth(BTNode* root);

二叉樹節點個數：采用分治思想，即節點個數等于根結點+左子樹節點個數+右子樹節點個數，

// 二叉樹節點個數
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : //空樹 
                          BinaryTreeSize(root->left) + //左子樹節點個數
                          BinaryTreeSize(root->right) + //右子樹節點個數
                          1;//根節點
}

二叉樹葉子節點個數：葉子節點即度為0的節點，左右子樹都為NULL

// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)//空樹
	{
		return 0;
	}
	else if (root->left == NULL && root->right == NULL)//葉子節點
	{
		return 1;
	}
	else
	{             //左子樹葉子節點+右子樹葉子節點
		return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
	}
}

二叉樹第k層節點個數：分治思想，第k層節點個數等于左子樹第k-1層節點個數+右子樹第k-1層節點個數，且當k=1時當前根節點就是第k層，

// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	else
	{
		return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
	}
}

二叉樹查找值為x的節點 :遍歷二叉樹，注意找到節點時需將該節點保存，不然不能回傳該節點，

// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	
	if (root->data == x)
	{
		return root;//找到了就回傳該節點
	}
	BTNode* nodeleft = BinaryTreeFind(root->left, x);//創建變數保存左子樹回傳的節點
	if (nodeleft)
	{
		return nodeleft;//如果回傳的節點不為NULL，就直接回傳，不必再遍歷右子樹
	}
	BTNode* noderight = BinaryTreeFind(root->right, x);
	if (noderight)
	{
		return noderight;
	}
	return NULL;
}

二叉樹的深度 :可以理解為找出左右子樹深度較大的那一個，然后整個深度為較大的那一個+1，

int BinaryTreeDeepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int leftdepth = BinaryTreeDeepth(root->left);//保存左子樹深度
	int rightdepth = BinaryTreeDeepth(root->right);//保存右子樹深度
	
	return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;//回傳較大值+1
}

判斷二叉樹是否是完全二叉樹

判斷一棵樹是否是完全二叉樹，則需要知道什么是完全二叉樹：若一顆二叉樹的高度為k，則從該樹第0層到第k-1層的左右子節點全部不為NULL，第k層從左到右節點連續，

既然要判斷每一層，所以這里還需要使用層序遍歷的方法(即佇列)來做：

方法：

將二叉樹的所有節點入隊(方法同層序遍歷一樣，出頭結點，入左右子節點，空節點也入)，

若出隊的節點為NULL，則退出回圈，

檢查佇列中剩余節點是否全為NULL，全為NULL則是完全二叉樹，否則不是完全二叉樹，

// 判斷二叉樹是否是完全二叉樹
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
        
        //若出的節點為NULL，退出回圈
		if (front == NULL)
		{
			break;
		}
        //否則繼續入左右子節點，空節點也入
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}

    //判斷佇列中剩余節點
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
        //若存在不為空的節點，則說明該樹不是完全二叉樹
		if (front)
		{
            //回傳之前需銷毀佇列
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

二叉樹銷毀

按照后序遍歷的方式銷毀二叉樹，

// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory((*root)->left);
	BinaryTreeDestory((*root)->right);
	free(*root);
	*root = NULL;

}

創作不易，留個贊再走吧~

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/356983.html

標籤：其他

上一篇：壓力測驗工具webbench使用方法

下一篇：【Leetcode】單鏈表中快慢指標(雙指標)的運用

【資料結構】二叉樹(順序結構+鏈式結構+堆排序+Topk問題)

樹概念及結構

樹的概念

樹的相關概念

樹的表示

樹在實際中的運用（表示檔案系統的目錄樹結構）

二叉樹概念及結構

概念

現實中的二叉樹

特殊的二叉樹

二叉樹的性質

二叉樹的存盤結構

二叉樹的順序結構及實作

二叉樹的順序結構

堆的概念及結構

堆的實作

堆的初始化

堆的銷毀

堆的列印

堆的插入

堆的洗掉

堆的判空

堆的資料個數

取堆頂資料

堆的應用

堆排序

TOP-K問題

二叉樹鏈式結構的實作

前置說明

二叉樹的遍歷

前序、中序以及后序遍歷

層序遍歷

節點個數以及高度等

判斷二叉樹是否是完全二叉樹

二叉樹銷毀