必須有為成功付出代價的決心，然后想辦法付出這個代價。云邊有個稻草人-CSDN博客

這節(jié)課挺抽象（苦笑），沒事，我會幫你！干就完了！

（目錄在路上）

---

正文開始——

引言

用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。通常的方法是鏈表中每個結點有三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在鏈結點的存儲地址，結構見下：

//創(chuàng)建鏈式結構二叉樹的結構->二叉鏈
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType* data;struct BinaryTreeNode* left;//指定當前結點的左孩子struct BinaryTreeNode* right;//指定當前結點的右孩子
}BTNode;

二叉樹的創(chuàng)建方式比較復雜，為了更好地步入到二叉樹內容中，我們先手動創(chuàng)建一棵鏈式二叉樹。

//申請結點
BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc faile!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}BTNode* CreateTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);//改變指針指向，使其成為一棵鏈式二叉樹node1->left = node2;node1->right = node3;node2->left = node4;return node1;}

回顧二叉樹的概念，二叉樹分為空樹和非空二叉樹，非空二叉樹由根節(jié)點、根節(jié)點的左子樹和根節(jié)點的右子樹組成的。

根節(jié)點的左子樹和右子樹分別又是由子樹節(jié)點、子樹結點的左子樹和子樹結點的右子樹組成的，因此二叉樹是遞歸式的，后序鏈式二叉樹的操作基本都是按照概念實現的。

一、前中后序遍歷

1.1 遍歷規(guī)則

按照規(guī)則，二叉樹的遍歷有：前序 /中序/ 后序的遍歷結構：

• 前序遍歷（Preorder Traversal 亦稱先序遍歷）：訪問根結點的操作發(fā)生在遍歷其左右子樹之前，訪問的順序：根節(jié)點、左子樹、右子樹
• 中序遍歷（Inorder Traversal）：訪問根節(jié)點的操作發(fā)生在遍歷其左右子樹之間，訪問順序：左子樹、根節(jié)點、右子樹
• 后序遍歷（Postorder Traversal）：訪問根節(jié)點的操作發(fā)生在遍歷其左右子樹之后，訪問順序：左子樹、右子樹、根節(jié)點

1.2 代碼實現

（1）前序遍歷

//前序遍歷
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

該圖里面，前序遍歷結果為：1 2 4 3?

（2）中序遍歷

//中序遍歷--左根右
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
} 

中序遍歷結果為：4? 2? 1? 3?

（3）后序遍歷

//后序遍歷--左右根
void PosOrder(BTNode* root)
{if (root == NULL){return;}PosOrder(root->left);PosOrder(root->right);printf("%d ", root->data);
}

二、結點個數以及高度等

2.1 二叉樹結點個數

//求二叉樹節(jié)點的個數
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

2.2 二叉樹葉子結點的個數

//二叉樹葉子結點個數
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.3 二叉樹第K層結點的個數

//第K層節(jié)點個數
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.4 求二叉樹的高度/深度

//求二叉樹高度/深度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}

2.5 二叉樹查找值為x的節(jié)點

//二叉樹找值為x的結點
BTNode* BinaryFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}

2.6 二叉樹的銷毀

//二叉樹的銷毀
void BinaryTreeDestroy(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestroy(&((*root)->left));//注意這里的傳參，傳的是地址BinaryTreeDestroy(&((*root)->right));free(*root);*root = NULL;
}

三、層序遍歷

我們要提前實現一個隊列的結構，（1）在下面的函數里面我們創(chuàng)建一個隊列，并且別忘記隊列的初始化和銷毀，（2）同時要注意，我們前面學習的隊列里面的數據是整型類型，這次我們要將結點插入到隊列里面，所以我們要將隊列里面的數據類型改為二叉樹節(jié)點的類型，并且我們不能直接寫二叉樹節(jié)點的縮寫那樣，我們要寫成 struct BinaryTreeNode* / struct BTNode* ，反正都不能少 struct，不然會報錯。（3）還有一點，在我們的層序遍歷代碼里面當while循環(huán)結束的時候隊列為NULL，下一步再進行隊列的銷毀的時候就會報錯，因為我們前面實現的隊列的銷毀里面隊列為空時不能銷毀，所以assert會報錯，所以我們可以把隊列的銷毀里面判斷隊列是否為空的那一步給注釋掉。

