?前言

我們已經(jīng)學(xué)過了順序表、鏈表、棧和隊列這些屬于線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)，那么下面我們就要學(xué)習(xí)我們第一個非線性結(jié)構(gòu)，非線性結(jié)構(gòu)又有哪些值得我們使用的呢？那么接下來我們就將談?wù)剺涞母拍盍恕?/p>

1.樹的概念與結(jié)構(gòu)

1.1樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

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

?注意：樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)，那樣可能是圖了，后續(xù)還會學(xué)習(xí)。

1.2樹的相關(guān)概念

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

1.3樹的表示

樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要存儲表示起來就比較麻煩了，既要保存值域，也要保存結(jié)點和結(jié)點之間的關(guān)系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。

?typedef int DataType;
struct Node
{
?? ?struct Node* firstchild; ? //第一個孩子節(jié)點
?? ?struct Node* pnextbrother; ?//指向其下一個兄弟節(jié)點
?? ?DataType data;?? ??? ??? ??? ?//結(jié)點中的數(shù)據(jù)域
};

?

1.4樹在實際中的運(yùn)用（表示文件系統(tǒng)的目錄樹結(jié)構(gòu)）

Linux中的文件目錄就是按照一種樹形結(jié)構(gòu)來實現(xiàn)的。

2.二叉樹的概念與結(jié)構(gòu)

2.1概念

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

• 或者為空
• 由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉樹組成

?從上圖可以明顯看出：

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

2.2現(xiàn)實中的二叉樹

簡直是大自然的奇跡，相信當(dāng)我們程序員看到這樣一顆樹，呼之欲出的就是二叉樹啦。?

2.3特殊的二叉樹

1. 滿二叉樹：一個二叉樹，如果每一個層的結(jié)點數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為K，且結(jié)點總數(shù)是 2^k-1，則它就是滿二叉樹。
2. 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。

?

2.4二叉樹的性質(zhì)

1. 若規(guī)定根節(jié)點的層數(shù)為1，則一棵非空二叉樹的第i層上最多有 2^（i-1）個結(jié)點.
2. 若規(guī)定根節(jié)點的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點數(shù)是2^h-1.
3. 對任何一棵二叉樹, 如果度為0其葉結(jié)點個數(shù)為n0 , 度為2的分支結(jié)點個數(shù)為n2,則有 n0＝n2 ＋1
4. 若規(guī)定根節(jié)點的層數(shù)為1，具有n個結(jié)點的滿二叉樹的深度，h=log2（n+1)
是log以2為底n+1的對數(shù)。
5. 對于具有n個結(jié)點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點從0開始編號，則對于序號為i的結(jié)點有：

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

1. 某二叉樹共有 399 個結(jié)點，其中有 199 個度為 2 的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)為（ ）
A 不存在這樣的二叉樹
B 200
C 198
D 199
2.下列數(shù)據(jù)結(jié)構(gòu)中，不適合采用順序存儲結(jié)構(gòu)的是（ ）
A 非完全二叉樹
B 堆
C 隊列
D 棧
3.在具有 2n 個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為（ ）
A n
B n+1
C n-1
D n/2
4.一棵完全二叉樹的節(jié)點數(shù)位為531個，那么這棵樹的高度為（ ）
A 11
B 10
C 8
D 12
5.一個具有767個節(jié)點的完全二叉樹，其葉子節(jié)點個數(shù)為（）
A 383
B 384
C 385
D 386
答案：
1.B
2.A
3.A
4.B
5.B

2.5二叉樹的存儲結(jié)構(gòu)

二叉樹一般可以使用兩種存儲方式，一種是順序存儲、一種是鏈?zhǔn)酱鎯Α?/p>

2.5.1順序存儲

順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。

而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲，關(guān)于堆我們后面的章節(jié)會專門講解。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。

2.5.2鏈?zhǔn)酱鎯?/h4>

二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。 通常的方法是鏈表中每個結(jié)點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址 。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們學(xué)習(xí)中一般都是二叉鏈，后面課程學(xué)到高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹等會用到三叉鏈。

?

?typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
?? ?struct BinTreeNode* pLeft; // 指向當(dāng)前節(jié)點左孩子
?? ?struct BinTreeNode* pRight; // 指向當(dāng)前節(jié)點右孩子
?? ?BTDataType data; // 當(dāng)前節(jié)點值域
};
// 三叉鏈
struct BinaryTreeNode
{
?? ?struct BinTreeNode* pParent; // 指向當(dāng)前節(jié)點的雙親
?? ?struct BinTreeNode* pLeft; // 指向當(dāng)前節(jié)點左孩子
?? ?struct BinTreeNode* pRight; // 指向當(dāng)前節(jié)點右孩子
?? ?BTDataType data; // 當(dāng)前節(jié)點值域
};

3.二叉樹的順序結(jié)構(gòu)及其實現(xiàn)代碼

3.1二叉樹的順序結(jié)構(gòu)

