主頁 > 軟體設計 > [資料結構]樹、堆、二叉樹內容的詳解與分析

[資料結構]樹、堆、二叉樹內容的詳解與分析

2021-09-27 09:47:32 軟體設計

在這里插入圖片描述

[資料結構]樹、堆、二叉樹內容的詳解與分析

  • 前言
  • 一、樹的結構與概念
    • 1.1樹的概念
    • 1.2樹的相關概念
    • 1.3樹的表示
    • 1.4樹的實際應用
  • 二、二叉樹的概念與結構
    • 2.1二叉樹的概念
    • 2.2特殊的二叉樹
    • 2.3二叉樹的性質
    • 2.4二叉樹的存盤
      • 2.4.1順序存盤
      • 2.4.2鏈式存盤
  • 三、二叉樹的順序結構及實作
    • 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.3.7堆的資料個數
      • 3.3.8堆的判空
    • 3.4堆的排序
    • 3.4堆中的topk問題
  • 四、二叉樹的鏈式結構及實作
    • 4.1前置說明
    • 4.2二叉樹的遍歷
    • 4.3二叉樹的常見介面
      • 4.3.1二叉樹的節點個數
      • 4.3.2二叉樹葉子節點的個數
      • 4.3.3二叉樹第k層節點個數
      • 4.3.4二叉樹查找值為x的節點
  • 總結

前言

在這里插入圖片描述

相信各位只要接觸過計算機這門學科，無論是否有學到過二叉樹的內容，但我們總是或多或少聽說過二叉樹這一話題，或許是來自學長學姐的吐槽它的難理解，又或許是來自老師的重復講解可任聽不懂，又或者正通過這篇文章了解到二叉樹；下面是我對二叉樹內容學習的個人理解與分析，希望對你有所幫助，

一、樹的結構與概念

1.1樹的概念

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

在這里插入圖片描述

②有一個特殊的結點，稱為根結點，根節點沒有前驅結點

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

④通過上面的三條相關概念的講解，我們可以初步知道樹可以劃分為三個部分，分別是根、左子樹、右子樹，而我們進一步分析，任一個子樹好像又可以按照上述的三個部分進行劃分，即子樹也含有根、左子樹、右子樹，那么我們對樹的定義時，我們可以采用遞回進行定義

在這里插入圖片描述

1.2樹的相關概念

在這里插入圖片描述

a、節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的為6；
b、葉節點或終端節點：度為0的節點稱為葉節點； 如上圖：B、C、H、I…等節點為葉節點；
c、非終端節點或分支節點：度不為0的節點； 如上圖：D、E、F、G…等節點為分支節點；
d、雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節
點；
e、孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點；
f、兄弟節點：具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點；
g、樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6；
h、節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
i、樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4；
j、堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點；
k、節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先；
l、子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫；
m、森林：由m（m>0）棵互不相交的樹的集合稱為森林；

上述這些定義我們只需要對其簡單理解即可，我們在后續的講解中并不會全部使用

1.3樹的表示

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

代碼如下：

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

②說明：
上述代碼中的“struct Node* _pNextBrother”，這里我們說的"指向其下一個兄弟節點"，這個兄弟節點是從左開始向右結束，并且擁有同一個父節點

如圖：
在這里插入圖片描述如：這里的D指向的E和E指向的F，它們之間都擁有同一個父節點；

1.4樹的實際應用

在我們的生活中與樹結構相似的場景是較為常見的，比如我們使用的電腦中的目錄樹結構

在這里插入圖片描述

二、二叉樹的概念與結構

2.1二叉樹的概念

①概念：
一棵二叉樹是結點的一個有限集合，并且該集合有兩個特點：
a、或者為空（空樹）
b、有一個根節點加上兩顆分別稱為左子樹和右子樹的二叉樹組成
①②特點：
a、二叉樹中不存在度大于2的節點
b、二叉樹的子樹有左右之分，次序不能顛倒，也因此二叉樹是有序樹

2.2特殊的二叉樹

根據上面我的講述，相信大家對二叉樹有了一個簡單的了解，但我們知道，任何事務的存在都有特殊的情況，二叉樹也不列外，我們根據一個二叉樹的葉節點的個數將二叉樹進行了一個分類，又或者叫特殊的二叉樹

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

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

上面的定義可能第一次閱讀時不好理解，下面是我們的滿二叉樹和完全二叉樹的舉例圖解，便于大家理解

