?

樹的概念

樹是一種非線性的數據結構，它是由n（n >= 0）個有限結點組成的一個具有層次關系的集合。它看起來像一個倒掛的樹。
二叉樹最上面的結點被稱為根節點，根節點沒有前驅結點，也就是根結點之上沒有節點。除根結點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼。樹形結構中的子樹之間不能有交集，也就是一個節點不能有兩個前驅。樹是遞歸定義的。

樹有很多引申出的概念，下面是一些常用的。

名稱	意義
結點的度	一個結點含有的子樹的個數稱為該結點的度
葉結點或終端結點	度為0的結點稱為葉結點
非終端結點或分支結點	度不為0的結點
雙親結點或父結點	若一個結點含有子結點，則這個結點稱為其子結點的父結點
孩子結點或子結點	一個結點含有的子樹的根結點稱為該結點的子結點
兄弟結點	具有相同父結點的結點互稱為兄弟結點
樹的度	一棵樹中，最大的結點的度稱為樹的度
結點的層次	從根開始定義起，根為第1層，根的子結點為第2層，以此類推
樹的高度或深度	樹中結點的最大層次
堂兄弟結點	雙親在同一層的結點互為堂兄弟
結點的祖先	從根到該結點所經分支上的所有結點
子孫	以某結點為根的子樹中任一結點都稱為該結點的子孫
森林	由m（m>0）棵互不相交的樹的集合稱為森林

樹的表示方法

由于樹是非線性的數據結構，表示樹時，既要保存樹的值，又要保存結點之間的關系，有一種非常巧妙的方法叫做左孩子右兄弟表示法，定義一個結構體，里面定義一個指向其第一個孩子的指針，再定義一個指向其兄弟的指針。

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

二叉樹的概念

二叉樹是一種特殊的樹，它是結點的一個有限集合，該結點要么為空，要么就是由一個根結點加上兩顆分別被稱為左子樹和右子樹的二叉樹組成。二叉樹不存在度大于2的結點，二叉樹的子樹有左右之分，因此二叉樹是有序樹。

特殊的二叉樹

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

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

二叉樹的性質

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

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

3. 對任何一棵二叉樹, 如果度為0其葉結n0, 度為2的分支結點個數為 n2,則有n0＝n2＋1，如何去理解這句話呢，其實很簡單，在二叉樹最開始只有一個根節點時，度為0的就有1個，度為2的有0個，每增加一個度為1的就會消滅一個度為0的，產生一個度為1的和一個度為0的，度為0的數目不會變，也因此度為1的結點數我們無法求得，而每增加一個度為2的，就會消滅一個度為0的，增加一個度為2的和兩個度為0的，一前一后相抵消的話相當于度為0的因為度為2的加一自己也加了一。于是乎度為0的永遠比度為2的大1。

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

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

（1）若i>0，i位置結點的雙親序號：(i-1)/2；i=0，i為根結點編號，無雙親結點

（2） 若i>0，i位置的左孩子節點為：2i+1，右孩子結點為：2i+2。

（3）高度為h的完全二叉樹，節點數量范圍為[2^(h-1), 2^h-1]。

二叉樹的存儲結構

順序存儲

順序存儲就是利用數組來存儲，這種存儲方式只適用于完全二叉樹，普通二叉樹會有空間上的浪費，畢竟既然使用數組了，數與數之間必然就要有強邏輯，只有完全二叉樹這種父結點與孩子結點都可一一對應的這種才合適，普通的就要將空出的結點的空間浪費。使用數組表示完全二叉樹的這種數據結構我們稱為堆（Heap）。

鏈式存儲

鏈式存儲就是利用來鏈來存儲，也就是使用指針，使用指針的話就相對好處理很多，對于二叉鏈來說，鏈表中的每個節結點都由三個變量組成，數據和左右指針。

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{struct BinTreeNode* left;   // 指向當前結點左孩子struct BinTreeNode* right;  // 指向當前結點右孩子BTDataType data;            // 當前結點值域
};

堆的概念與結構

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

堆的性質

堆中某個結點的值總是不大于或不小于其父結點的值

堆總是一棵完全二叉樹。

堆的實現

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<errno.h>#include<string.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;
//堆的創建
void HeapInit(Heap* php);
// 堆的銷毀
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的刪除
void HeapPop(Heap* hp);
// 取堆頂的數據
HPDataType HeapTop(Heap* hp);
// 堆的數據個數
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
//擴容
void Expansion(Heap* hp);
//交換
void swap(int* a, int* b);
//向上交換
void raise(HPDataType* a, int n);
//向下交換
void down(HPDataType* a, int n);

