【數據結構】8. 二叉樹

文章目錄

一、樹的概念及結構
- 1、樹的概念
- 2、樹的相關概念
- 3、樹的表示
- 4、樹的實際運用
二、二叉樹的概念及結構
- 1、二叉樹的概念
- 2、特殊的二叉樹
- 3、二叉樹的性質
- 4、二叉樹的存儲結構
三、二叉樹的順序結構及實現
- 1、二叉樹的順序結構
- 2、堆的概念及結構
- 3、堆的實現
- - 0）準備工作
  - 1）算法
  - - 1.a）數據交換
    - 1.b）向上調整算法
    - 1.c）向下調整算法
    - 1.e）向上/向下調整算法時間復雜度分析
  - 2）初始化和銷毀
  - 3）堆的插入
  - 4）堆的刪除
  - 5）取堆頂元素
  - 6）堆的判空
- 4、堆的應用
- - 1）堆排序
  - 2） TOP-K問題
四、二叉樹鏈式結構的實現
- 1、二叉樹的鏈式結構
- - 0）準備工作
  - 1）二叉樹的手動創建
  - 2）二叉樹的遍歷（前序、中序、后序）
  - 3）節點個數
  - 4）葉子節點個數
  - 5）高度
  - 6）第k層節點數
  - 7）查找值為x的節點
- 2、二叉樹的創建和銷毀
- - 1）前序遍歷數組構建二叉樹
  - 2）二叉樹的銷毀
  - 3）判斷二叉樹是否是完全二叉樹

一、樹的概念及結構

1、樹的概念

樹是一種非線性的數據結構，它是由n個有限結點組成一個具有層次關系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，根在上，葉在下。

樹上有一個特殊的結點，稱為根結點，根結點沒有前驅結點。
除根結點外，其余結點被分成M個互不相交的集合T1、T2、……、Tm，其中每個集合又是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅，但可以有0個或多個后繼。
因此，樹是遞歸定義的。

注意： 在樹形結構中，子樹間是不相交的，并且除根結點外每個結點有且只有一個父結點，否則就不是樹形結構。

2、樹的相關概念

★結點的度： 結點的子樹個數。如上圖：A的度為6。

★葉結點或終端結點： 度為0的結點。如上圖：B、C、H、I等結點為葉結點。
非終端結點或分支結點： 度不為0的結點。如上圖：D、E、F、G等結點為分支結點

★雙親結點或父結點： 含有子結點的結點，這個結點稱為其子結點的父結點。如上圖：A是B的父結點。
★孩子結點或子結點： 結點的子樹的根結點，稱為該結點的子節點。如上圖：B是A的孩子結點。
兄弟結點： 具有相同父結點的結點互稱為兄弟結點；如上圖：B、C是兄弟結點

★樹的度： 樹中所有結點度的最大值。

★樹的高度或深度： 樹中結點的最大層次。如上圖：樹的高度為4。

堂兄弟結點： 雙親在同一層的結點互為堂兄弟。如上圖：H、I互為兄弟結點。

★結點的祖先： 從根到該結點所經分支上的所有結點。如上圖：A->D->H這條分支上，A、D都是H的祖先。
子孫： 以某結點為根的子樹中任一結點都稱為該結點的子孫。如上圖：所有結點都是A的子孫。
森林： 由m棵互不相交的樹的集合稱為森林。

3、樹的表示

樹的結構體中既要保存值域，也要保存結點和結點之間的關系。實際中樹有很多種表示方式：雙親表示法，孩子表示法，孩子雙親表示法以及孩子兄弟表示法等。

下面是最常用的孩子兄弟表示法：

typedef int DataType;
struct TreeNode
{struct TreeNode* leftchild;//左孩子struct TreeNode* rightBrother;//右兄弟DataType val;//值
};

在這里插入圖片描述

4、樹的實際運用

樹在實際中的運用可以用來表示文件系統的目錄的樹結構。

二、二叉樹的概念及結構

1、二叉樹的概念

