數據結構c版（2）—

本章我們來了解一下二叉樹這一概念。

1.樹概念及結構

1.1樹的概念???????

1.2 樹的特點：

1.3?樹的相關概念

1.4?樹的表示???????

1.5?樹在實際中的運用（表示文件系統的目錄樹結構）

2.二叉樹概念及結構

2.1概念

2.3 特殊的二叉樹：

????????1. 滿二叉樹：

????????2. 完全二叉樹：

2.4 二叉樹的性質

2.5 二叉樹的存儲結構

1. 順序存儲

2. 鏈式存儲

3.二叉樹的順序結構及實現

3.1 二叉樹的順序結構

3.2 堆的概念及結構

3.3 堆的實現

3.2.1 堆向下調整算法

3.2.2堆的創建

3.2.3 建堆時間復雜度???????

3.2.4?堆中元素調整

3.2.5?堆的插入

3.2.6?堆中元素的判斷

3.2.7?堆中元素的刪除

3.2.8?堆的摧毀

3.2.9?堆的頭文件

3.3?堆的應用

3.3.1 堆排序

3.3.2 TOP-K問題

4.二叉樹鏈式結構的實現

4.1 前置說明

4.2二叉樹的遍歷

4.2.1 前序、中序以及后序遍歷

4.2.2 層序遍歷

4.3 節點個數以及高度等

4.4?二叉樹的創建和銷毀

4.5?二叉樹頭文件

1.樹概念及結構

1.1樹的概念

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

1.2 樹的特點：

? ? ? ? ? (1) 所有樹都有一個特殊的結點，稱為根結點，它是整個樹的起點，其他節點都是從根節點開始向下延伸的。

? ? ? ? ? (2) 每個節點在樹中都是唯一的，每個節點都可以通過其在樹中的位置被唯一地標識。

? ????????(3)?樹形結構的節點之間呈現出層級關系，每個節點可以有多個子節點，但只能有一個父節點，除了根節點沒有父節點。

? ? ? ? ? (4)在數據結構樹中，每個節點都不能構成環，即不存在一個節點的子孫節點中存在其祖先節點的情況。

? ????????(5)?樹是遞歸定義的。

注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構。

1.3?樹的相關概念

1.節點的度?：一個節點含有的子樹的個數稱為該節點的度； ??如上圖： ?A的為6。

2.葉節點或終端節點：度為0的節點稱為葉節點； ??如上圖： ?B、C、?H、?I...等節點為葉節點。

3.非終端節點或分支節點：度不為0的節點； ??如上圖： ?D、?E、?F、G...等節點為分支節點。

4.雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； ??如上圖： ?A是B的父節點。

5.孩子節點或子節點?：一個節點含有的子樹的根節點稱為該節點的子節點； ??如上圖： ?B是A的孩子節點。

6.兄弟節點：具有相同父節點的節點互稱為兄弟節點； ??如上圖： ?B、C是兄弟節點。

7.樹的度?：一棵樹中，最大的節點的度稱為樹的度； ??如上圖：樹的度為6。

8.節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；

9.樹的高度或深度：樹中節點的最大層次； ??如上圖：樹的高度為4。

10.堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：??H、?I互為兄弟節點。

11.節點的祖先：從根到該節點所經分支上的所有節點；如上圖： ?A是所有節點的祖先。

12.子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。如上圖：所有節點都是A的子孫。

13.森林：由?m（?m>0）棵互不相交的樹的集合稱為森林；

1.4?樹的表示

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

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

1.5?樹在實際中的運用（表示文件系統的目錄樹結構）

2.二叉樹概念及結構

2.1概念

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

????????1. 或者為空

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

從上圖可以看出：

????????1. 二叉樹不存在度大于2的結點。

????????2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹。

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

2.3 特殊的二叉樹：

????????1. 滿二叉樹：

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

????????2. 完全二叉樹：

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

2.4 二叉樹的性質

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

2. 若規定根節點的層數為 1 ，則 深度為 h 的二叉樹的最大結點數是 $2^{h}-1$ 。

3. 對任何一棵二叉樹 , 如果度為 0 其葉結點個數為 $n_{0}$ , 度為 2 的分支結點個數為 $n_{1}$ ,則有

$n_{0}$ ＝ $n_{1}$ ＋1

4. 若規定根節點的層數為 1 ，具有 n 個結點的滿二叉樹的深度 ， $h=log_{2}(n+1)$ 。(ps： $log_{2}(n+1)$ 是log 以 2為底，n+1 為對數 )

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

????????1. 若 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 否則無右孩子。