提及到的代碼需要注意的點都在下面，多看看！

//創(chuàng)建節(jié)點的結構
typedef struct BinaryTreeNode* QUDatatype;//這里需要注意
typedef struct QueueNode
{QUDatatype data;struct QueueNode* next;
}QueueNode;

//銷毀
void QueueDestroy(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));//往這看，注釋掉這里也沒事，就算隊列為空也沒關系//此時pcur為NULL，進不去循環(huán)QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

//層序遍歷
void LevelBinaryTree(BTNode* root)
{//先創(chuàng)建一個隊列Queue q;QueueInit(&q);//取根節(jié)點入隊列QueuePush(&q, root);while (!QueueEmpty(&q)){//打印隊頭數據BTNode* Front = QueueFront(&q);printf("%d ", Front->data);QueuePop(&Front);if (Front->left){QueuePush(&q, Front->left);}if (Front->right){QueuePush(&q, Front->right);}}QueueDestroy(&q);
}

四、判斷是否是完全二叉樹

//判斷是否是完全二叉樹
bool 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 false;}}QueueDestroy(&q);return true;
}

【圖解】

五、本節(jié)課代碼匯總

?Queue.h

#pragma once
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//創(chuàng)建節(jié)點的結構
typedef struct BinaryTreeNode* QUDatatype;
typedef struct QueueNode
{QUDatatype data;struct QueueNode* next;
}QueueNode;//創(chuàng)建隊列的結構
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);//入隊列
void QueuePush(Queue* pq,QUDatatype x);//判空
bool QueueEmpty(Queue* pq);//出隊列
void QueuePop(Queue* pq);//取隊頭數據
QUDatatype QueueTop(Queue* pq);//去隊尾數據
QUDatatype QueueBack(Queue* pq);//去隊列中有效數據的個數
int QueueSize(Queue* pq);//銷毀
void QueueDestroy(Queue* pq);

Queue.c

#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//入隊列
void QueuePush(Queue* pq, QUDatatype x)
{assert(pq);//現申請新的結點QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//如果為空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}//出隊列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* pcur = pq->phead->next;free(pq->phead);pq->phead = pcur;}pq->size--;
}//取隊頭數據
QUDatatype QueueTop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;}//去隊尾數據
QUDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}int QueueSize(Queue* pq)
{assert(pq);/*QueueNode* pcur = pq->phead;int count = 0;while (pcur){count++;QueuePop(pq);pcur = pq->phead;}*//*return count;*/return pq->size;
}//銷毀
void QueueDestroy(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

Tree.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//創(chuàng)建鏈式結構二叉樹的結構->二叉鏈
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;//指定當前節(jié)點的左孩子struct BinaryTreeNode* right;//指定當前節(jié)點的右孩子
}BTNode;//申請節(jié)點
BTNode* BuyNode(BTDataType x);//前序遍歷
void PreOrder(BTNode* root);//中序遍歷
void InOrder(BTNode* root);//后序遍歷
void PosOrder(BTNode* root);//求二叉樹節(jié)點的個數
int BinaryTreeSize(BTNode* root);//二叉樹葉子結點個數
int BinaryTreeLeafSize(BTNode* root);//第K層節(jié)點個數
int BinaryTreeLevelKSize(BTNode* root,int k);//求二叉樹高度/深度
int BinaryTreeDepth(BTNode* root);//找X的結點
BTNode* BinaryFind(BTNode* root, BTDataType x);//二叉樹的銷毀
void BinaryTreeDestroy(BTNode** root);//層序遍歷
void LevelBinaryTree(BTNode* root);//判斷是否是完全二叉樹
bool BinaryTreeComplete(BTNode* root);