在這里插入圖片描述

2.3二叉樹的性質

注意：二叉樹的性質是根據經驗與分析所得

  1. 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有2^(i-1)個結點.
  2. 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是 2^h -1
  3. 對任何一棵二叉樹, 如果度為0其葉結點個數為n0, 度為2的分支結點個數為n2 ,則有n0 = n2 + 1
  4. 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h = log2（n+1）（PS：log2（n+1）是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否則無右孩子

2.4二叉樹的存盤

二叉樹的存盤一般使用兩種結構進行存盤，一種是順序結構存盤，一種是鏈式結構存盤

2.4.1順序存盤

①定義：
順序結構存盤就是使用陣列來存盤，一般使用陣列只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費，而現實中使用中只有堆才會使用陣列來存盤，關于堆我們后面的章節會專門講解，二叉樹順序存盤在物理上是一個陣列，在邏輯上是一顆二叉樹，

②圖解：
在這里插入圖片描述

2.4.2鏈式存盤

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

②圖解：
在這里插入圖片描述
在這里插入圖片描述

三、二叉樹的順序結構及實作

3.1二叉樹的順序結構

①普通的二叉樹是不適合用陣列來存盤的，因為可能會存在大量的空間浪費，而完全二叉樹更適合使用順序結構存盤，

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

在這里插入圖片描述

3.2堆的概念與分類

①概念：
在這里插入圖片描述

②分類：

小堆：在樹中，所有的父親節點都小于孩子節點，其中根節點最小
注意：所有的父親節點是指根節點和所有左子樹和右子樹中的父親節點
在這里插入圖片描述
大堆：在樹中，所以的父親節點都大于孩子節點，其中根節點最大

在這里插入圖片描述

3.3堆的實作

下面我們將實作堆的各種介面，這是我們建立的堆的結構體：

typedef int HPDataTpye;
typedef struct Heap
{
	HPDataTpye* a;//指向陣列的指標
	int size;//記錄當前陣列中存盤元素的個數
	int capacity;//陣列的最大存盤能力
}HP;

3.3.1堆的向下調整演算法

①引言：
現在我們給一個陣列隨機進行賦值，最終我們得到的陣列內容為：
arr=[27,15,19,18,28,34,65,49,25,37]
而此時我們可以通過這里的“向下調整演算法”實作堆的建立，可我們真的可以對任意的陣列通過這個“向下調整演算法”實作堆的建立嗎？

在這里插入圖片描述
②引言回答：
答案是否定的，這里我們對這個隨機陣列進行分析，其實我們可以發現根節點下的左右子樹均為小堆

③堆的向下調整演算法的使用條件：根的左右子樹均為堆，并且左右子樹的堆的型別相同

④代碼：

void Swap(int * px, int * py)//交換函式
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
//向下調整，前提是左右子樹都是小堆或者大堆
//因為上述隨機陣列中，左右子樹均為小堆，所以我們建立小堆
void AdjustDown(int* a, int n, int parent)//a是我們的陣列；n是我們陣列的元素個數；parent是我們根節點的坐標
{
	int child = parent * 2 + 1;//這里我們先默認小孩子指向左孩子；
	while (child < n)
	{
		if (a[child + 1]<n && a[child + 1] < a[child])//如果我們的右孩子小于我們的左孩子
		{
			++child;//此時我們的小孩子就指向了右孩子；這一步，我們就選出來左右孩子中小的孩子
		}

		if (a[child] < a[parent])//如果我們的小的孩子小于父親，那么我們進行交換；這里我寫出一個交換函式，后續任需要用到
		{
			Swap(&a[child], &a[parent]);//當我們交換完成之后，根據我們之前的分析可知，當孩子與父親交換之后，父親要從新的位置繼續進行比較交換
			parent = child;
			child = parent * 2 + 1;
		}
		else//如果我們小的孩子比父親大，那么我們就結束交換；
		{ 
			break;
		}
	}
}

⑤代碼部分陳述句決議：

int child = parent * 2 + 1;

這里是我們上面講述的“2.3二叉樹的性質”，在樹中，父子之間的陣列坐標之間的關系為：
①leftchild= parent*2 + 1;

②rightchild = parent* 2 + 2;

③parent = (child-1)/2

while (child < n)
{
	…………
}

