目錄
1.概念與結構
2.二叉數鏈式的實現
2.1遍歷規則
2.2申請內存空間
2.3手動構建一棵二叉樹
2.4二叉樹結點的個數
2.5二叉樹葉子結點的個數
2.6二叉樹第K層結點個數
2.7二叉樹的高度
2.8二叉樹中查找值為x的結點
2.9二叉樹的銷毀
3.層序遍歷
3.1概念
3.2層序遍歷的實現
4.判斷是否為完全二叉樹
5.總結
1.概念與結構
用鏈表來表示一棵二叉樹，即用鏈表來指示元素的邏輯關系。通常的方法是鏈表中每一個由三個域組成：數據域，左指針域和右指針域。左右指針分別用來給出該結點的左孩子和右孩子所在的鏈結點的存儲地址，最終結點的結構是下面所示：
typedef int BTDataType;
typedef struct BinaryTreeNode
{
?? ?BTDataType data;
?? ?struct BinaryTreeNode* left;
?? ?struct BinaryTreeNode* right;
}BTNode;
由于根結點的左子樹分別又是由子樹結點、子樹結點的左子樹、子樹結點的右子樹組成的。因此二叉樹定義是遞歸式的，鏈式二叉樹的操作中基本都是按照該概念實現的。所以我們在二叉樹的各種操作中都要用到遞歸操作，所以代碼比較簡單，但是比較難寫出來！
2.二叉數鏈式的實現
2.1遍歷規則
（1）前序遍歷
訪問根結點的操作發生在左右結點之前，即我們先遍歷更結點然后再是左結點，最后才是右結點。
我們從A開始進入二叉樹，先打印A結點的數據，再打印A結點的左孩子即為B，再同理推出D，由于D的左孩子為NULL，打印完NULL后再進入D的右孩子，又為NULL，然后返回到B ，B 的左孩子已經打印完了，所以我們開始打印B的右孩子，由于為NULL，所以我們返回到B，B 子樹已經全部遍歷完了，所以我們開始遍歷C 子樹，以此類推，最終打印出順序為：ABDNULLNULLNULLCENULLNULLFNULLNULL這就是我們所說的前序遍歷。
代碼實現：
//前序遍歷
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c", root->data);//我們主要是打印出這個結點的位置，所以我們用字母來表示這個//我們要把開始typedef的int 改為charPreOrder(root->left);PreOrder(root->right);
}(2)中序遍歷
中序遍歷是先從左結點開始遍歷后面是根結點最后是右結點。容易知道上副圖的遍歷結果為ABDNULLNULLNULLCENULLNULLFNULLNULL,所以最終代碼實現是：
//中序遍歷
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}（3）后序遍歷
后序遍歷是先去遍歷左結點，再是右結點最后才是根結點，所以開始的運行結果為NULL NULL D NULL B NULL NULL E NULL NULL F C A,代碼實現：
//后序遍歷
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}2.2申請內存空間
我們需要先malloc一個結點大小的空間并且把傳入的數據賦值給data，左孩子和右孩子指針置為NULL，所以代碼如下：
//申請內存空間
BTNode* buyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));node->data = x;node->left = node->right = NULL;
}2.3手動構建一棵二叉樹
我們如果和我們之前的那張圖片一樣構造二叉樹的結果一樣的話，我們可以寫出以下代碼：
//手動構造一塊二叉樹
BTNode* CreateTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;return nodeA;
}2.4二叉樹結點的個數
我們發現二叉樹結點個數等于左子樹的結點個數加上右結點個數加上根結點的個數（1）構成，而左子樹也等于左二叉樹的結點個數加上右二叉樹的結點個數加上根結點的個數（1）構成，所以最終代碼如下：
//二叉樹結點個數
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}2.5二叉樹葉子結點的個數
我們發現二叉樹葉子結點的個數=左子樹葉子結點的個數+右子樹葉子結點的個數，所以最終代碼如下：
//葉子結點的個數
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);
}2.6二叉樹第K層結點個數
我們發現二叉樹第K層結點個數=左子樹第K層結點的個數+右子樹第K層結點的個數，所以最終代碼如下：
//二叉樹第K層結點個數
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}2.7二叉樹的高度
我們要比較的是左子樹深度和右子樹的深度，比較大的一方才算，即為根結點+max(左子樹，右子樹）我們先調用一下左子樹的遞歸序列，并把左子樹的深度存儲起來，然后把右子樹按照同樣的方法進行存儲，后面返回其中最大的一個加1即可，最終代碼如下：
//求二叉樹的深度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return 1 + (leftDep > rightDep ? leftDep : rightDep);
}2.8二叉樹中查找值為x的結點
我們用前序遍歷方法進行查找，代碼如下：
//二叉樹中查找值為x的結點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}2.9二叉樹的銷毀
我們需要傳一個指針，然后先進行左子樹的銷毀，最后再進行右子樹的銷毀，所以代碼如下：
//二叉樹的銷毀
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&(*root)->left);//->的優先級大于*BinaryTreeDestory(&(*root)->right);free(*root);*root = NULL;
}3.層序遍歷
3.1概念
層序遍歷就是從二叉樹的根結點出發，依次往左孩子到右孩子進行訪問，像我們上一副圖的層序遍歷就是ABCDEF。
3.2層序遍歷的實現
先說結論，我們用隊列來實現層序遍歷，先進行根結點入隊列，若發現不為空，則把隊頭數據進行出隊操作，若取出的結點有左孩子（右孩子），則把左孩子（右孩子）入隊列，依次類推。所以我們需要隊列這個數據結構的幫助。我們把之前的代碼復制過來有
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
#include<stdbool.h>
//定義隊列結點的結構
typedef int STDataType;
typedef struct QueueNode
{STDataType data;struct QueueNode* next;
}QueueNode;
//隊列的結構
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;
}Queue;
//隊列的初始化
void QueueInit(Queue* pq)
{assert(pq);//防止傳參為空pq->phead = pq->ptail = NULL;
}
//入隊列
void QueuePush(Queue* pq, STDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!\n");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){//也可以寫為//pq->phead==pq->ptailpq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;//也可以把pq->ptail=newnode寫到if-else語句之后}
}
//隊列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}
//隊列有效元素的個數
int QueueSize(Queue* pq)
{int size = 0;QueueNode* pcur = pq->phead;while (pcur){size++;pcur = pcur->next;}return size;
}
//出隊列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}
}
//取隊頭數據
STDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}
//取隊尾數據
STDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
//銷毀隊列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;//可以加pq->size=0
}
//測試函數
void test()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);int size = QueueSize(&q);printf("%d\n", size);QueuePop(&q);size = QueueSize(&q);printf("%d\n", size);size = QueueFront(&q);printf("%d\n", size);size = QueueBack(&q);printf("%d\n", size);QueueDestroy(&q);
}
int main()
{test();return 0;
}我們需要改以下的東西：typedef struct BiaryTreeNode*? STDataType;（我們所存儲的數據類型是struct BinaryTreeNode*）,之所以是指針，因為我們之后要使用二級指針，這樣子更方便，所以最終實現有：
//層序遍歷
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);printf("%c ", top->data);if (top->left){QueuePush(&q, top->left);}if (top->right){QueuePush(&q, top->right);}}QueueDestroy(&q);
}4.判斷是否為完全二叉樹
完全二叉樹有兩個特點：除最后一層外其余層數的結點個數都達到最大；最后一層結點從左到右依次排列。代碼實現如下（我會注釋）：
//判斷是否為完全二叉樹
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取隊頭出隊頭BTNode* top = QueueFront(&q);QueuePop(&q);if (top == NULL){break;}//把不為空的隊頭結點的左右孩子入隊列QueuePush(&q, top->left);QueuePush(&q, top->right);}//隊列不一定為空，繼續取隊頭出隊頭while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}5.總結
二叉樹鏈式代碼比較簡單，但是實現這個比較難。下節我將講解二叉樹的應用，喜歡的可以一鍵三連哦。
)
)