2.5 二叉樹的存儲結構

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

1. 順序存儲

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

2. 鏈式存儲

????????二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址。鏈式結構又分為二叉鏈和三叉鏈，本篇我們學習使用的是二叉鏈，后續我們會更加深入的進行學習三叉鏈等。

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向當前節點左孩子struct BinTreeNode* _pRight; // 指向當前節點右孩子BTDataType _data; // 當前節點值域
}
// 三叉鏈
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向當前節點的雙親struct BinTreeNode* _pLeft; // 指向當前節點左孩子struct BinTreeNode* _pRight; // 指向當前節點右孩子BTDataType _data; // 當前節點值域
}；

3.二叉樹的順序結構及實現

3.1 二叉樹的順序結構

????????普通的二叉樹是不適合用數組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。現實中我們通常把堆( 一種二叉樹 ) 使用順序結構的數組來存儲，需要注意的是這里的堆和操作系統 虛擬進程地址空間中的堆是兩回事，一個是數據結構，一個是操作系統中管理內存的一塊區域分段。

3.2 堆的概念及結構

????????如果有一個關鍵碼的集合 $K=\left \{ k_{0},k_{1},k_{2},..., k_{n-1} \right \}$ ，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數組中，并滿足：? $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.堆中某個節點的值總是不大于或不小于其父節點的值；

? ? ? ? 2.堆總是一棵完全二叉樹。

3.3 堆的實現

3.2.1 堆向下調整算法

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

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

3.2.2堆的創建

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

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

// 小堆
//堆初始化函數
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

3.2.3 建堆時間復雜度

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

因此： 建堆的時間復雜度為 O(N) 。

3.2.4?堆中元素調整

為了便于插入元素的同時滿足堆的特性，我們需要寫一個調整堆中元素的函數：

//交換函數
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向上調整法 
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//while (parent >= 0)while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;//child = (child - 1) / 2;//parent = (parent - 1) / 2;}else{break;}}
}//向下調整法
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;}}
}

???????

3.2.5?堆的插入

先插入一個 10 到數組的尾上，再進行向上調整算法，直到滿足堆。

// O(logN)
//堆的插入函數
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*)realloc(php->a, newCapacity * sizeof(HPDataType));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.2.6?堆中元素的判斷

為了方便對堆中元素的狀況的判斷，我們還需要寫一下這些函數：

//獲取堆頂元素
HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//獲取堆中元素的個數
size_t HeapSize(HP* php)
{assert(php);return php->size;
}//判斷堆是否為空
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

3.2.7?堆中元素的刪除

刪除堆是刪除堆頂的數據，將堆頂的數據根最后一個數據一換，然后刪除數組最后一個數據，再進行向下調整算法。

//堆中元素的刪除
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.2.8?堆的摧毀

在堆使用完畢后，我們需要摧毀已經建立的隊，釋放系統資源，釋放之前向系統申請的堆區域的空間。

//摧毀堆
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

3.2.9?堆的頭文件

#define _CRT_SECURE_NO_WARNINGS 
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void HeapInit(HP* php);void HeapDestroy(HP* php);void HeapPush(HP* php, HPDataType x);
// 規定刪除堆頂（根節點）
void HeapPop(HP* php);HPDataType HeapTop(HP* php);
size_t HeapSize(HP* php);
bool HeapEmpty(HP* php);void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int size, int parent);

3.3?堆的應用

3.3.1 堆排序

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

1. 建堆

????????升序：建大堆

????????降序：建小堆

2. 利用堆刪除思想來進行排序

????????建堆和堆刪除中都用到了向下調整，因此掌握了向下調整，就可以完成堆排序

例：

以下是一個堆排代碼：

// 升序堆排
void HeapSort(int* a, int n)
{// 建大堆// O(N*logN)/*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);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

3.3.2 TOP-K問題

TOP-K 問題：即求數據結合中前 K 個最大的元素或者最小的元素，一般情況下數據量都比較大 。

比如：專業前 10 名、世界 500 強、富豪榜、游戲中前 100 的活躍玩家等。

????????對于Top-K 問題，能想到的最簡單直接的方式就是排序，但是：如果數據量非常大，排序就不太可取了 ( 可能數據都不能一下子全部加載到內存中) 。最佳的方式就是用堆來解決，基本思路如下：

1. 用數據集合中前 K 個元素來建堆

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

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

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

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

以下為參考解決代碼：

//創建文件存入10000000個隨機數
void CreateNDate()
{// 造數據int n = 10000000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand()+i) % 10000000;fprintf(fin, "%d\n", x);}fclose(fin);
}//堆排獲取文件中最大的k個數
void PrintTopK(const char* file, int k)
{FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}// 建一個k個數小堆int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc error");return;}// 讀取前k個，建小堆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);fclose(fout);
}