這里的判讀條件為child<n是因為當我們在建立小堆時，我們不斷將parent與child進行比較交換，但最終是要停止的，而這個停止的條件是當我們的parent存在的時候，我們的child不存在，那么這個時候我們就不能在進行比較交換，則當child = parent* 2 + 1 不存在時，停下來，而這個不存在的條件“當我們的child這個節點不存”翻譯成另一種話術就是“我們的child的下標超出了物理結構的陣列范圍，即child < n”

⑥代碼分析與檢驗：
上述我們的代碼中，我們建立的結果是將這個陣列的內容在邏輯結構上建立成小堆，這是因為我們給出的案例是兩個左右子樹均為小堆，所以我們在寫代碼時的目的就是建立小堆，但注意“堆的向下調整演算法”并非只能建立小堆，當我們的“隨機”陣列中的左右子樹均為大堆時，那么我們只要將代碼中的“<”替換成“>”即可，這樣當我們的陣列通過代碼后即建立成大堆，

代碼如下：

int a[] = { 12, 45, 36, 32, 21, 34, 20 };

此時我們的隨機陣列的根的左右子樹均為大堆，那么我們只需要對堆的向下調整演算法改進即可建立大堆

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 (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

上述就是建立大堆的“堆的向下調整演算法”

#include<stdio.h>

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;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

int main()
{
	int a[] = { 12, 45, 36, 32, 21, 34, 20 };
	AdjustDown(a, sizeof(a) / sizeof(int), 0);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}

	return 0;
}

圖解：
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述

3.3.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 (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int * a, int n)//將隨機陣列建立成堆
{
	for (int i = (n - 1 - 1) / 2; i >= 0;--i)
	{
		AdjustDown(a, n, i);
	}
}

⑤代碼分析與檢驗：

#include<stdio.h>

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;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int * a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0;--i)
	{
		AdjustDown(a, n, i);
	}
}

int main()
{
	int a[] = { 0, 69, 36, 12, 21, 22, 64, 25, 49, 15 };
	HeapSort(a, 10);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}

	return 0;
}

圖解：

在這里插入圖片描述

3.3.3建堆的時間復雜度（了解）

在這里插入圖片描述

3.3.4堆的插入

在這里插入圖片描述

①問題：
我們在前面學習順序表和鏈表時，我們經常實作對其進行元素的插入 ，洗掉等操作，在堆中任然需要實作這些功能，但和順序表和鏈表不同的是，當我們在堆中插入元素時，我們任然需要確保堆在插入元素之后堆任然成立

②分析：
我們想要實作堆的插入，同時又要保證堆的成立，如果我們空想的話很難有所思路，這個時候我們畫圖進行分析

在這里插入圖片描述
在這里插入圖片描述在這里插入圖片描述③代碼：

//前提：我們原有的堆為大堆
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 HeapPush(HP* php, HPDataTpye x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataTpye* tmp = (HPDataTpye*)realloc(php->a, php->capacity * 2 * sizeof(HPDataTpye));
		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);

}//插入元素；這里不再是鏈表的情況，頭插尾插，這里我們只需要保證插入之后任然是堆；

3.3.5堆的洗掉

在這里插入圖片描述

①問題：
我們在前面學習順序表和鏈表時，我們經常實作對其進行元素的插入 ，洗掉等操作，在堆中任然需要實作這些功能，但和順序表和鏈表不同的是，我們在堆中的洗掉元素只有洗掉頭節點才有意義，如果我們洗掉的是堆中的最后一個元素太過簡單，只需要將陣列的計數變數減一即可實作，所以我們要實作的是洗掉堆中的根節點，洗掉之后我們要保證堆的成立，

②分析：
如果我們是直接洗掉根節點的話，引出的問題就是我們相當于原本的堆變成了一個隨機陣列，那么我們就需要重復建堆的步驟，這樣的話我們的時間復雜度太高，所以我們需要換一種思路，

在這里插入圖片描述
在這里插入圖片描述
③代碼：

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);

}

3.3.6堆的銷毀

后面幾個介面的實作較為簡單，就不在進行過多描述

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

}

3.3.7堆的資料個數

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}//判斷當前堆中有多少資料；

3.3.8堆的判空

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}//判斷堆是否為空；

3.4堆的排序

在這里插入圖片描述