定義了一個結構體用來保存堆的頭指針，堆的尺寸和堆的存儲元素數量

#include"heap.h"void HeapInit(Heap* php)
{assert(php);Heap* ptr = (HPDataType*)calloc(8, sizeof(HPDataType));if (ptr == NULL){perror("HeapInit:calloc");return;}php->_a = ptr;php->_capacity = 8;php->_size = 0;
}void HeapDestory(Heap* hp)
{assert(hp);free(hp->_a);hp->_a = NULL;hp->_capacity = 0;hp->_size = 0;
}void HeapPush(Heap* hp, HPDataType x)
{assert(hp);Expansion(hp);hp->_a[hp->_size] = x;++hp->_size;raise(hp->_a,hp->_size);
}void raise(HPDataType* a, int n)//向上調整算法
{int child = n;int parents = child / 2;while (child > 1){if (a[child - 1] > a[parents - 1]){swap(&(a[child - 1]), &(a[parents - 1]));child = parents;parents = child / 2;}else{break;}}
}void Expansion(Heap* hp)
{assert(hp);if (hp->_capacity == hp->_size){Heap* ptr = (Heap*)realloc(hp->_a, sizeof(HPDataType) * hp->_capacity * 2);if (ptr == NULL){perror("Expansion:realloc");return;}hp->_a = ptr;hp->_capacity *= 2;}
}void HeapPop(Heap* hp)
{assert(hp && hp->_size);swap(hp->_a, &(hp->_a[hp->_size - 1]));--hp->_size;down(hp->_a, hp->_size);
}void down(HPDataType* a, int n)//向下調整算法
{int parents = 1;int child = parents * 2;while (child <= n){if (child + 1 <= n && a[child - 1] < a[child]){++child;}if (a[child - 1] > a[parents - 1]){swap(&(a[child - 1]), &(a[parents - 1]));parents = child;child = parents * 2;}else{break;}}
}void swap(int* a, int* b)//交換算法
{int ex = *a;*a = *b;*b = ex;
}int HeapSize(Heap* hp)
{assert(hp);return hp->_size;
}int HeapEmpty(Heap* hp)
{assert(hp);if (hp->_size == 0){return 0;}return 1;
}HPDataType HeapTop(Heap* hp)
{assert(hp && HeapEmpty(hp));return hp->_a[0];
}

堆的初始化

void HeapInit(Heap* php)
{assert(php);Heap* ptr = (HPDataType*)calloc(8, sizeof(HPDataType));if (ptr == NULL){perror("HeapInit:calloc");return;}php->_a = ptr;php->_capacity = 8;php->_size = 0;
}

由于堆是一個數組，為了充分的利用空間，我采用動態數組的方式，對于傳入的堆指針，calloc動態開辟內存，檢驗之后設置好頭指針，尺寸和元素數量就行了。

入堆

void HeapPush(Heap* hp, HPDataType x)
{assert(hp);Expansion(hp);hp->_a[hp->_size] = x;++hp->_size;raise(hp->_a,hp->_size);
}

對于進入的元素，首先用擴容函數進行擴容，之后將其插入到隊尾，再將存儲的元素數++，之后進入排序函數對插入后的堆進行排序。

堆的擴容

void Expansion(Heap* hp)
{assert(hp);if (hp->_capacity == hp->_size){Heap* ptr = (Heap*)realloc(hp->_a, sizeof(HPDataType) * hp->_capacity * 2);if (ptr == NULL){perror("Expansion:realloc");return;}hp->_a = ptr;hp->_capacity *= 2;}
}

常規的動態數組的擴容方式。

向上調整算法

void raise(HPDataType* a, int n)//向上調整算法
{int child = n;int parents = child / 2;while (child > 1){if (a[child - 1] > a[parents - 1]){swap(&(a[child - 1]), &(a[parents - 1]));child = parents;parents = child / 2;}else{break;}}
}