4.二叉樹鏈式結構的實現

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

注意：上述代碼并不是創建二叉樹的方式，真正創建二叉樹方式后序詳解重點講解。

再看二叉樹基本操作前，再回顧下二叉樹的概念， 二叉樹是：

????????1. 空樹

????????2. 非空：根節點，根節點的左子樹、根節點的右子樹組成的。

從概念中可以看出，二叉樹定義是遞歸式的，因此后序基本操作中基本都是按照該概念實現的。

4.2二叉樹的遍歷

4.2.1 前序、中序以及后序遍歷

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

按照規則，二叉樹的遍歷有：前序 / 中序 / 后序的遞歸結構遍歷 ：

????????1. 前序遍歷 (Preorder Traversal 亦稱先序遍歷 )—— 訪問根結點的操作發生在遍歷其左右子樹之前。

????????2. 中序遍歷 (Inorder Traversal)—— 訪問根結點的操作發生在遍歷其左右子樹之中（間）。

????????3. 后序遍歷 (Postorder Traversal)—— 訪問根結點的操作發生在遍歷其左右子樹之后。

????????由于被訪問的結點必是某子樹的根，所以 N(Node ）、 L(Left subtree ）和 R(Right subtree ）又可解釋為 根、根的左子樹和根的右子樹 。 NLR 、 LNR 和 LRN 分別又稱為先根遍歷、中根遍歷和后根遍歷。

// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){return;}printf("%c ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){return;}BinaryTreeInOrder(root->left);printf("%c ", root->data);BinaryTreeInOrder(root->right);
}// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){return;}BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);printf("%c ", root->data);
}

下面主要分析前序遞歸遍歷，中序與后序圖解類似。

前序遍歷遞歸圖解 ：

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

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

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

4.2.2 層序遍歷

????????層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設二叉樹的根節點所在層數為1 ，層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然后從左到右訪問第 2 層上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問樹的結點的過程就是層序遍歷。

// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;   //這里創建了一個隊列，借助隊列先進先出的特性實現了層序QueueInit(&q);   //隊列初始化if (root){QueuePush(&q, root);  //元素入隊列}int levelsize = 1;while (!QueueEmpty(&q))      //隊列為空停止訓話{while (levelsize--)       {BTNode* front = QueueFront(&q);  //獲取隊頭元素QueuePop(&q);                    //刪除隊頭printf("%c ", front->data);if (front->left){QueuePush(&q, front->left);   //元素入隊列}if (front->right){QueuePush(&q, front->right);}}printf("\n");levelsize = QueueSize(&q);    //獲取隊列元素個數}printf("\n");QueueDestroy(&q);                 //摧毀隊列}

4.3 節點個數以及高度等

// 二叉樹節點個數
int BinaryTreeSize(BTNode* root)
{return root == NULL ? 0 : 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}// 二叉樹葉子節點個數
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);
}// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return TreeLevelK(root->left, k - 1)+ TreeLevelK(root->right, k - 1);
}// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data==x){return root;}BTNode* left = BinaryTreeFind(root->left,x);if (left){return left;}BTNode* right = BinaryTreeFind(root->right,x);if (right){return right;}return NULL;
}// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root)
{Queue q;           //同樣借助隊列進行QueueInit(&q);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);if (front == NULL){QueueDestroy(&q);return 0;}}QueueDestroy(&q);return 1;}

4.4?二叉樹的創建和銷毀

//創建二叉樹
BTNode *BinaryTreeCreate(BTDataType * src, int n, int* pi)
{if (*pi >= n || src[*pi] == '#'){(*pi)++;return NULL;}BTNode * cur = (BTNode *)malloc(sizeof(BTNode));cur->_data = src[*pi];(*pi)++;cur->left = BinaryTreeCreate(src, n, pi);cur->right = BinaryTreeCreate(src, n, pi);return cur;
}//摧毀二叉樹void BinaryTreeDestory(BTNode** root)
{if (*root){BinaryTreeDestory(&(*root)->left);BinaryTreeDestory(&(*root)->right);free(*root);*root = NULL;}
}

4.5?二叉樹頭文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;// 通過前序遍歷的數組"ABD##E#H##CF##G##"構建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root);
// 二叉樹節點個數
int BinaryTreeSize(BTNode* root);
// 二叉樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹查找值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root);
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root);
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root);
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root);
// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root);

本章結束！?