①引言：
通過上面的講解，我們已經可以實作對堆的一系列操作，比如堆的建立，堆的向下調整，堆的洗掉，堆的添加等；這個時候我們回顧一下堆的本質是什么？或者說樹的本質是什么？沒錯，是陣列，我們上面畫出的那些二叉樹的圖片都是我們從邏輯結構上得出的，然而本質上這些節點的存盤在記憶體中就是在一個陣列中有序排列而已，既然我們知道本質是陣列，那么在陣列中就繞不開一個話題，就是陣列的排序，在這里就是堆的排序，那么我們如何實作堆的排序呢？

在這里插入圖片描述
②分析：
既然我們要實作堆的排序，這里我以建立升序為例進行講解，如果我們想要建立一個升序那么我們應該建立一個什么樣的堆呢？大堆還是小堆？這里我們進行一一講解：
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
③代碼：

void Swap(int * px, int * py)//交換函式
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

//堆排序：效率更高
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堆中的topk問題

在這里插入圖片描述

①引言：
我們在打王者榮耀或者LOL這樣的電子競技游戲中，都有一個排名系統，比如：國服第一XXXX、XX省第一XX等等；而這些的排名的出現其實就是堆中的topk問題的實際應用，此時我們的電腦就需要處理，將那么多的玩家中選出前K名玩家進行排序，也就是獲取前K名玩家的資料，

②分析：
我們從堆的角度進行分析，我們知道這k個資料是這個堆中的最大的前k個資料，那么就看建立一個k個數的小堆；

注意這里我們建立的是k個數的小堆，為什么我們建立的是小堆，而不是大堆呢？這是因為當我們建立的是小堆時，我們最先獲取的是堆頂資料，也就是當前堆中的最小的數

若果當前我們的k個數的小堆已經存盤結束，前k個資料已經完全進入，那么我們將堆頂的資料與余下的資料進行比較時，是永遠小于我們的堆頂資料的，而若果此時余下的資料大于我們當前的堆頂資料，那么就說明前k個資料還有資料沒有進入我們的小堆，那么我們就可以先進行堆頂資料的洗掉，然后在將這個大于堆頂的資料插入，這樣我們就實作了將原本前k的資料插入我們的小堆，

③代碼：

void HeapInit(HP* php, HPDataTpye* a, int n)//這里的HPDataTpye* a是一個陣列指標，就是我們給了一個已知的陣列，然后用這個陣列對另一個陣列（堆）進行初始化
{
	assert(php);

	php->a = (HPDataTpye*)malloc(sizeof(HPDataTpye)*n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	memcpy(php->a, a, sizeof(HPDataTpye)*n);//從a的位置開始，向后sizeof……那么多個空間的內容拷貝到php->a中

	//建堆：大堆

	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		//AdjustDown(a, n, i);這里我們在寫的時候出了問題，這里我們傳參的a是我們要對結構體中的陣列進行初始化的模板陣列a，并非我們堆中被初始化的陣列：
		AdjustDown(php->a, n, i);
	}
	php->size = n;
	php->capacity = n;

}//初始化，但給了一個陣列，用于初始化


void PrintTopK(int* a,int n,int k)//topk問題
{
	HP hp;
	HeapInit(&hp,a,k);//將堆進行初始化
	for(int i = k;i<n;i++)
	{
		HeapPop(&hp);
		HeapPush(&hp,a[i]);
	}

	HeapPrint(&hp);//將堆的內容進行列印
	HeapDestory(&hp);//將堆進行銷毀
}

四、二叉樹的鏈式結構及實作

4.1前置說明

在講解二叉樹的基本操作前，需先要創建一棵二叉樹，然后才能講解其相關的基本操作，由于我們現在不知道二叉樹的基本操作，所以此處手動創建一棵簡單的二叉樹，便于對內容的講解，

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;
}

4.2二叉樹的遍歷

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

②分類：
在這里插入圖片描述③舉例：
在這里插入圖片描述
④代碼：

前序遍歷：

void PreOrder(BTNode* root)//前序遍歷
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	printf("%c ", root->data);
	return PreOrder(root->left);
	return PreOrder(root->right);
}

圖解：

在這里插入圖片描述

遞回畫圖理解（建議放大觀看）
在這里插入圖片描述
中序遍歷與后序遍歷與前序遍歷相似，建議自己畫一下上面的遞回畫圖，更加便于理解

中序遍歷：