一顆二叉樹是由n個結點構成的集合，該集合有兩種情況：為空或者由一個根結點加上兩棵被稱為左子樹和右子樹的二叉樹組成。

從上圖可以看出：

①：二叉樹不存在度大于2的結點。
②：二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹。

注意：對于任意的二叉樹都是由以下幾種情況復合而成的：

2、特殊的二叉樹

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

3、二叉樹的性質

①：若規定根結點的層數為1，則一棵非空二叉樹的第 i 層上最多有 2^(i-1)個結點。

②：若規定根結點的層數為1，則深度為 h 的二叉樹的最大結點數是2^h-1。

③★：對任何一棵二叉樹，如果度為0的葉結點個數為 $n_0$ ，度為2的分支結點個數為 $n_2$ ，則有 $n_0$ = $n_2$ +1。注意：總結點N = $n_0$ + $n_1$ + $n_2$ 。（當N為偶數時 $n_1$ =1，否則為0）

④★：若規定根結點的層數為1，具有n個結點的滿二叉樹的深度：h= $log_2 (n+1)$ 。

⑤：對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有結點從0開始編號，則對于下標為 i 的結點有：

若i>0，i 位置結點的雙親下標：(i-1)/2。
若2i+1<n，左孩子下標：2i+1。
若2i+2<n，右孩子下標：2i+2。

練習題

1. 某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（B）  
A. 不存在這樣的二叉樹  
B. 200  
C. 198  
D. 199  解析：根據性質3，葉子結點等于度為2的分支節點+1，也就是200。2. 下列數據結構中，不適合采用順序存儲結構的是（A）  
A. 非完全二叉樹  
B. 堆  
C. 隊列  
D. 棧  解析：非完全二叉樹使用順序存儲會浪費大量的空間。3. 在具有 2n 個結點的完全二叉樹中，葉子結點個數為（A）  
A. n  
B. n+1  
C. n-1  
D. n/2  解析：根據性質3，總結點為偶數，n1=1，N=n0+n1+n2，n0=n2+1，所以N=2n0,葉子結點為n。4. 一棵完全二叉樹的結點數位為 531 個，那么這棵樹的高度為（ B）  
A. 11  
B. 10  
C. 8  
D. 12  解析：根據性質2，當n=9時，滿二叉樹最大有512個節點，多出的節點是下一層的，因此n=10

4、二叉樹的存儲結構

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

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

如圖所示：

下面這里使用數組來存儲非完全二叉樹，可以看到在數組中許多空間都沒有使用到，在數組中其實都是浪費了的。

②：鏈式存儲
二叉樹的鏈式存儲就是使用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址。鏈式結構又分為二叉鏈和三叉鏈，目前一般都是二叉鏈，如紅黑樹等會用到三叉鏈。

typedef int BTDataType;// 二叉鏈
struct BinaryTreeNode4
{struct BinTreeNode* left;//左孩子struct BinTreeNode* right;//右孩子BTDataType data;//值
};// 三叉鏈
struct BinaryTreeNode12
{struct BinTreeNode* parent;//雙親struct BinTreeNode* left;//左孩子struct BinTreeNode* right;//右孩子BTDataType data;//值
};

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

1、二叉樹的順序結構

一般針對完全二叉樹會使用順序結構的數組存儲。
堆在物理層面上是數組，而在邏輯層面上是完全二叉樹，因此可以使用數組來存儲堆。

2、堆的概念及結構

如果有一個關鍵碼的集合K = { $k_0$ ， $k_1$ ， $k_2$ ， …， $k_{n-1}$ }，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數組中，并滿足： $K_i$ <= $K_{2*i+1}$ 且 $K_i$ <= $K_{2*i+2}$ ( $K_i$ >= $K_{2*i+1}$ 且 $K_i$ >= $K_{2*i+2}$ ) 。 i = 0，1，2…，則稱為小堆(或大堆)。
將根結點最大的堆叫做最大堆或大根堆，根結點最小的堆叫做最小堆或小根堆。

堆的性質：
①堆中某個結點的值總是大于等于或小于等于其父結點的值。
②堆是一棵完全二叉樹。

