引言
本篇博客是初階數(shù)據(jù)結(jié)構(gòu)樹的收尾，將會講掉基本二叉樹鏈式結(jié)構(gòu)的具體內(nèi)容和實現(xiàn)，包括二叉樹的構(gòu)建，前序遍歷，中序遍歷，后序遍歷和層序遍歷，計算二叉樹結(jié)點個數(shù)，第k層結(jié)點個數(shù)，二叉樹葉子結(jié)點個數(shù)，以及判斷一個二叉樹是否為完全二叉樹。話不多說，開始我們今天的內(nèi)容。
二叉樹鏈式結(jié)構(gòu)
在之前的博客中，已經(jīng)講到了關(guān)于鏈式二叉樹相關(guān)定義的內(nèi)容。
這里我們可以來看一看關(guān)于二叉樹結(jié)點的定義：
typedef char BTDataType;//定義存儲數(shù)據(jù)類型
typedef struct BinaryTreeNode
{
BTDataType _data; //存儲數(shù)據(jù)
struct BinaryTreeNode* _left; //指向左孩子（左子樹）
struct BinaryTreeNode* _right; //指向右孩子（右子樹）
}BTNode;二叉樹：
1. 空樹
2. 非空樹：由根結(jié)點，根節(jié)點的左子樹，根節(jié)點的右子樹組成。
從概念上可以看出，二叉樹是遞歸定義的，后面對二叉樹的構(gòu)建和遍歷操作都是圍繞遞歸的思路展開。
二叉樹的遍歷方式及實現(xiàn)
學(xué)習二叉樹，首先就需要學(xué)會其遍歷方式，所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點進行相應(yīng)的操作，并且每個節(jié)點只操作一次。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎(chǔ)。
按照不同的遍歷規(guī)則，二叉樹的遍歷方式有四種：前序遍歷，中序遍歷，后序遍歷和層序遍歷
- 前序遍歷(Preorder Traversal 亦稱先序遍歷)訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之前。
- 中序遍歷(Inorder Traversal)訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之中（間）。
- 后序遍歷(Postorder Traversal)訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之后。
這三種遍歷方式大同小異，層序遍歷放到后面單獨再講。
下面仔細講下前序遍歷，弄懂前序遍歷，中序和后序也就沒什么難度了。
1.前序遍歷
前序遍歷：訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之前。
前序遍歷圖解：
對于上面這棵二叉樹：
前序遍歷結(jié)果：1 2 3 N N N 4 5 N N 6 N N
中序遍歷結(jié)果：N 3 N 2 N 1 N 5 N 4 N 6 N
后序遍歷結(jié)果：N N 3 N 2 N N 5 N N 6 4 1
層序遍歷結(jié)果：1 2 4 3 N 5 6 N N N N N N
代碼實現(xiàn)：
打印結(jié)點操作在遍歷左右子樹之前。
// 二叉樹前序遍歷
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)return; //遇到NULL結(jié)點返回
printf("%c ", root->_data);
BinaryTreePrevOrder(root->_left); //遞歸到左子樹
BinaryTreePrevOrder(root->_right); //遞歸到右子樹
}
2.中序遍歷
中序遍歷：訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之中（間）。
代碼實現(xiàn)：
與前序很相似，不過打印結(jié)點操作在遍歷完左子樹之后。
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)return; //遇到NULL結(jié)點返回
BinaryTreeInOrder(root->_left); //遍歷左子樹
printf("%c ", root->_data);
BinaryTreeInOrder(root->_right); //遍歷右子樹
}3.后續(xù)遍歷
后序遍歷：訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之后。
代碼實現(xiàn)：
與前序遍歷相似，不過打印結(jié)點操作在遍歷完左右子樹之后。
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)return; //遇到NULL結(jié)點返回
BinaryTreePostOrder(root->_left); //遍歷左子樹
BinaryTreePostOrder(root->_right); //遍歷右子樹
printf("%c ", root->_data);
}4.層序遍歷
層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設(shè)二叉樹的根節(jié)點所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先訪問第一層的樹根節(jié)點，然后從左到右訪問第2層上的節(jié)點，接著是第三層的節(jié)點，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點的過程就是層序遍歷。
二叉樹層序遍歷的實現(xiàn)，需要借助之前講過的一個數(shù)據(jù)結(jié)構(gòu)——隊列。
在使用隊列之前，需要知道隊列中存放的是什么內(nèi)容，對于二叉樹的結(jié)點來說，存放的應(yīng)該是指向二叉樹結(jié)點的指針：
// 鏈式結(jié)構(gòu)：表示隊列
typedef BTNode* QDataType;
//隊列的一個結(jié)點
typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;
// 隊列的結(jié)構(gòu)
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int size;//隊列元素個數(shù)
}Queue;看一下實現(xiàn)代碼，這里直接復(fù)用隊列的內(nèi)容：
// 初始化隊列
void QueueInit(Queue* q)
{
assert(q);
q->_front = NULL;
q->_rear = NULL;
q->size = 0;
}
// 隊尾入隊列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL) {
perror("malloc fail:");
exit(1);
}
newnode->_data = data;
newnode->_next = NULL;
if (q->_front == NULL) {
q->_front = newnode;
q->_rear = newnode;
}
else {
q->_rear->_next = newnode;
q->_rear = newnode;
}
q->size++;
}
// 隊頭出隊列
void QueuePop(Queue* q)
{
assert(q);
assert(q->_front);
if (q->size == 1) {
free(q->_front);
q->_front = q->_rear = NULL;
}
else {
QNode* pnext = q->_front->_next;
free(q->_front);
q->_front = pnext;
}
q->size--;
}
// 獲取隊列頭部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->_front);
return q->_front->_data;
}
// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->_rear);
return q->_rear->_data;
}
// 獲取隊列中有效元素個數(shù)
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
// 檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}
// 銷毀隊列
void QueueDestroy(Queue* q)
{
assert(q);
if (q->_front == NULL)return;
if (q->size == 1) {
free(q->_front);
}
else {
while (q->_front) {
QNode* pnext = q->_front->_next;
free(q->_front);
q->_front = pnext;
}
}
q->_front = q->_rear = NULL;
q->size = 0;
}
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{
Queue qu; //創(chuàng)建一個隊列
QueueInit(&qu); //初始化隊列
if (root)QueuePush(&qu, root); //判斷樹是否為空樹
while (!QueueEmpty(&qu)) { //結(jié)束條件：隊列為空
BTNode* front = QueueFront(&qu); //取出隊列中首元素
QueuePop(&qu); //刪除隊首元素
printf("%c ", front->_data); //打印遍歷到的結(jié)點數(shù)據(jù)
//將下一層結(jié)點放入隊列中
if (front->_left)QueuePush(&qu, front->_left);
if (front->_right)QueuePush(&qu, front->_right);
}
printf("\n");
QueueDestroy(&qu);//銷毀隊列
}層序遍歷規(guī)則：
- 根節(jié)點的指針入隊列。
- 隊列非空，隊列中首元素出隊，將隊列下一層元素帶入隊尾（如果元素為NULL則不入隊）。
- 如果隊列為空，循環(huán)停止，遍歷結(jié)束。
關(guān)于結(jié)點數(shù)和查找
計算二叉樹結(jié)點個數(shù)
把二叉樹遞歸遍歷一遍就可以得到結(jié)點個數(shù)，每層結(jié)點遞歸時都加一。
// 二叉樹節(jié)點個數(shù)
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)return 0;
//return中遍歷了整個二叉樹，很像遞歸方式求斐波那契數(shù)
return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}計算葉子結(jié)點個數(shù)
也是需要遍歷一遍二叉樹，但是需要滿足葉子結(jié)點條件（左右孩子都為NULL）的時候才會return 1計數(shù)。
// 二叉樹葉子節(jié)點個數(shù)
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)return 0;
else if (root->_left == NULL && root->_right == NULL)return 1;
return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}計算二叉樹第k層結(jié)點個數(shù)
底層邏輯依然是遍歷二叉樹，這里計算第k層結(jié)點個數(shù)的關(guān)鍵點是通過控制每層遞歸傳入的k值判斷當前結(jié)點所在層數(shù)。
// 二叉樹第k層節(jié)點個數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)return 0;
else if (k == 1)return 1;//當k==1時說明此處遍歷的結(jié)點已經(jīng)是第k層
return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}二叉樹查找值為x的結(jié)點
查找的邏輯依然是遍歷二叉樹。
// 二叉樹查找值為x的節(jié)點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)return NULL;
else if (root->_data == x)return root;
BTNode* ret1 = BinaryTreeFind(root->_left, x);
if (ret1)return ret1; //如果左子樹找到（不為NULL），直接返回，否則返回右子樹
return BinaryTreeFind(root->_right, x);
}二叉樹的創(chuàng)建和銷毀
二叉樹的創(chuàng)建（前序遍歷）
此處講的二叉樹創(chuàng)建，是以一個所給的前序遍歷數(shù)組為基礎(chǔ)（如："ABD##E#H##CF##G##"）創(chuàng)建的。其實創(chuàng)建過程的本質(zhì)還是遞歸結(jié)構(gòu)。
// 通過前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
assert(*pi <= n);
if (a[*pi] == '#') {
(*pi)++;
return NULL;
}
//開辟結(jié)點空間
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (root == NULL) { //判斷空間是否開辟成功
perror("malloc fail:");
exit(1);
}
root->_data = a[(*pi)++];
//遞歸構(gòu)建左右子樹
root->_left = BinaryTreeCreate(a, n, pi);
root->_right = BinaryTreeCreate(a, n, pi);
return root;
}二叉樹的銷毀
二叉樹的銷毀更適合基于后序遍歷，從下往上依次銷毀。這里并不是說前序和中序遍歷無法實現(xiàn)銷毀這一過程，只是用這兩種結(jié)構(gòu)實現(xiàn)會將問題復(fù)雜化——前中序遍歷在銷毀根節(jié)點后很難在找到左右孩子結(jié)點繼續(xù)進行遞歸銷毀，而后續(xù)遍歷卻可以規(guī)避這個問題：因為在刪除根節(jié)點之前左右子樹及其結(jié)點已被釋放無需遞歸刪除。
// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root)
{
if (*root == NULL)return;
BinaryTreeDestory(&((*root)->_left));
BinaryTreeDestory(&((*root)->_right));
free(*root);
*root = NULL;
}上述代碼傳遞二級指針是為了方便根節(jié)點指針置空，傳一級指針在函數(shù)外部置空也是一種可行的解決方式。
判斷二叉樹是否為完全二叉樹
判斷一個二叉樹是否為完全二叉樹，可以使用之前講到的層序遍歷的思想。
完全二叉樹：除了最后一層，其他每一層結(jié)點都是完全填滿的，且最后一層所有結(jié)點都集中在左側(cè)。層序遍歷的過程中，如果遇到了一個結(jié)點，其無左子樹而有右子樹，那么這棵樹肯定不是完全二叉樹；另外，如果遇到了一個結(jié)點并非左右子結(jié)點都有，那么所有接下來遍歷到的結(jié)點都必須是葉子節(jié)點。
我們可以在原有的層序遍歷代碼上修改：
這里就不再粘貼一遍隊列的代碼了
// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root)
{
Queue qu;
QueueInit(&qu);
if (root)QueuePush(&qu, root);
while (!QueueEmpty(&qu)) {
BTNode* front = QueueFront(&qu);
QueuePop(&qu);
if (front == NULL)break;//如果隊列中出現(xiàn)空結(jié)點跳出循環(huán)，進行下一步判斷
//通過push將下一層結(jié)點帶入隊列
QueuePush(&qu, front->_left);
QueuePush(&qu, front->_right);
}
while (!QueueEmpty(&qu)) {
BTNode* front = QueueFront(&qu);
QueuePop(&qu);
//如果出現(xiàn)非空結(jié)點則證明不是完全二叉樹
if (front) {
QueueDestroy(&qu);
return false;
}
}
QueueDestroy(&qu);
//如果正常跳出循環(huán)則證明為完全二叉樹
return true;
}上述代碼的主要判斷邏輯是，當隊列中出現(xiàn)一個空結(jié)點時，判斷此時隊列中剩余結(jié)點是否都為空：如果隊列中剩余結(jié)點都為空則證明是完全二叉樹；如果存在非空結(jié)點則證明不是完全二叉樹。
具體代碼演示
這里來測試一下之前所寫的二叉樹的接口函數(shù)：
int main()
{
char arr[] = "ABD##E#H##CF##G##";
int i = 0;
BTNode* treeroot = BinaryTreeCreate(arr, sizeof(arr) / sizeof(arr[0]), &i);
printf("結(jié)點個數(shù)：%d\n", BinaryTreeSize(treeroot));
printf("葉子結(jié)點個數(shù)：%d\n", BinaryTreeLeafSize(treeroot));
int k;
printf("輸入計算第幾層的結(jié)點個數(shù)：");
scanf("%d", &k);
printf("第k層結(jié)點個數(shù)： % d\n", BinaryTreeLevelKSize(treeroot, k));
BTNode* node = BinaryTreeFind(treeroot, 'C');
printf("%c\n", node->_data);
printf("二叉樹前序遍歷：");
BinaryTreePrevOrder(treeroot);
printf("\n");
printf("二叉樹中序遍歷：");
BinaryTreeInOrder(treeroot);
printf("\n");
printf("二叉樹后序遍歷：");
BinaryTreePostOrder(treeroot);
printf("\n");
printf("二叉樹層序遍歷：");
BinaryTreeLevelOrder(treeroot);
printf("是否為完全二叉樹：%d",BinaryTreeComplete(treeroot));
BinaryTreeDestory(&treeroot);
return 0;
}下面是所創(chuàng)建樹的結(jié)構(gòu)：?
?
下面是運行結(jié)果：?
文章來源：http://www.zghlxwxcb.cn/news/detail-842885.html
結(jié)語
關(guān)于二叉樹鏈式結(jié)構(gòu)的內(nèi)容到這里就結(jié)束了。本篇博客圍繞二叉樹的遍歷，結(jié)點個數(shù)計算以及數(shù)值查找等內(nèi)容展開。關(guān)于二叉樹更多有趣的內(nèi)容還遠遠不止這些，不過再次深入時就會以C++的方式來給大家呈現(xiàn)，如果對后續(xù)內(nèi)容感興趣的話，還請大家多多關(guān)注博主，感謝大家的支持。文章來源地址http://www.zghlxwxcb.cn/news/detail-842885.html
到了這里，關(guān)于初階數(shù)據(jù)結(jié)構(gòu)之---二叉樹鏈式結(jié)構(gòu)（二叉樹的構(gòu)建，二叉樹的前序，中序，后序和層序遍歷，計算二叉樹結(jié)點個數(shù)，第k層結(jié)點個數(shù)，葉子結(jié)點個數(shù)，判斷是否為完全二叉樹）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
