準備

博主:大大怪先森(記得關注哦!）
編程環境：vs2013

提示：本文內容基于C語言主要講述資料結構二叉樹的問題！！！

文章目錄

準備
前言
一、二叉樹和樹
- 1.1樹的概念
- 1.2樹的相關概念
- 1.3 樹的表示方法
- 1.3二叉樹的概念及其結構
- - 1.3.1二叉樹的概念
  - 1.3.2 現實生活中的二叉樹
  - 1.3.3特殊的二叉樹
- 1.4二叉樹的相關概念
- - 1.4.1二叉樹的性質
  - 1.4.2二叉樹的存盤結構
  - - 1.4.2.1順序存盤
    - 1.4.2.2鏈式存盤
- 1.5二叉樹和樹，森林之間的相互轉化
二、二叉樹經典例題
- 1.前序，中序，后序遍歷二叉樹
- 2.二叉樹求葉子節點的個數
- 3.二叉樹中查找值為x的節點
- 4.二叉樹中第k層的個數
- 5.二叉樹中深度
三、大堆和小堆
- 3.1堆的概念和結構
- 3.2大堆和小堆的建立
- - 3.2.1大小堆的向上和向下調整
- 3.3topk問題
- 3.4堆排序
總結
結語

前言

提示：本文要記錄的大概內容：
二叉樹是資料結構當中一種重要的存盤方式
本文將簡單講述二叉樹的存盤方法和相關樹的問題！！！

提示：以下是本篇文章正文內容

一、二叉樹和樹

1.1樹的概念

樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因
為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，

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

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; // 結點中的資料域
};

在這里插入圖片描述

1.3二叉樹的概念及其結構

1.3.1二叉樹的概念

一棵二叉樹是結點的一個有限集合，該集合:

或者為空

由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成

從上圖可以看出：

二叉樹不存在度大于2的結點
二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
注意：對于任意的二叉樹都是由以下幾種情況復合而成的：

1.3.2 現實生活中的二叉樹

作為一個程式員，當看到這棵樹的第一反應，我相信就是：哎，，，這不是一顆二叉樹嗎？果然現實中處處都是知識

1.3.3特殊的二叉樹

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

1.4二叉樹的相關概念

1.4.1二叉樹的性質

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

1.4.2二叉樹的存盤結構

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

1.4.2.1順序存盤

順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，而現實中使用中只有堆才會使用陣列來存盤二叉樹順序存盤在物理上是一個陣列，在邏輯上是一顆二叉樹，

1.4.2.2鏈式存盤

二叉樹的鏈式存盤結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系，通常的方法是鏈表中每個結點由三個域組成，資料域和左右指標域，**左右指標分別用來給出該結點左孩子和右孩子所在的鏈結點的存盤地址，**鏈式結構又分為二叉鏈和三叉鏈，

1.5二叉樹和樹，森林之間的相互轉化

在這里插入圖片描述

二、二叉樹經典例題

1.前序，中序，后序遍歷二叉樹

此處以中序的內容舉例
代碼如下（示例）：

//中序遍歷二叉樹
void InOrder(BTNode* root)
{
	if (root == NULL){
		printf("NULL ");
		return;
	}

	InOrder(root->lchild);
	printf("%C ", root->data);
	InOrder(root->rchild);
}

2.二叉樹求葉子節點的個數

代碼如下（示例）：

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

3.二叉樹中查找值為x的節點

//二叉樹查找值為X的節點
BTNode* BinaryTreeFind(BTNode* root, STDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	struct Tree* left = BinaryTreeFind(root->lchild, x);
	if (left != NULL)
		return left;
	struct Tree* right = BinaryTreeFind(root->rchild, x);
	if (right != NULL)
		return right;
	return NULL;
}

4.二叉樹中第k層的個數

//二叉樹第k層的節點的個數
int BinaryTreeLevelSize(BTNode* root,int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	// root不等空，k也不等于1，說明root這顆樹的第k節點在子樹里面
	// 轉換成求左右子樹的第k-1等的節點數量
	return BinaryTreeLevelSize(root->lchild, k - 1) + 
		BinaryTreeLevelSize(root->rchild, k - 1);
}

在這里插入圖片描述

5.二叉樹中深度

// 二叉樹深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftDepth = BinaryTreeDepth(root->lchild);

	int rightDepth = BinaryTreeDepth(root->rchild);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