如圖所示：

堆的練習題：

1. 下列關鍵字序列為堆的是：（A）
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

選項A如圖：

2. 已知小根堆為8,15,10,21,34,16,12，刪除關鍵字8之后需重建堆，在此過程中，關鍵字之間的比較次數是（B）。  
A. 1  
B. 2  
C. 3  
D. 4

如圖所示：

3. 最小堆[0,3,2,5,7,4,6,8]，在刪除堆頂元素0之后，其結果是（）  
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]

如圖所示：

3、堆的實現

0）準備工作

實現堆之前我們先創建三個文件：
Heap.h：庫函數頭文件的聲明，堆結構體的定義，方法的聲明。
Heap.c：方法的實現。
test.c：方法的測試。

先來實現Heap.h文件：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;//數組int size;int capacity;
}HP;//算法的聲明
//交換數據
void Swap(HPDataType* p1, HPDataType* p2);//向上調整算法
void AdjustUP(HPDataType* a, int child);//向下調整算法
void AdjustDown(HPDataType* a, int n, int parent);//方法的聲明
//堆的初始化與銷毀
void HPInit(HP* php);
void HPDestroy(HP* php);//堆的插入
void HPPush(HP* php, HPDataType x);//堆的刪除
void HPPop(HP* php);//取堆頂元素
HPDataType HPTop(HP* php);//堆的判空
bool HPEmpty(HP* php);//堆的排序
void HPSort(HPDataType* a, int n);

1）算法

1.a）數據交換

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

1.b）向上調整算法

在這里插入圖片描述

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

下面這條代碼是創建小堆的判斷條件：只要父親大于孩子，就交換順序。

if (a[child] < a[parent])

只要改變判斷條件：只要父親小于孩子，就交換順序。就是創建大堆。

if (a[child] > a[parent])

1.c）向下調整算法

在這里插入圖片描述

void AdjustDown(HPDataType* 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 = 2 * parent + 1;}else{break;}}
}

如果想要建大堆，那么上述代碼要修改的有兩點：
①：先找到較大的孩子。
②：改變判斷條件。

1.e）向上/向下調整算法時間復雜度分析

在這里插入圖片描述

由上述公式推導得出

向下調整算法的時間復雜度為：O(N）
向上調整算法的時間復雜度為：0(N*logN)

2）初始化和銷毀

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

再在test.c中進行測試：

3）堆的插入

在這里插入圖片描述

在數據插入之后再調用向上調整算法。

void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newcapacity;}//直接插入php->a[php->size] = x;php->size++;//向上調整AdjustUp(php->a, php->size - 1);
}

再進行測試：

void test()
{int a[] = { 4,2,8,1,5,6,9,7,3,2 };int len = sizeof(a) / sizeof(a[0]);HP hp;HPInit(&hp);//依次將數組元素插入到堆上for (int i = 0; i < len; i++){HPPush(&hp, a[i]);}
}int main()
{test();return 0;
}

調試結果：

邏輯結構如圖所示：

4）堆的刪除

刪除堆是刪除堆頂的數據，將堆頂的數據跟最后的數據先交換，然后刪除數組最后一個數據（原來的堆頂），再進行向下調整算法。

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

再進行測試：

void test()
{int a[] = { 4,2,8,1,5,6,9,7,3,2 };int len = sizeof(a) / sizeof(a[0]);HP hp;HPInit(&hp);//依次將數組元素插入到堆上for (int i = 0; i < len; i++){HPPush(&hp, a[i]);}HPPop(&hp);HPPop(&hp);HPDestroy(&hp);
}int main()
{test();return 0;
}

調試結果：

5）取堆頂元素

直接返回堆頂元素即可。

HPDataType* HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

再進行測試；

void test()
{int a[] = { 4,2,8,1,5,6,9,7,3 };int len = sizeof(a) / sizeof(a[0]);HP hp;HPInit(&hp);//依次將數組元素插入到堆上for (int i = 0; i < len; i++){HPPush(&hp, a[i]);}printf("%d\n", HPTop(&hp));HPPop(&hp);printf("%d\n", HPTop(&hp));HPDestroy(&hp);
}int main()
{test();return 0;
}