普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲?，F(xiàn)實中我們通常把堆(一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。

3.2堆的概念及結(jié)構(gòu)

如果有一個關(guān)鍵碼的集合K = { k0，k1 ，k2 ，…，kn-1?}，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數(shù)組中，并滿足：Ki <= K2*i+1且 Ki<=K2*i+2? (Ki >= K2*i+1且 Ki>=K2*i+2,K后內(nèi)容均為下標(biāo)?) i = 0，1，2…，則稱為小堆(或大堆)。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。

?堆的性質(zhì)：

• 堆總是一棵完全二叉樹。

• 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；

?

?1.下列關(guān)鍵字序列為堆的是：（）
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，刪除關(guān)鍵字 8 之后需重建堆，在此過程中，關(guān)鍵字之間的比較次數(shù)是（）。
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之后，其結(jié)果是（）
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

3.3堆的實現(xiàn)

3.3.1堆的調(diào)整算法

向下調(diào)整

現(xiàn)在我們給出一個數(shù)組，邏輯上看做一顆完全二叉樹。我們通過從根節(jié)點開始的向下調(diào)整算法可以把它調(diào)整成一個小堆。向下調(diào)整算法有一個前提：左右子樹必須是一個堆，才能調(diào)整。

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

?

?向下調(diào)整算法代碼實現(xiàn)：

void Swap(HPDatetype* pa, HPDatetype* pb)
{HPDatetype tmp = *pa;*pa = *pb;*pb = tmp;
}
void AdjustDown(HPDatetype* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){//若假設(shè)的左孩子小，若假設(shè)是錯的，更新一下if (child + 1 < size && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else{break;}}
}

?向上與向下調(diào)整算法類似。

void Swap(HPDatetype* pa, HPDatetype* pb)
{HPDatetype tmp = *pa;*pa = *pb;*pb = tmp;
}
void AdjustUp(HPDatetype* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}}

3.3.2堆的創(chuàng)建

下面我們給出一個數(shù)組，這個數(shù)組邏輯上可以看做一顆完全二叉樹，但是還不是一個堆，現(xiàn)在我們通過算法，把它構(gòu)建成一個堆。根節(jié)點左右子樹不是堆，我們怎么調(diào)整呢？這里我們從倒數(shù)的第一個非葉子節(jié)點的子樹開始調(diào)整，一直調(diào)整到根節(jié)點的樹，就可以調(diào)整成堆。

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

?

3.3.3堆建時間復(fù)雜度

因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明(時間復(fù)雜度本來看的就是近似值，多幾個節(jié)點不影響最終結(jié)果)：

故建堆的時間復(fù)雜度為O（n）。?

3.3.4堆的插入

先插入一個數(shù)到數(shù)組的尾上，再進(jìn)行向上調(diào)整算法，直到滿足堆。

代碼實現(xiàn)：

void HeapPush(HP* php, int x)
{assert(php);if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : sizeof(php->a) * 2;HPDatetype * tmp = (HPDatetype*)realloc(php->a, newcapacity*sizeof(HPDatetype));if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

3.3.5堆的刪除

刪除堆是刪除堆頂?shù)臄?shù)據(jù)，將堆頂?shù)臄?shù)據(jù)跟最后一個數(shù)據(jù)一換，然后刪除數(shù)組最后一個數(shù)據(jù)，再進(jìn)行向下調(diào)整算法。

代碼實現(xiàn)：

void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

3.3.6堆的代碼實現(xiàn)

Heap.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>typedef int HPDatetype;typedef struct Heap
{int* a;int size;int capacity;
}HP;//堆的初始化
void HeapIint(HP* php);//堆的銷毀
void HeapDestroy(HP* php);//堆的插入
void HeapPush(HP* php, int child);//堆的刪除
void HeapPop(HP* php);//取堆頂元素
HPDatetype HeapTop(HP* php);//堆的數(shù)據(jù)個數(shù)
int HeapSize(HP* php);//堆的判空
bool HeapEmpty(HP* php);

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1#include"Heap.h"void HeapIint(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}
void Swap(HPDatetype* pa, HPDatetype* pb)
{HPDatetype tmp = *pa;*pa = *pb;*pb = tmp;
}
void AdjustUp(HPDatetype* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}}
void HeapPush(HP* php, int x)
{assert(php);if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : sizeof(php->a) * 2;HPDatetype * tmp = (HPDatetype*)realloc(php->a, newcapacity*sizeof(HPDatetype));if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HPDatetype* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){//若假設(shè)的左孩子小，若假設(shè)是錯的，更新一下if (child + 1 < size && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else{break;}}
}
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}HPDatetype HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}int HeapSize(HP* php)
{assert(php);return php->size;
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

3.4堆的應(yīng)用

3.4.1 堆排序

1.建堆

根據(jù)升序和降序來決定是建大堆還是建小堆，

升序建大堆，反之建小堆。

2.利用堆刪除思想來進(jìn)行排序

?代碼實現(xiàn)堆排序：

void HeapSort(int* a, int n)
{//升序//建大堆//降序//建小堆/*for (int i = 1; i < n; i++){AdjustUp(a, i);}*/for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//選數(shù)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

3.4.2 TOP-K問題

TOP-K問題：即求數(shù)據(jù)結(jié)合中前K個最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。
比如：專業(yè)前10名、世界500強(qiáng)、富豪榜、游戲中前100的活躍玩家等。
對于Top-K問題，能想到的最簡單直接的方式就是排序，但是：如果數(shù)據(jù)量非常大，排序就不太可取了(可能數(shù)據(jù)都不能一下子全部加載到內(nèi)存中)。最佳的方式就是用堆來解決，基本思路如下：

1. 用數(shù)據(jù)集合中前K個元素來建堆

前k個最大的元素，則建小堆
前k個最小的元素，則建大堆

2. 用剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素

將剩余N-K個元素依次與堆頂元素比完之后，堆中剩余的K個元素就是所求的前K個最小或者最大的元素。

代碼實現(xiàn)：?

void CreateNDate()
{// 造數(shù)據(jù)int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void PrintTopK(int k)
{FILE* fout = fopen("data.txt", "r");if (fout == NULL){perror("fopen fail");return;}//建立k個數(shù)的小堆int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc fail");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);AdjustUp(minheap,i);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minheap[0]){minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}printf("\n");free(minheap);minheap = NULL;fclose(fout);
}int main()
{int k = 5;CreateNDate();PrintTopK(k);return 0;
}