在這里插入圖片描述

三、大堆和小堆

3.1堆的概念和結構

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

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

3.2大堆和小堆的建立

3.2.1大小堆的向上和向下調整

//大堆樹：向上調整
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}
		child = parent;
		parent = (child - 1) / 2;
	}
}
//小堆樹：向下調整
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++;
		}
		if (child < n && a[child] < a[parent])//如果想要更改為大堆只需要將<更改為>即可
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}

此處以一個小堆的更換來演示小堆的作業模式（AdjustDown函式）：
在這里插入圖片描述

3.3topk問題

對于小堆和大堆我相信各位大大一定有了一定得了解，那么大小堆究竟有什么作用？
我們接著往下看
思考：在n個數中選出最大的k個數？

思路方法：
1.使用前k個數建立一個k個數的小堆
2.剩下的n - k個數與小堆的堆頂進行比較如果比堆頂大就進行交換，
3.最后堆里面的就是最大的k個數

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

typedef struct Tree
{
	STDataType data;
	struct Tree* lchild;
	struct Tree* rchild;
}BTNode;
//初始化節點
void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

//交換大小
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}
		child = parent;
		parent = (child - 1) / 2;
	}
}
//在N個數中找到最大的k個數
void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	int parent = 0;
	if (hp->size == hp->capacity)
	{
		int Nowcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		struct Heap* tmp = (struct Heap*)realloc(hp->a,sizeof(struct Heap) * Nowcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail");
		}
		hp->a = tmp;
		hp->capacity = Nowcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a,hp->size - 1);
}
void HeapPrintTopk(int* a, int n,int k)
{
	HP hp;
	HeapInit(&hp);
	//創建一個小堆
	for (int i = 0; i < k; i++)
	{
		HeapPush(&hp, a[i]);
	}
	//剩下的N - K 個數跟堆頂的元素資料比較，比它大，就替換他進堆
	for (int i = k; i < n - k; i++)
	{
		if (a[i] > HeapTop(&hp))
		{
			hp.a[0] = a[i];
			AdjustDown(hp.a, hp.size, 0);//AdjustDown()函式此處不在寫入，可以參照上面，
		}
	}
}

3.4堆排序

void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		//利用向下排序建立大堆選出最大的數
		AdjustDown(a, n, i);
	}
	//依次選數，調堆O(N * log ^ n)
	for (int end = n - 1; end > 0; end--)
	{
		//大堆就是最大的樹與最后一個數交換位置
		Swap(&a[0], &a[end]); 
		//再進行一次向下大堆調整
		AdjustDown(a, end, 0);
	}
}

以一個陣列：18 16 56 23 17 65 為例
利用向下排序建立大堆選出最大的數（圖解）

大堆就是最大的樹與最后一個數交換位置
再進行一次向下大堆調整于是將最大的數交換到資料最后的位置

總結

二叉樹問題的大多數的解決方法就是基于左右孩子的遞回問題，當處理問題我們應該盡可能就
去解決左右子樹的問題，

結語

希望本篇文章能給各位帶來幫助，如有不足還請指正！！！
碼字不易，各位大大給個收藏點贊吧！！！

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

標籤：其他

上一篇：開源作業系統OpenHarmony就要搭配開源圖形驅動Mesa

下一篇：順序表@線性表

【初階】帶你看懂二叉樹（附圖解）

準備

文章目錄

前言

一、二叉樹和樹

1.1樹的概念

1.2樹的相關概念

1.3 樹的表示方法

1.3二叉樹的概念及其結構

1.3.1二叉樹的概念

1.3.2 現實生活中的二叉樹

1.3.3特殊的二叉樹

1.4二叉樹的相關概念

1.4.1二叉樹的性質

1.4.2二叉樹的存盤結構

1.4.2.1順序存盤

1.4.2.2鏈式存盤

1.5二叉樹和樹，森林之間的相互轉化

二、二叉樹經典例題

1.前序，中序，后序遍歷二叉樹

2.二叉樹求葉子節點的個數

3.二叉樹中查找值為x的節點

4.二叉樹中第k層的個數

5.二叉樹中深度

三、大堆和小堆

3.1堆的概念和結構

3.2大堆和小堆的建立

3.2.1大小堆的向上和向下調整

3.3topk問題

3.4堆排序

總結

結語