運行結果：
在這里插入圖片描述

6）堆的判空

直接判斷size是否等于0即可。

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

再進行測試依次取出所有堆頂的元素：

void test()
{int a[] = { 4,2,8,1,5,6,9,7,3 };int len = sizeof(a) / sizeof(a[0]);HP hp;HPInit(&hp);//依次將數組元素插入到堆上for (int i = 0; i < len; i++){HPPush(&hp, a[i]);}while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);}
}int main()
{test();return 0;
}

運行結果：
在這里插入圖片描述

4、堆的應用

1）堆排序

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

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

建堆使用向上或者向下調整算法都可以實現，向上調整算法其實套用的就是建堆的方法，如果使用向下調整算法建堆，時間復雜度更小，效率會更高。

在這里插入圖片描述
②利用堆刪除思想來進行排序。
在堆中被刪除的數據，實際上在數組中還存在，并且已經處于有序狀態。

void HPSort(HPDataType* a, int n)
{//建堆   //向上調整//for (int i = 1; i < n; i++)//{//	AdjustUp(a, i);//}//向下調整   O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//堆刪除   O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

再進行測試：

int main()
{int arr[] = { 4,2,8,1,5,6,9,7,3 };int len = sizeof(arr) / sizeof(arr[0]);HPSort(arr, len);for (int i = 0; i < len; i++){printf("%d ", arr[i]);}return 0;
}

運行結果：
在這里插入圖片描述

堆排序的時間復雜度分析：
如果建堆時采用向上調整算法，那么堆排序的時間復雜度為：O（N* $log^N$ ）。相比于冒泡排序的時間復雜度O(N²)已經大大減少了。

如果建堆時采用向下調整算法，時間復雜度將銳減為O(N)，效率大大提升。

2） TOP-K問題

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

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

②用剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素。將剩余N-K個元素依次與堆頂元素比完之后，堆中剩余的K個元素就是所求的前K個最小或者最大的元素。

void testHeap2()
{int k;printf("請輸入k:");scanf("%d", &k);//開辟k個大小的數組int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail");return;}//打開文件const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}//讀取文件前k個數for (int i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);}//建k個數的小堆  (向下調整建堆) O(N)for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kminheap, k, i);}//讀取剩下的N-K個數，并依次與堆頂元素比較int x = 0;while (fscanf(fout, "%d", &x) > 0){if (x > kminheap[0]){kminheap[0] = x;AdjustDown(kminheap, k, 0);}}//打印printf("最大的前%d個數：", k);for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}printf("\n");
}

接著再進行測試：
首先創建一個100000個隨機整數的文件data.txt

void CreateNDate()
{//造數據int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen fail");return;}for (int i = 0; i < n; i++){//生成10000000以內的數int x = (rand() + i) % 10000000;fprintf(fin, "%d\n", x);}fclose(fin);
}

為了方便我們查看是否查找正確，我們可以在data.txt中將部分數據改得突出一點。

現在就可以測試了。

int main()
{//CreateNDate();testHeap2();return 0;
}

運行結果：
在這里插入圖片描述

四、二叉樹鏈式結構的實現

1、二叉樹的鏈式結構

0）準備工作

我們在這里創建3個文件：
BT.h：二叉樹的定義，方法的聲明
BT.c：方法的實現
test.c：測試

先在BT.h中實現二叉樹的定義以及方法的聲明:

#include<stdio.h.>
#include<stdlib.h>typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
} BTNode;//手動創建二叉樹
BTNode* CreateBinaryTree();//前序
void PrevOrder(BTNode* root);//中序
void InOrder(BTNode* root);//后序
void PostOrder(BTNode* root);

1）二叉樹的手動創建

在手動創建二叉樹之前，需要先編寫創建二叉樹單獨節點的函數。

BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}

接著再進行創建：

BTNode* CreateBinaryTree()
{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;
}

創建的二叉樹的邏輯結構如下所示：