void InOrder(BTNode* root)//中序遍歷
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	return PreOrder(root->left);
	printf("%c ", root->data);
	return PreOrder(root->right);
}

后序遍歷：

void PostOrder(BTNode* root)//后序遍歷
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	return PreOrder(root->left);
	return PreOrder(root->right);
	printf("%c ", root->data);
}

4.3二叉樹的常見介面

引言：
在這里插入圖片描述

首先我們要有一種分而治之的思想，這個思想遍歷我們的二叉樹介面的實作，我們舉個例子：

放假返校時，學習要統計學校的返校人數，那么這個時候校長找到各個學院的院長，問他們要各個學院的返校人數；這個時候各個院長找到輔導員，問學院的各個班的返校人數；再接著輔導員找到各個班的班長，問各個班的返校人數；再接著班長找到各個宿舍長，問各個宿舍的返校人數；這個時候各個宿舍長開始反饋宿舍的返校人數，就這樣逐一反饋，最終實作全校的返校人數，

這里我們發現，返校人數的統計問題從一開始的全校返校人數逐一化簡，最侄訓簡到不能再化簡，化簡到各個宿舍的返校人數，這個時候我們開始反饋宿舍的返校人數，然后逐一向上一級反饋，獲得最終返校人數，

下面我們的各個介面的實作大多數都需要上面的思想，一定要將問題簡化到不能再進行簡化

4.3.1二叉樹的節點個數

①分析:
我們要獲取一個二叉樹的節點個數，這個時候我們按照引言中獲取的思考方式，那么我們要活動二叉樹的節點個數，那么我們就要先獲得根節點的左子樹和右子樹的節點個數，而在這兩個左子樹和右子樹中，我們又要分別獲得這個兩個子樹的左子樹和右子樹的節點個數，如此重復，

②代碼：
實作一：

int size = 0;
void BinaryTreeSize(BTNode* root)//這里我們采取了全域變數size用來記錄節點的個數，如果我們函式內定義int size = 0；那么這樣的話，我們在遍歷的時候，我們就會導致size又為0
{
	if (root == NULL)
		return;
	else
		size++;
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);
}

實作二：

void BinaryTreeSize(BTNode* root,int* psize)//這里我們采取了全域變數size用來記錄節點的個數，如果我們函式內定義int size = 0；那么這樣的話，我們在遍歷的時候，我們就會導致size又為0
{
	if (root == NULL)
		return;
	else
		++*psize;
	BinaryTreeSize(root->left,psize);
	BinaryTreeSize(root->right,psize);
}

實作三：

int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

4.3.2二叉樹葉子節點的個數

①分析：
1.我們首先要對葉子結點的特征進行描述，葉子節點的左右孩子節點均為NULL；
2.當我們的節點地址為NULL時，那么這個節點不存在，那么其計數為0；
3.分而治之的思想，將問題不斷化簡；

②代碼：

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);
}

4.3.3二叉樹第k層節點個數

①分析：
在這里插入圖片描述
②代碼：

int BinaryTreeLevelkSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	
	int leftDepth = BinaryTreeLevelkSize(root->left);
	int rightDepth = BinaryTreeLevelKsize(root->right);

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

4.3.4二叉樹查找值為x的節點

①分析：
1.先判斷是否是當前節點，如果是就即刻回傳；
2.如果當前節點不是，那么就去其左子樹中進行尋找判斷，如果是就即刻回傳；
3.若左子樹沒有尋找到，那么我們就跳轉到右子樹中尋找；

②代碼：

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;
	}
}

總結

以上就是我對樹、堆、二叉樹內容的個人理解，后續我還會對其進一步講解，包括練習與更深層次的介面等內容

上述內容如果有錯誤的地方，還麻煩各位大佬指教【膜拜各位了】【膜拜各位了】
在這里插入圖片描述

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

標籤：其他

上一篇：圖資料庫JanusGraph入門(一)JanusGraph初識