對于之前的入堆函數，我將數據插入到隊尾，這時要對堆進行排序，就要用到向上調整函數，其原理就要利用到堆的性質，即父節點要比子節點大（大堆）或者小（小堆），對于插入到堆的尾部的元素，我們就是要一步一步地找到其對應的父節點，與之比較，如果父節點比他大（大堆）或比他小（小堆），就交換兩個數，直到父節點比他小（大堆）或者大（小堆）為止，我們就完成了排序。對于具體的實現方法，首先我們需要明白的是，堆的理想樣式與數組是有一些出入的，對于堆，我們會讓其從1開始計數，而數組是從0開始計數的，這兩種計數方式計算父子結點的方式不同。對于從1開始的堆，父節點 = 子節點 / 2，子節點1 = 父節點 * 2 ，子節點2 = 父節點 * 2 + 1。對于從0開始的堆，父節點 = （子節點 - 1） / 2，子節點1 = 父節點 * 2 + 1 ，子節點2 = 父節點 * 2 + 2。所以在排序時我們要注意到這一點，我這里采用的是將父節點和子節點按一般堆的表示方式即從1開始計數，在數組計算時將其減一表示正確的位置，其實也可以在一開始就按從0開始計算，這樣就不用減一了，按習慣來。引入兩個新變量后，將child表示為新入堆元素的位置，parents表示為child的父節點，，之后用while循環反復執行檢驗父子節點并交換的操作，當插入元素來到根結點或者找到比它大（大堆）或者小（小堆）時就停止。

出堆（最頂端元素）

void HeapPop(Heap* hp)
{assert(hp && hp->_size);swap(hp->_a, &(hp->_a[hp->_size - 1]));--hp->_size;down(hp->_a, hp->_size);
}

刪除堆中最頂端的元素，也就是根結點，這其實是有點麻煩的，對于堆來說，刪除其末端的元素，其實是最為簡單的，下一次存入時覆蓋就行，他不會破壞整體的排序。而對于頂端，如果用一般的處理方式，貿然用memmove函數或循環等方法將后面的元素向前移動來覆蓋是不行的，堆中的數據排序有著強邏輯，整體移動這么多元素會破壞這種關系，所以我先將頂段元素與末端元素交換，將size–，之后我們用向下調整算法對其進行排序，完成頂端元素的刪除。

向下調整算法

void down(HPDataType* a, int n)//向下調整算法
{int parents = 1;int child = parents * 2;while (child <= n){if (child + 1 <= n && a[child - 1] < a[child]){++child;}if (a[child - 1] > a[parents - 1]){swap(&(a[child - 1]), &(a[parents - 1]));parents = child;child = parents * 2;}else{break;}}
}

對于出堆（頂端元素）函數中，我們需要用到向下調整函數，在入堆操作中，我使用向上調整算法，將入堆元素與其父節點進行比較，向上交換。向下調整函數與之相反，交換首尾元素后，將頂端元素（根結點）與其子節點進行比較，如果比其小（大堆）或者大（小堆）就交換，直到比子節點大（大堆）或者小（小堆）或者超出堆的元素數量為止。具體的實現方式與向上調整方式類似，有一點需要特別注意，在向上調整算法中，元素只需要找到其父節點就行，父節點就一個，而在向下調整算法中，與之比較的子節點有兩個，那我們就要保證與其比較的是最大（大堆）或者最小（小堆），所以在正式進行父子結點比較時，還要加一個if語句選出最大的子節點，與此同時也要時刻注意堆的越界情況，child和child+1都要<=n。

二叉樹的實現

#include "queue.h"#include<stdio.h>#include<stdlib.h>#include<string.h>#include<assert.h>#include<errno.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* 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);

