二叉樹

1.樹的概念及結構
- 1.1樹的概念
- 1.2樹的相關概念
- 1.3樹的表示
2.二叉樹概念及結構
- 2.1概念
- 2.2特殊的二叉樹
- 2.3二叉樹的性質
- 2.4二叉樹的存盤結構
3.二叉樹的順序結構及實作
- 3.1二叉樹的順序結構
- 3.2堆的概念及結構
- 3.3堆的實作
- - 3.3.1堆向下調整演算法
  - 3.3.2堆的創建
  - 3.3.3建堆時間復雜度
  - 3.3.4堆的插入
  - 3.3.5堆的洗掉
  - 3.3.6堆的代碼實作
- 3.4堆的應用
- - 3.4.1堆排序
  - 3.4.2TOP-K問題
4.二叉樹鏈式結構的實作
- 4.1前置說明
- 4.2二叉樹的遍歷
- 4.3二叉樹的實作

1.樹的概念及結構

1.1樹的概念

樹是一種資料結構，它是由n(n≥1)個有限節點組成一個具有層次關系的集合，把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，
特點：
1、有一個特殊的結點，稱為根結點，根節點沒有前驅結點，
2、除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i<= m)又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼，
3、因此，樹是遞回定義的，
注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構，

在這里插入圖片描述

1.2樹的相關概念

在這里插入圖片描述

節點的度：一個節點含有的子樹的個數稱為該節點的度；如上圖：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）棵互不相交的樹的集合稱為森林，

1.3樹的表示

樹結構相對線性表就比較復雜了，要存盤表示起來就比較麻煩了，既然保存值域，也要保存結點和結點之間的關系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等，我們這里就簡單的了解其中最常用的孩子兄弟表示法，
在這里插入圖片描述

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

2.二叉樹概念及結構

2.1概念

二叉樹（Binary tree）是樹形結構的一個重要型別，許多實際問題抽象出來的資料結構往往是二叉樹形式，即使是一般的樹也能簡單地轉換為二叉樹，而且二叉樹的存盤結構及其演算法都較為簡單，因此二叉樹顯得特別重要，二叉樹特點是每個結點最多只能有兩棵子樹，且有左右之分，
二叉樹是n個有限元素的集合，該集合或者為空、或者由一個稱為根（root）的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成，是有序樹，當集合為空時，稱該二叉樹為空二叉樹，在二叉樹中，一個元素也稱作一個結點，
特點：
一棵二叉樹是結點的一個有限集合，該集合:
1.或者為空
2. 由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成
在這里插入圖片描述
從上圖可以看出：
1 .二叉樹不存在度大于2的結點
2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
注意：對于任意的二叉樹都是由以下幾種情況復合而成的：

2.2特殊的二叉樹

滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是，則它就是滿二叉樹，
完全二叉樹：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹，要注意的是滿二叉樹是一種特殊的完全二叉樹，

2.3二叉樹的性質

在這里插入圖片描述

2.4二叉樹的存盤結構

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

順序存盤
順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，而現實中使用中只有堆才會使用陣列來存盤，二叉樹順序存盤在物理上是一個陣列，在邏輯上是一顆二叉樹，
鏈式存盤
二叉樹的鏈式存盤結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系，通常的方法是鏈表中每個結點由三個域組成，資料域和左右指標域，左右指標分別用來給出該結點左孩子和右孩子所在的鏈結點的存盤地址，

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

3.二叉樹的順序結構及實作

3.1二叉樹的順序結構

普通的二叉樹是不適合用陣列來存盤的，因為可能會存在大量的空間浪費，而完全二叉樹更適合使用順序結構存盤，現實中我們通常把堆(一種二叉樹)使用順序結構的陣列來存盤，
需要注意的是這里的堆和作業系統虛擬行程地址空間中的堆是兩回事，一個是資料結構，一個是作業系統中管理記憶體的一塊區域分段，
在這里插入圖片描述

3.2堆的概念及結構

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

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

在這里插入圖片描述

3.3堆的實作

3.3.1堆向下調整演算法

現在我們給出一個陣列，邏輯上看做一顆完全二叉樹，我們通過從根節點開始的向下調整演算法可以把它調整成一個小堆，向下調整演算法有一個前提：左右子樹必須是一個堆，才能調整，

