1. 前言
前面學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)的幾種結(jié)構(gòu)，順序表，鏈表，棧和隊(duì)列等，今天我們來學(xué)習(xí)一種非線性的數(shù)據(jù)結(jié)構(gòu)——樹。由于二叉樹是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)重點(diǎn)和難點(diǎn)，所以本文著重介紹二叉樹的相關(guān)概念和性質(zhì)，以及二叉樹的應(yīng)用。
2. 樹的概念及結(jié)構(gòu)
2.1 樹的概念
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。
注意事項(xiàng)：
1.樹是遞歸定義的
2.樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)
2.2 樹的相關(guān)概念
如果有一棵樹如下圖所示：
那么它有以下概念：
節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度； 如上圖：A的為6
葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)； 如上圖：B、C、H、I…等節(jié)點(diǎn)為葉節(jié)點(diǎn)
非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)； 如上圖：D、E、F、G…等節(jié)點(diǎn)為分支節(jié)點(diǎn)
雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)
孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)； 如上圖：B是A的孩子節(jié)點(diǎn)
兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)； 如上圖：B、C是兄弟節(jié)點(diǎn)
樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度； 如上圖：樹的度為6
節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
樹的高度或深度：樹中節(jié)點(diǎn)的最大層次； 如上圖：樹的高度為4
堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為兄弟節(jié)點(diǎn)
節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先
子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫
森林：由m（m>0）棵互不相交的樹的集合稱為森林；
2.3 樹的表示
樹在存儲(chǔ)時(shí)，既要保存數(shù)據(jù)，也要保存結(jié)點(diǎn)與結(jié)點(diǎn)之間的關(guān)系，而且實(shí)際中樹有許多種表示方法，如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。下面我們就介紹最常用的孩子兄弟表示法。
typedef int TreeDataType;
struct TreeNode
{
TreeDataType data;//結(jié)點(diǎn)的數(shù)據(jù)域
struct TreeNode* FirstChild;//指向其第一個(gè)孩子結(jié)點(diǎn)
struct TreeNode* NextBrother;//指向其下一個(gè)兄弟結(jié)點(diǎn)
};
3. 二叉樹的概念
一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合:
1.或者為空
2.由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的二叉樹組成
如下圖所示就是一顆二叉樹：
從上圖我們可以看出：
1.二叉樹不存在度大于2的結(jié)點(diǎn)
2.二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
3.1 特殊二叉樹
二叉樹中還有倆種特殊的二叉樹：
1.滿二叉樹：一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。也就是說，如果一個(gè)二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是2^k - 1，則它就是滿二叉樹。
2.完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹。要注意的是滿二叉樹是一種特殊的完全二叉樹。
3.2 二叉樹的性質(zhì)
1.若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1)個(gè)結(jié)點(diǎn)
2.若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是2^h-1
3.對(duì)任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為n0, 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為n2,則有n0 = n2 + 1
4.若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h = log2(n+1)
5.對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開始編號(hào)，
則對(duì)于序號(hào)為i的結(jié)點(diǎn)有：
（1）若i > 0，i位置節(jié)點(diǎn)的雙親序號(hào)：(i - 1) / 2；若i = 0，則i為根節(jié)點(diǎn)編號(hào)，無雙親節(jié)點(diǎn)
（2）若2i + 1 < n，左孩子序號(hào)：2i + 1，若2i + 1 >= n則無左孩子
（3）若2i + 2 < n，右孩子序號(hào)：2i + 2，若2i + 2 >= n則無右孩子
4. 二叉樹的順序存儲(chǔ)
順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來存儲(chǔ)，一般使用數(shù)組只適合表示完全二叉樹，因?yàn)椴皇峭耆鏄鋾?huì)有空間的浪費(fèi)。
二叉樹順序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹。
而現(xiàn)實(shí)中只有堆才會(huì)使用數(shù)組來存儲(chǔ)。
4.1 堆的概念
所有元素按完全二叉樹的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中，將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。
堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
堆總是一棵完全二叉樹。
4.2 堆的實(shí)現(xiàn)
4.2.1 堆的結(jié)點(diǎn)定義
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
4.2.2 堆的打印和銷毀
打?。?/p>
void HeapPrint(HP* php)
{
assert(php);
int i = 0;
for (i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
銷毀：
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
4.2.3 堆的插入
先插入一個(gè)數(shù)據(jù)到數(shù)組的尾上，再進(jìn)行向上調(diào)整算法，直到滿足大根堆或者小根堆。
向上調(diào)整算法：以小根堆來舉例，從該結(jié)點(diǎn)開始向上找父結(jié)點(diǎn)，如果該結(jié)點(diǎn)小于父結(jié)點(diǎn)，就把該結(jié)點(diǎn)和父結(jié)點(diǎn)交換，繼續(xù)向上調(diào)整，直到滿足小根堆。
插入：
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("malloc");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
向上調(diào)整算法：
void AdjustUp(HPDataType* 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 Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
4.2.4 堆的刪除
刪除堆是刪除堆頂?shù)臄?shù)據(jù)，將堆頂?shù)臄?shù)據(jù)根最后一個(gè)數(shù)據(jù)一換，然后刪除數(shù)組最后一個(gè)數(shù)據(jù)，再進(jìn)行向下調(diào)整算法。
向下調(diào)整算法：以小根堆來舉例，從該結(jié)點(diǎn)開始向下找子結(jié)點(diǎn)，如果子結(jié)點(diǎn)小于該結(jié)點(diǎn)，就把子結(jié)點(diǎn)和該結(jié)點(diǎn)交換，再繼續(xù)向下調(diào)整，直到滿足小根堆
刪除：
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);
}
向下調(diào)整算法：
void AdjustDown(HPDataType* a, int size, int parent)
{
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;
}
}
}
4.2.5 取堆頂數(shù)據(jù)
堆頂元素就是數(shù)組下標(biāo)為0的元素
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
4.2.6 堆的判空
size為0即為空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
4.2.7 堆的數(shù)據(jù)個(gè)數(shù)
size的大小就是數(shù)據(jù)個(gè)數(shù)
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
4.3 堆的應(yīng)用
4.3.1 堆排序
堆排序即利用堆的思想來進(jìn)行排序，總共分為兩個(gè)步驟：
1.建堆
升序：建大堆
降序：建小堆
2.利用堆刪除思想來進(jìn)行排序
void HeapSort(int* arr, int size)
{
//排升序建大堆，排降序建小堆
//向上調(diào)整建堆O(N*logN)
//int i = 0;
//for (i = 1; i < size; i++)
//{
// AdjustUp(arr, i);
//}
//向下調(diào)整建堆O(N)
int i = 0;
for (i = (size - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, size, i);
}
int end = size - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, end, 0);
end--;
}
}
int main()
{
int arr[10] = { 23,45,48,123,12,49,80,15,5,35 };
HeapSort(arr, 10);
int i = 0;
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
4.3.2 TOP-K問題
TOP-K問題：即求數(shù)據(jù)結(jié)合中前K個(gè)最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。
比如：專業(yè)前10名、世界500強(qiáng)、富豪榜、游戲中前100的活躍玩家等。
思路：
1.用數(shù)據(jù)集合中前K個(gè)元素來建堆
求前k個(gè)最大的元素，則建小堆
求前k個(gè)最小的元素，則建大堆
2.用剩余的N - K個(gè)元素依次與堆頂元素來比較，不滿足則替換堆頂元素
將剩余N - K個(gè)元素依次與堆頂元素比完之后，堆中剩余的K個(gè)元素就是所求的前K個(gè)最小或者最大的元素。
void PrintTopK(int* a, int n, int k)
{
//1.建堆--用a中前k個(gè)元素建堆
int* kMaxHeap = (int*)malloc(sizeof(int)*k);
assert(kMaxHeap);
int i = 0;
for (i = 0; i < k; i++)
{
kMaxHeap[i] = a[i];
}
for (i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(kMaxHeap, k, i);
}
//2.將剩余n-k個(gè)元素依次與堆頂元素交換，不滿則則替換
int j = 0;
for (j = k; j < n; j++)
{
if (a[j] > kMaxHeap[0])
{
kMaxHeap[0] = a[j];
AdjustDown(kMaxHeap, k, 0);
}
}
for (i = 0; i < k; i++)
{
printf("%d ", kMaxHeap[i]);
}
}
void TestTopk()
{
int n = 10000;
int* a = (int*)malloc(sizeof(int) * n);
srand(time(0));
for (int 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);
}
int main()
{
TestTopk();
return 0;
}
5. 二叉樹的鏈?zhǔn)酱鎯?chǔ)
二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。
通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。
鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈。
5.1 鏈?zhǔn)蕉鏄涞慕Y(jié)點(diǎn)定義
typedef int BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType data;
}BTNode;
5.2 結(jié)點(diǎn)創(chuàng)建
BTNode* CreatBTNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
assert(node);
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
由于二叉樹的創(chuàng)建比較復(fù)雜，所以下面我們來手動(dòng)模擬一個(gè)簡單的二叉樹，便于后邊操作的實(shí)現(xiàn)
5.3 模擬創(chuàng)建二叉樹
BTNode* CreatBinaryTree()
{
BTNode* node1 = CreatBTNode(1);
BTNode* node2 = CreatBTNode(2);
BTNode* node3 = CreatBTNode(3);
BTNode* node4 = CreatBTNode(4);
BTNode* node5 = CreatBTNode(5);
BTNode* node6 = CreatBTNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}
5.4 二叉樹的遍歷
二叉樹的遍歷有：前序/中序/后序/層序的遞歸結(jié)構(gòu)遍歷：
1.前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。
2.中序遍歷(Inorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中（間）。
3.后序遍歷(Postorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。
4.層序遍歷(Level Traversal)——從所在二叉樹的根結(jié)點(diǎn)出發(fā)，首先訪問第一層的樹根結(jié)點(diǎn)，然后從左到右訪問第2層上的結(jié)點(diǎn)，接著是第三層的結(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷。
5.4.1 前序遍歷
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
5.4.2 中序遍歷
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
5.4.3 后序遍歷
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("# ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
5.4.4 層序遍歷
層序遍歷稍微復(fù)雜一點(diǎn)，需要隊(duì)列來實(shí)現(xiàn)，我們這里就之前使用之前創(chuàng)建好的隊(duì)列，不再過多展示，核心思路是：先判斷該結(jié)點(diǎn)是不是空，如果不是就進(jìn)隊(duì)，再判斷隊(duì)是不是空，如果不是先打印出此時(shí)隊(duì)頭元素，然后刪除隊(duì)頭元素，接下來再分別判斷打印的隊(duì)頭元素的左孩子和右孩子是不是為空，不是空就繼續(xù)入隊(duì)。這樣循環(huán)迭代即層序遍歷。
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
printf("%d ", front->data);
QueuePop(&q);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
QueueDestroy(&q);
}
5.5 二叉樹結(jié)點(diǎn)個(gè)數(shù)及高度等操作
5.5.1 二叉樹的結(jié)點(diǎn)個(gè)數(shù)
因?yàn)槎鏄涞淖笞訕浜陀易訕涠伎梢苑謩e看成單獨(dú)的二叉樹，所以核心思路是遞歸計(jì)算左子樹和右子樹的結(jié)點(diǎn)個(gè)數(shù)，最后返回再加1就是該二叉樹的結(jié)點(diǎn)個(gè)數(shù)。
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
5.5.2 二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)
左右子樹都為空的結(jié)點(diǎn)就是葉子結(jié)點(diǎn)，這里也采用遞歸的思路，把二叉樹分為左子樹和右子樹，左子樹也可以分為左子樹和右子樹，遞歸計(jì)算并返回即可求的整棵樹的葉子結(jié)點(diǎn)個(gè)數(shù)。
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);
}
5.5.3 二叉樹第k層的結(jié)點(diǎn)個(gè)數(shù)
這里的思路是，求根結(jié)點(diǎn)的第k層的結(jié)點(diǎn)個(gè)數(shù)，可以轉(zhuǎn)換成求該結(jié)點(diǎn)的左孩子的第k-1層的結(jié)點(diǎn)個(gè)數(shù)+該結(jié)點(diǎn)的右孩子的第k-1層的結(jié)點(diǎn)個(gè)數(shù)，遞歸下去，結(jié)束后返回的即為根結(jié)點(diǎn)第k層的結(jié)點(diǎn)個(gè)數(shù)。
int BinaryTreeLevelKSize(BTNode* root, int k)
{
assert(k >= 1);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
5.5.4 查找二叉樹中值為x的結(jié)點(diǎn)
這里的思路是，如果該結(jié)點(diǎn)就是要求的結(jié)點(diǎn)，直接返回該結(jié)點(diǎn)，如果不是就遞歸查找該結(jié)點(diǎn)的左子樹和右子樹，找到就返回。
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1)
{
return ret1;
}
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2)
{
return ret2;
}
return NULL;
}
5.5.5 計(jì)算二叉樹的深度
二叉樹的深度就是該二叉樹的左子樹和右子樹的最大深度再+1，這里的思路是，遞歸計(jì)算左子樹的深度和右子樹的深度，每次返回都是以某個(gè)結(jié)點(diǎn)為根的二叉樹的深度，最后返回的就是該二叉樹的深度。
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;
}
5.5.6 判斷是否為完全二叉樹
這里也要用到隊(duì)列，核心思路是利用完全二叉樹的性質(zhì)，完全二叉樹的非空結(jié)點(diǎn)一定是連在一起的，一旦出現(xiàn)空結(jié)點(diǎn)，則空結(jié)點(diǎn)后面的所有結(jié)點(diǎn)都應(yīng)該為空，如果還有非空結(jié)點(diǎn)，就不是完全二叉樹。文章來源：http://www.zghlxwxcb.cn/news/detail-420279.html
int BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
else
{
break;
}
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
6. 結(jié)尾
到這里，二叉樹的概念及二叉樹順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)和應(yīng)用就介紹完了，二叉樹作為數(shù)據(jù)結(jié)構(gòu)中的重點(diǎn)和難點(diǎn)需要反復(fù)學(xué)習(xí)，理解透徹，非?？简?yàn)大家的理解能力和基本功，本人也是一個(gè)初學(xué)者，文中難免有很多地方出現(xiàn)錯(cuò)誤和紕漏，此文僅供大家學(xué)習(xí)和參考。如果本文對(duì)大家學(xué)習(xí)二叉樹有幫助的話，博主感到非常榮幸。
最后，感謝各位大佬的耐心閱讀和支持，覺得本篇文章寫的不錯(cuò)的朋友可以三連關(guān)注支持一波，如果有什么問題或者本文有錯(cuò)誤的地方大家可以私信我，也可以在評(píng)論區(qū)留言討論，再次感謝各位。文章來源地址http://www.zghlxwxcb.cn/news/detail-420279.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)（C語言實(shí)現(xiàn)）——二叉樹的概念及二叉樹順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（堆排序+TOP-K問題+鏈?zhǔn)蕉鏄湎嚓P(guān)操作）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