Tree.c

#include"Tree.h"
#include"Queue.h"//申請節(jié)點
BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc faile!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}//前序遍歷-
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}//中序遍歷--左根右
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
} //后序遍歷--左右根
void PosOrder(BTNode* root)
{if (root == NULL){return;}PosOrder(root->left);PosOrder(root->right);printf("%d ", root->data);
}//求二叉樹節(jié)點的個數
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 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層節(jié)點個數
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);
}//求二叉樹高度/深度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}//二叉樹找值為x的結點
BTNode* BinaryFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}//二叉樹的銷毀
void BinaryTreeDestroy(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestroy(&((*root)->left));BinaryTreeDestroy(&((*root)->right));free(*root);*root = NULL;
}//層序遍歷
void LevelBinaryTree(BTNode* root)
{//先創(chuàng)建一個隊列Queue q;QueueInit(&q);//取根節(jié)點入隊列QueuePush(&q, root);while (!QueueEmpty(&q)){//打印隊頭數據BTNode* Front = QueueFront(&q);printf("%d ", Front->data);QueuePop(&Front);if (Front->left){QueuePush(&q, Front->left);}if (Front->right){QueuePush(&q, Front->right);}}QueueDestroy(&q);
}//判斷是否是完全二叉樹
bool 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 false;}}QueueDestroy(&q);return true;
}

?test.c

#include"Tree.h"BTNode* CreateTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);node1->left = node2;node1->right = node3;node2->left = node4;return node1;}int main()
{BTNode* node = CreateTree();/*PreOrder(node);printf("\n");InOrder(node);printf("\n");PosOrder(node);*/printf("NodeSize:%d\n", BinaryTreeSize(node));printf("NodeSize:%d\n", BinaryTreeSize(node));printf("NodeSize:%d\n", BinaryTreeSize(node));printf("LeafSize：%d\n", BinaryTreeLeafSize(node));printf("%d\n", BinaryTreeLevelKSize(node, 3));printf("%d\n", BinaryTreeDepth(node));BTNode* find = BinaryFind(node, 22);printf("%s\n", find == NULL ? "沒找到\n" : "找到了！\n");LevelBinaryTree(node);bool ret = BinaryTreeComplete(node);printf("%s\n", ret == false ? "不是完全二叉樹\n" : "是完全二叉樹\n");BinaryTreeDestroy(&node);return 0;
}

我感覺這節(jié)遞歸還是挺難理解的，感覺函數遞歸進行的過程不好想象，層層遞歸就比較難以理解透徹，我會忘記自己遞歸到那個地方了繞不回去了就很燒腦筋，難想的時候呢我就得畫出函數進行棧幀的創(chuàng)建與銷毀，這樣一步一步來還是比較好的。對了，我畫的紅箭頭還有綠箭頭可以看成是函數棧幀的創(chuàng)建與銷毀。把詳細的函數的棧幀的創(chuàng)建與銷毀多想幾遍函數的遞歸應該就會好想象一點了。這節(jié)課我啃了兩天了，后續(xù)還得多回顧理解多敲代碼，告訴自己，別畏難，很難，但也得一步一步走下去，總不能放棄吧，那就堅定不移的前進！（這節(jié)課的博客真難寫呀啊啊啊——）

知識點有不對的地方還請多多指教（抱拳）

完——

---

終——Relaxing Time！

好好休息一下，繼續(xù)戰(zhàn)斗！昨天又發(fā)現了一首好聽的歌(＾－＾)V）分享給你

? ? ? ? ? ?————————————《Falling U》————————————

Falling U_T-ara_高音質在線試聽_Falling U歌詞|歌曲下載_酷狗音樂

至此結束——

我是云邊有個稻草人

期待與你的下一次相遇！