int array[] = {27,15,19,18,28,34,65,49,25,37};

3.3.2堆的創建

下面我們給出一個陣列，這個陣列邏輯上可以看做一顆完全二叉樹，但是還不是一個堆，現在我們通過演算法，把它構建成一個堆，根節點左右子樹不是堆，我們怎么調整呢？這里我們從倒數的第一個非葉子節點的子樹開始調整，一直調整到根節點的樹，就可以調整成堆，

int a[] = {1,5,3,8,7,6};

3.3.3建堆時間復雜度

在這里插入圖片描述

3.3.4堆的插入

先插入一個10到陣列的尾上，再進行向上調整演算法，直到滿足堆，
在這里插入圖片描述

3.3.5堆的洗掉

洗掉堆是洗掉堆頂的資料，將堆頂的資料根最后一個資料一換，然后洗掉陣列最后一個資料，再進行向下調整演算法，
在這里插入圖片描述

3.3.6堆的代碼實作

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

//交換函式
void Swap(int* px, int* py);
//向下調整演算法
void AdjustDown(int* a, int n, int parent);
//向上調整演算法
void AdjustUp(int* a,int child);
//堆初始化
//void HeapInit(HP* php);
void HeapInit(HP* php,HPDataType* a,int n);
//堆銷毀
void HeapDestroy(HP* php);
//堆的插入，插入x，保持它繼續是堆
void HeapPush(HP* php, HPDataType x);
//堆的洗掉，洗掉堆頂資料，洗掉后保持它繼續是堆
void HeapPop(HP* php);
//獲得堆頂資料，也就是最值
HPDataType HeapTop(HP* php);
//堆的判空
bool HeapEmpty(HP* php);
//求堆有多少的元素
int HeapSize(HP* php);
//堆的列印
void HeapPrint(HP* php);

交換函式

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

向下調整演算法

//條件:左右子樹都是小堆/大堆
//示例:小堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child<n)
	{
		//選出左右孩子中小的那個
		if (child + 1 < n && a[child + 1] > a[child])//判斷是否越界
		{
			++child;
		}
		//1.如果小的孩子小于父親，則交換，繼續往下調整，
		//2.如果小的孩子大于父親，則結束，
		if (a[child]>a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

向上調整演算法

void AdjustUp(int* a,int child)
{
	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 HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	memcpy(php->a, a, sizeof(HPDataType)*n);
	//建堆
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}
	php->size = n;
	php->capacity = n;
}

堆銷毀

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

堆的插入

//插入x，保持它繼續是堆
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
		if (php->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	php->size++;

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

堆的洗掉

//洗掉堆頂資料，洗掉后保持它繼續是堆
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size,0);
}

獲得堆頂資料，也就是最值

//獲得堆頂資料，也就是最值
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}

堆的判空

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

求堆有多少的元素

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

堆的列印

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

3.4堆的應用

3.4.1堆排序

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

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

//堆排序 -> 效率更高
//排升序->大堆
//排降序->小堆
void HeapSort(int* a, int n)
{
	//建堆演算法
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//降序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

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

3.4.2TOP-K問題

TOP-K問題：即求資料結合中前K個最大的元素或者最小的元素，一般情況下資料量都比較大，
對于Top-K問題，能想到的最簡單直接的方式就是排序，但是：如果資料量非常大，排序就不太可取了(可能資料都不能一下子全部加載到記憶體中)，最佳的方式就是用堆來解決，基本思路如下：

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

void PrintTopK(int* a, int n, int k)
{
	HP hp;
	HeapInit(&hp, a, k);

	for (int i = k; i < n; ++i)
	{
		if (a[i] > HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
	}

	HeapPrint(&hp);

	HeapDestroy(&hp);
}

void TestTopk()
{
	int n = 100000;
	int* a = (int*)malloc(sizeof(int)*n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;

	PrintTopK(a, n, 10);
}

4.二叉樹鏈式結構的實作

4.1前置說明

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

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;

	return node;
}

BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode('A');
	BTNode* node2 = BuyNode('B');
	BTNode* node3 = BuyNode('C');
	BTNode* node4 = BuyNode('D');
	BTNode* node5 = BuyNode('E');
	BTNode* node6 = BuyNode('F');

	node1->_left = node2;
	node1->_right = node3;
	node2->_left = node4;
	node3->_left = node5;
	node3->_right = node6;
	return node1;
}

4.2二叉樹的遍歷

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

前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點的操作發生在遍歷其左右子樹之前，
中序遍歷(Inorder Traversal)——訪問根結點的操作發生在遍歷其左右子樹之中（間），
后序遍歷(Postorder Traversal)——訪問根結點的操作發生在遍歷其左右子樹之后，
由于被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹，NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷，

//前序遍歷
void PreOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}

	printf("%c ", root->_data);
	PreOrder(root->_left);
	PreOrder(root->_right);
}