#include"BinaryTree.h"BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{if (a[(*pi)] == '#' || !a){++(*pi);return NULL;}BTNode* newnode = (BTNode*)calloc(1, sizeof(BTNode));newnode->_data = a[(*pi)++];newnode->_left = BinaryTreeCreate(a, pi);newnode->_right = BinaryTreeCreate(a, pi);return newnode;
}void BinaryTreeDestory(BTNode** root)
{if (!*root)return;BinaryTreeDestory(&((*root)->_left));BinaryTreeDestory(&((*root)->_right));free(*root);*root = NULL;
}int BinaryTreeSize(BTNode* root)
{if (!root)return 0;return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}int BinaryTreeLeafSize(BTNode* root)
{if (!root)return 0;if (!root->_left && !root->_right)return 1;return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}int BinaryTreeLevelKSize(BTNode* root, int k)
{--k;if (!root){return 0;}if (k == 0)return 1;return BinaryTreeLevelKSize(root->_left, k) + BinaryTreeLevelKSize(root->_right, k);
}//int BTLKSize(BTNode* root, int* k)
//{
//	--*k;
//	if (*k == 0)
//		return 1;
//	int ck = *k;
//	return BTLKSize(root->_left, &ck) + BTLKSize(root->_right, k);
//}BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (!root)return NULL;if (root->_data == x)return root;BTNode* left = BinaryTreeFind(root->_left, x);if (left)return left;return BinaryTreeFind(root->_right, x);
}void BinaryTreePrevOrder(BTNode* root)//前
{if (!root){printf("# ");return;}printf("%c ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}void BinaryTreeInOrder(BTNode* root)//中
{if (!root){printf("# ");return;}BinaryTreeInOrder(root->_left);printf("%c ", root->_data);BinaryTreeInOrder(root->_right);
}void BinaryTreePostOrder(BTNode* root)//后
{if (!root){printf("# ");return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%c ", root->_data);
}void BinaryTreeLevelOrder(BTNode* root)
{if (!root)return;Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* curr = QueueFront(&q);printf("%c ", curr->_data);QueuePop(&q);if(curr->_left)QueuePush(&q, curr->_left);if(curr->_right)QueuePush(&q, curr->_right);}QueueDestory(&q);
}int BinaryTreeComplete(BTNode* root)
{Queue qu;BTNode* cur;int tag = 0;QueueInit(&qu);QueuePush(&qu, root);while (!QueueIsEmpty(&qu)){cur = QueueTop(&qu);putchar(cur->_data);if (cur->_right && !cur->_left)return 0;if (tag && (cur->_right || cur->_left))return 0;if (cur->_left)QueuePush(&qu, cur->_left);if (cur->_right)QueuePush(&qu, cur->_right);elsetag = 1;QueuePop(&qu);}QueueDestory(&qu);return 1;
}

二叉樹的創建

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{if (a[(*pi)] == '#' || !a){++(*pi);return NULL;}BTNode* newnode = (BTNode*)calloc(1, sizeof(BTNode));newnode->_data = a[(*pi)++];newnode->_left = BinaryTreeCreate(a, pi);newnode->_right = BinaryTreeCreate(a, pi);return newnode;
}

在二叉樹的實現過程中需要時刻用到兩路歸并的思想，也就是分成兩路的遞歸，傳入的參數是字符串數組和計數用的整形指針，他在初始時解引用的值為0，以此來計數。對于遞歸函數，其開頭當然是寫遞歸的結束條件，當數組為字符’#‘或’\0’時結束遞歸（'#'表示空結點），返回NULL。之后就是創建結點，給結點賦值，之后引用函數本身給左右子節點地址賦值以此形成遞歸。

二叉樹的銷毀

void BinaryTreeDestory(BTNode** root)
{if (!*root)return;BinaryTreeDestory(&((*root)->_left));BinaryTreeDestory(&((*root)->_right));free(*root);*root = NULL;
}

對于二叉樹的銷毀，傳參有兩種形式，一種是傳根節點的指針，一種是傳根節點的二級指針，這兩者的區別是傳二級指針的話可以在函數內就完成指針free后的置空，而傳一級指針就不行，需要手動置空，我這里用的是二級指針，用二級指針的話就要注意解引用。這個函數也是一個二路歸并函數，先判斷遞歸結束的條件（指針為空），引用自己對左右指針進行銷毀，注意先要引用自己銷毀左右指針，再銷毀自己，先銷毀自己的話就i丟失了左右指針的地址了。

二叉樹的元素數

int BinaryTreeSize(BTNode* root)
{if (!root)return 0;return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

二叉樹沒法像堆一樣直接得出元素的數量，需要遍歷求和才行，這里我同樣采用二路歸并，先給出遞歸結束的條件，返回0，之后再return語句中引用自己求和就行。

二叉樹的葉子節點數

int BinaryTreeLeafSize(BTNode* root)
{if (!root)return 0;if (!root->_left && !root->_right)return 1;return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

葉子節點就是沒有子節點的結點，同樣的，遞歸先給出遞歸結束的條件，這里有兩種情況，一種是遇到了左右子節點都為空節點的葉子節點返回1，一種是遇到了空節點返回0，這里有人會疑惑為什么判斷為葉子節點就返回了為什么還會遇到空結點，這是因為會有一個子節點為空另一個子節點正常的情況。之后我們同樣利用return語句計算總數。

二叉樹第k層結點個數

int BinaryTreeLevelKSize(BTNode* root, int k)
{--k;if (!root){return 0;}if (k == 0)return 1;return BinaryTreeLevelKSize(root->_left, k) + BinaryTreeLevelKSize(root->_right, k);
}

我們計算二叉樹第k層結點個數的原理就是每訪問一層就將k–，當k減為0就到達了k層，此時如果不為空結點就返回1。 首先為了避免k值過大出現非法訪問的情況，設置一個遇到空結點return 0的if語句，之后設置遞歸結束的條件，即k值減為0時返回1。

二叉樹中尋找值為x的結點

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (!root)return NULL;if (root->_data == x)return root;BTNode* left = BinaryTreeFind(root->_left, x);if (left)return left;return BinaryTreeFind(root->_right, x);
}

同樣的，先給出遞歸結束的條件，當結點為空時返回NULL，當結點為要找的數時返回結點地址，之后我們先引用自己對左子樹進行尋找，返回結果賦值給left，if語句判斷left不為空就返回left，不是就返回引用自己對右子樹的尋找結果，因為已經找完了左子樹了，右子樹就算沒找到也是返回NULL，所以直接返回右子樹的結果就行。

二叉樹的前中后序遍歷

void BinaryTreePrevOrder(BTNode* root)//前
{if (!root){printf("# ");return;}printf("%c ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}void BinaryTreeInOrder(BTNode* root)//中
{if (!root){printf("# ");return;}BinaryTreeInOrder(root->_left);printf("%c ", root->_data);BinaryTreeInOrder(root->_right);
}void BinaryTreePostOrder(BTNode* root)//后
{if (!root){printf("# ");return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%c ", root->_data);
}

所謂前中后序遍歷，就是對父結點，左子樹，右子樹的訪問順序，前序遍歷就是先訪問根結點，再從左至右訪問左右子樹，中序遍歷就是根結點在中間，左子樹在左，右子樹在右，后序遍歷就是先從左至右訪問左右子樹，最后再訪問根結點。前中后序遍歷的實現很簡單，理解了之前的二路歸并就很容易實現。

二叉樹的層序遍歷

void BinaryTreeLevelOrder(BTNode* root)
{if (!root)return;Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* curr = QueueFront(&q);printf("%c ", curr->_data);QueuePop(&q);if(curr->_left)QueuePush(&q, curr->_left);if(curr->_right)QueuePush(&q, curr->_right);}
}

層序遍歷顧名思義就是就是按照層的順序逐層遍歷二叉樹，這相比較于二叉樹的前中后序遍歷要麻煩得多，因為二叉樹只層與層之間有鏈接，同層元素之間的并沒有強聯系。這里有一種巧妙的方法，那就是用隊列來實現。先引入隊列的數據結構，我引入了我之前完成的隊列。先將二叉樹的根結點入隊列，然后根據隊列先進先出的特點，每出一個元素就在隊列尾部按從左到右插入左右子節點，如此往復，知道隊列為空，如此就完成了二叉樹的層序遍歷。下面是圖解。

判斷二叉樹是否為完全二叉樹

int BinaryTreeComplete(BTNode* root)
{Queue qu;BTNode* cur;int tag = 0;QueueInit(&qu);QueuePush(&qu, root);while (!QueueIsEmpty(&qu)){cur = QueueTop(&qu);putchar(cur->_data);if (cur->_right && !cur->_left)return 0;if (tag && (cur->_right || cur->_left))return 0;if (cur->_left)QueuePush(&qu, cur->_left);if (cur->_right)QueuePush(&qu, cur->_right);elsetag = 1;QueuePop(&qu);}QueueDestory(&qu);return 1;
}

根據完全二叉樹的定義，我們明白完全二叉樹直到結束為止到要排滿的二叉樹，對于如何檢驗，我們首先要明白在這種情況下使用隊列來遍歷是一個很好的選擇，因為隊列是層序遍歷，完全二叉的檢驗也是按層序檢驗有沒有缺子節點，之后要明確何種情況下才能判斷其不是完全二叉樹，一種是出現左節點為空時，完全二叉要么左右節點都為空，要么只有右為空，所以左為空一定不是完全二叉；再者就是右為空的情況，但我們明白右為空本身并不一定就不是完全二叉，但右為空一定意味著完全二叉已經到了末尾，之后如果出現不為空的節點，就一定能判斷其不是完全二叉了，我使用了一個tag變量來記錄，將其初始化為0，第一次遇到右為0時將其賦值為1，之后當tag為1且左右子節點有一個不為空時就可以認定其不為完全二叉樹了。

?