下一篇：企業級springboot落地：連接內外網郵箱，實作郵件提醒功能

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 面試突擊第一季，第二季，第三季

    第一季必考 https://www.bilibili.com/video/BV1FE411y79Y?from=search&seid=15921726601957489746 第二季分布式 https://www.bilibili.com/video/BV13f4y127ee/?spm_id_fro ......

    uj5u.com 2020-09-10 05:35:24 more
  • 第三單元作業總結

    1.前言 這應該是本學期最后一次寫作業總結了吧。總體來說，對作業的節奏也差不多掌握了，作業做起來的效率也更高了。雖然和之前的作業一樣，作業中都要用到新的知識，但是相比之前，更加懂得了如何利用工具以及資料。雖然之間卡過殼，但總體而言，這幾次作業還算完成的比較好。 2.作業程序總結 相比前兩個單元，此單 ......

    uj5u.com 2020-09-10 05:35:41 more
  • 北航OO（2020）第四單元博客作業暨課程總結博客

    北航OO（2020）第四單元博客作業暨課程總結博客 本單元作業的架構設計 在本單元中，由于UML圖具有比較清晰的樹形結構，因此我對其中需要進行查詢操作的元素進行了包裝，在樹的父節點中存盤所有孩子的參考。考慮到性能問題，我采用了快取機制，一次查詢后盡可能快取已經遍歷過的資訊，以減少遍歷次數。 本單元我 ......

    uj5u.com 2020-09-10 05:35:48 more
  • BUAA_OO_第四單元

    一、UML決議器設計 ? 先看下題目：第四單元實作一個基于JDK 8帶有效性檢查的UML(Unified Modeling Language)類圖，順序圖，狀態圖分析器 MyUmlInteraction，實際上我們要建立一個有向圖模型，UML中的物件（元素）可能與同級元素連接，也可與低級元素相連形成 ......

    uj5u.com 2020-09-10 05:35:54 more
  • 6.1邏輯運算子

    邏輯運算子 1. && 短路與 運算式1 && 運算式2 01.運算式1為true并且運算式2也為true 整體回傳為true 02.運算式1為false，將不會執行運算式2 整體回傳為false 03.只要有一個運算式為false 整體回傳為false 2. || 短路或 運算式1 || 運算式2 ......

    uj5u.com 2020-09-10 05:35:56 more
  • BUAAOO 第四單元 & 課程總結

    1. 第四單元：StarUml檔案決議 本單元采用了圖模型決議UML。 UML檔案可以抽象為圖、子圖、邊的邏輯結構。 在實作中，圖的節點包括類、介面、屬性，子圖包括狀態圖、順序圖等。 采用了三次遍歷UML元素的方法建圖，第一遍遍歷建點，第二、三次遍歷設定屬性、連邊，實作圖物件的初始化。這里借鑒了一些 ......

    uj5u.com 2020-09-10 05:36:06 more
  • 談談我對C# 多型的理解

    面向物件三要素：封裝、繼承、多型。 封裝和繼承，這兩個比較好理解，但要理解多型的話，可就稍微有點難度了。今天，我們就來講講多型的理解。 我們應該經常會看到面試題目：請談談對多型的理解。 其實呢，多型非常簡單，就一句話：呼叫同一種方法產生了不同的結果。 具體實作方式有三種。 一、多載 多載很簡單。 p ......

    uj5u.com 2020-09-10 05:36:09 more
  • Python 資料驅動工具：DDT

    背景 python 的unittest 沒有自帶資料驅動功能。 所以如果使用unittest，同時又想使用資料驅動，那么就可以使用DDT來完成。 DDT是 “Data-Driven Tests”的縮寫。 資料：http://ddt.readthedocs.io/en/latest/ 使用方法 dd. ......

    uj5u.com 2020-09-10 05:36:13 more
  • Python里面的xlrd模塊詳解

    那我就一下面積個問題對xlrd模塊進行學習一下： 1.什么是xlrd模塊？ 2.為什么使用xlrd模塊？ 3.怎樣使用xlrd模塊？ 1.什么是xlrd模塊？ ?python操作excel主要用到xlrd和xlwt這兩個庫，即xlrd是讀excel，xlwt是寫excel的庫。 今天就先來說一下xl ......

    uj5u.com 2020-09-10 05:36:28 more
  • 當我們創建HashMap時，底層到底做了什么？

    jdk1.7中的底層實作程序（底層基于陣列+鏈表） 在我們new HashMap()時，底層創建了默認長度為16的一維陣列Entry[ ] table。當我們呼叫map.put(key1,value1)方法向HashMap里添加資料的時候： 首先，呼叫key1所在類的hashCode()計算key1 ......

    uj5u.com 2020-09-10 05:36:38 more