//中序遍歷
void PreOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	PreOrder(root->_left);
	printf("%c ", root->_data);
	PreOrder(root->_right);
}



//后序遍歷
void PreOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}

	PreOrder(root->_left);
	PreOrder(root->_right);
	printf("%c ", root->_data);
}

示例：
在這里插入圖片描述

前序遍歷結果：1 2 3 4 5 6
中序遍歷結果：3 2 1 5 4 6
后序遍歷結果：3 1 5 6 4 1

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

//層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		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");
	QueueDestory(&q);
}

在這里插入圖片描述

4.3二叉樹的實作

二叉樹節點個數

//二叉樹節點個數
//1.遍歷 -- 全域變數
//int size = 0;
//void BinaryTreeSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	else
//	{
//		size++;
//	}
//	BinaryTreeSize(root->left);
//	BinaryTreeSize(root->right);
//
//}

//1.遍歷 -- 區域變數，傳地址
//void BinaryTreeSize(BTNode* root,int* psize)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	else
//	{
//		(*psize)++;
//	}
//	BinaryTreeSize(root->left,psize);
//	BinaryTreeSize(root->right,psize);
//
//}

//1.遍歷 -- 遞回(分而治之)
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);

}

二叉樹葉子節點個數


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

二叉樹第k層節點個數

//二叉樹第k層節點個數
//核心思路：求當前樹的第k層 = 左子樹的第k-1層 + 右子樹的第k-1層，
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

二叉樹深度/高度

//二叉樹深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

二叉樹查找值為x的節點

// 二叉樹查找值為x的節點
//先判斷是不是當前節點，是就回傳；不是先去左樹找，找到了就回傳；左樹沒找到，再去右樹找，
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* retleft = BinaryTreeFind(root->left, x);
	if (retleft)
	{
		return retleft;
	}
	BTNode* retright = BinaryTreeFind(root->right, x);
	if (retright)
	{
		return retright;
	}
	return NULL;
}

二叉樹銷毀

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

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

//判斷二叉樹是否是完全二叉樹
//核心思路：層序遍歷，把空也入佇列；完全二叉樹，非空是連續；不是完全二叉樹，非空不是連續，
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//出到空，以后，佇列中全是空，就是完全二叉樹；
	//還有非空，就不是完全二叉樹，
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestory(&q);
			return false;
		}
		
	}
	QueueDestory(&q);
	return true;
}

以上就是有關二叉樹的相關知識內容，希望對大家有所幫助；后續會給大家更新以一篇有關二叉樹方面的習題，來讓大家牛刀小試一下，感謝大家支持！加油！

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

標籤：AI

上一篇：深入淺出 eBPF 安全專案 Tracee

下一篇：Python訪問街區所有節點最短路徑問題，并結合matplotlib可視化

【資料結構】二叉樹的全部詳解，沒有比這一篇更詳細的了。

二叉樹

1.樹的概念及結構

1.1樹的概念

1.2樹的相關概念

1.3樹的表示

2.二叉樹概念及結構

2.1概念

2.2特殊的二叉樹

2.3二叉樹的性質

2.4二叉樹的存盤結構

3.二叉樹的順序結構及實作

3.1二叉樹的順序結構

3.2堆的概念及結構

3.3堆的實作

3.3.1堆向下調整演算法

3.3.2堆的創建

3.3.3建堆時間復雜度

3.3.4堆的插入

3.3.5堆的洗掉

3.3.6堆的代碼實作

3.4堆的應用

3.4.1堆排序

3.4.2TOP-K問題

4.二叉樹鏈式結構的實作

4.1前置說明

4.2二叉樹的遍歷

4.3二叉樹的實作