2）二叉樹的遍歷（前序、中序、后序）

三種遍歷如下所示：

//前序
void PrevOrder(BTNode* root)
{//訪問到空節點if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}//中序
void InOrder(BTNode* root)
{//訪問到空節點if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}//后序
void PostOrder(BTNode* root)
{//訪問到空節點if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

再來進行測試：

int main()
{//創建一顆二叉樹BTNode* root = CreateBinaryTree();//前序printf("前序遍歷：");PrevOrder(root);printf("\n");//中序printf("中序遍歷：");InOrder(root);printf("\n");//后序printf("后序遍歷：");PostOrder(root);printf("\n");return 0;
}

運行結果：

因此遍歷節點的先后順序如下所示：

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

3）節點個數

//節點個數
int TreeSize(BTNode* root)
{return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}

再進行測試；

int main()
{BTNode* root = CreateBinaryTree();printf("節點個數：%d\n", TreeSize(root));return 0;
}

運行結果：
在這里插入圖片描述

4）葉子節點個數

在這里插入圖片描述

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

再進行測試：

int main()
{BTNode* root = CreateBinaryTree();printf("葉子節點個數：%d\n", TreeLeafSize(root));return 0;
}

運行結果：
在這里插入圖片描述

5）高度

在這里插入圖片描述

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

再進行測試：

int main()
{BTNode* root = CreateBinaryTree();printf("二叉樹的高度為：%d\n", TreeHeight(root));return 0;
}

運行結果：
在這里插入圖片描述
這里測試的二叉樹依舊是之前的創建的二叉樹，高度為3，上面的圖片僅作方法的演示。

6）第k層節點數

在這里插入圖片描述

int TreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;//子問題return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

進行測試：

int main()
{BTNode* root = CreateBinaryTree();printf("二叉樹第3層的節點個數為：%d\n", TreeLevelKSize(root,3));return 0;
}

運行結果：
在這里插入圖片描述

7）查找值為x的節點

在這里插入圖片描述

BTNode* TreeFind(BTNode* root,int x)
{if (root == NULL)return NULL;if (root->data == x)return root;//先找左子樹BTNode* ret1 = TreeFind(root->left, x);//找到了if (ret1)return ret1;//再找右子樹BTNode* ret2 = TreeFind(root->right, x);//找到了if (ret2)return ret2;//遍歷整個二叉樹都沒有找到return NULL;
}

再進行測試：

int main()
{BTNode* root = CreateBinaryTree();int k = 0;printf("請輸入你要查找的值:");scanf("%d", &k);int find = TreeFind(root, k);if (find)printf("找到了！\n");elseprintf("沒有找到...\n");return 0;
}

運行結果：

2、二叉樹的創建和銷毀

1）前序遍歷數組構建二叉樹

例如：通過前序遍歷的數組"ABD##E#H##CF##G##"構建二叉樹。

在這里插入圖片描述

 BTNode* CreateTree(char* a, int* pi){if (a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->val = a[*pi];(*pi)++;root->left = CreateTree(a, pi);root->right = CreateTree(a, pi);return root;}

我們可以通過前序遍歷這個二叉樹并打印，觀察是否成功創建：

 void PrevPrint(BTNode* root){if (root == NULL){printf("# ");return;}printf("%c ", root->val);PrevPrint(root->left);PrevPrint(root->right);}int main(){char a[30] = "ABD##E#H##CF##G## ";int i = 0;BTNode* root = CreateTree(a, &i);PrevPrint(root);return 0;}

運行結果：
在這里插入圖片描述

可以看到已經成功創建二叉樹。

2）二叉樹的銷毀

在這里插入圖片描述

 void TreeDestroy(BTNode* root){if (root == NULL)return;TreeDestroy(root->left);TreeDestroy(root->right);free(root);}

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

在這里插入圖片描述

 bool TreeComplete(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);//遇到非空->不是完全二叉樹  直接銷毀返回falseif (front){QueueDestroy(&q);return false;}}//是完全二叉樹QueueDestroy(&q);return true;}