最新发布
  • 【中介者設計模式詳解】C/Java/JS/Go/Python/TS不同語言實作

    * 中介者模式是一種行為型設計模式，它可以用來減少類之間的直接依賴關系，
    * 將物件之間的通信封裝到一個中介者物件中，從而使得各個物件之間的關系更加松散。
    * 在中介者模式中，物件之間不再直接相互互動，而是通過中介者來中轉訊息。 ......

    uj5u.com 2023-04-20 08:20:47 more
  • 露天煤礦現場調研和交流案例分享

    他們集團的資訊化公司及研究院在一個礦區正在做智能礦山的統一平臺的 試點，專案投資大概1億，包括了礦山的各方面的內容，顯示得我們這次交流有點多余。他們2年前開始做智能礦山的規劃，有很多煤礦行業專家的加持，他們的描述是非常完美，但是去年底應該上線的平臺，現在還沒有看到影子。他們確實有很多場景需求，但是被... ......

    uj5u.com 2023-04-20 08:20:25 more
  • 《社區人員管理》實戰案例設計&個人案例分享

    設計是一個讓人夢想成真程序，開始編碼、測驗、除錯之前進行需求分析和架構設計，才能保證關鍵方面都做正確 ......

    uj5u.com 2023-04-20 08:20:17 more
  • 軟體架構生態化-多角色交付的探索實踐

    作為一個技術架構師，不僅僅要緊跟行業技術趨勢，還要結合研發團隊現狀及痛點，探索新的交付方案。在日常中，你是否遇到如下問題 “ 業務需求排期長研發是瓶頸；非研發角色感受不到研發技改提效的變化；引入ISV 團隊又擔心質量和安全，培訓周期長“等等，基于此我們探索了一種新的技術體系及交付方案來解決如上問題。 ......

    uj5u.com 2023-04-20 08:20:10 more
  • 【中介者設計模式詳解】C/Java/JS/Go/Python/TS不同語言實作

    * 中介者模式是一種行為型設計模式，它可以用來減少類之間的直接依賴關系，
    * 將物件之間的通信封裝到一個中介者物件中，從而使得各個物件之間的關系更加松散。
    * 在中介者模式中，物件之間不再直接相互互動，而是通過中介者來中轉訊息。 ......

    uj5u.com 2023-04-20 08:19:44 more
  • 露天煤礦現場調研和交流案例分享

    他們集團的資訊化公司及研究院在一個礦區正在做智能礦山的統一平臺的 試點，專案投資大概1億，包括了礦山的各方面的內容，顯示得我們這次交流有點多余。他們2年前開始做智能礦山的規劃，有很多煤礦行業專家的加持，他們的描述是非常完美，但是去年底應該上線的平臺，現在還沒有看到影子。他們確實有很多場景需求，但是被... ......

    uj5u.com 2023-04-20 08:19:07 more
  • 《社區人員管理》實戰案例設計&個人案例分享

    設計是一個讓人夢想成真程序，開始編碼、測驗、除錯之前進行需求分析和架構設計，才能保證關鍵方面都做正確 ......

    uj5u.com 2023-04-20 08:18:57 more
  • 軟體架構生態化-多角色交付的探索實踐

    作為一個技術架構師，不僅僅要緊跟行業技術趨勢，還要結合研發團隊現狀及痛點，探索新的交付方案。在日常中，你是否遇到如下問題 “ 業務需求排期長研發是瓶頸；非研發角色感受不到研發技改提效的變化；引入ISV 團隊又擔心質量和安全，培訓周期長“等等，基于此我們探索了一種新的技術體系及交付方案來解決如上問題。 ......

    uj5u.com 2023-04-20 08:18:49 more
  • 05單件模式

    #經典的單件模式 public class Singleton { private static Singleton uniqueInstance; //一個靜態變數持有Singleton類的唯一實體。 // 其他有用的實體變數寫在這里 //構造器宣告為私有，只有Singleton可以實體化這個類! ......

    uj5u.com 2023-04-19 08:42:51 more
  • 【架構與設計】常見微服務分層架構的區別和落地實踐

    軟體工程的方方面面都遵循一個最基本的道理：沒有銀彈，架構分層模型更是如此，每一種都有各自優缺點，所以請根據不同的業務場景，并遵循簡單、可演進這兩個重要的架構原則選擇合適的架構分層模型即可。 ......

    uj5u.com 2023-04-19 08:42:41 more

Copyright © 2010-2020 有解無憂