本篇博客給大家帶來的是用C++語言來實現堆鏈式結構和二叉樹的實現！

🐟🐟文章專欄：數據結構

🚀🚀若有問題評論區下討論，我會及時回答

??歡迎大家點贊、收藏、分享！

今日思想：你現在的懶惰將來你會買單的！

?上篇文章我們實現了二叉樹的堆的順序結構的實現具體內容請看這兩篇文章：【C++】樹和二叉樹的實現（上）-CSDN博客

【C++】樹和二叉樹的實現（下）-CSDN博客

接下來我們實現二叉樹堆的鏈式結構?！

一、二叉樹堆的鏈式結構的定義

? ? ? ? 順序結構實現堆的底層是數組，那么鏈式結構的底層是鏈表。我們先定義鏈表的結構體。

代碼實例：

//Tree.h
//定義鏈式結構二叉樹
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

二、二叉樹堆的鏈式結構的實現方法

? ? ? ? 二叉樹堆的鏈式結構的實現方法有：?前序遍歷、中序遍歷、后序遍歷、二叉樹結點個數、二叉樹葉子結點個數、二叉樹第k層結點個數、二叉樹查找值為x的結點、二叉樹的銷毀、層序遍歷、判斷二叉樹是否為完成二叉樹。

注意：這些方法的實現大部分都是遞歸的思想，即使不知道遞歸也沒事下面我會細說。

1、前序遍歷

? ? ? ??前序遍歷的規則：先遍歷根，再遍歷左子樹、最后遍歷右子樹。

遍歷順序：A->B->D->NULL->NULL->NULL->C->E->NULL->NULL->F->N->ULL->NULL? ? ?

注：大家可以根據遍歷順序來理解前序遍歷的規則。

代碼實例：

//Tree.h
//前序遍歷
void preOrder(BTNode* root);

//Tree.c
//前序遍歷-根左右
void preOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);preOrder(root->left);preOrder(root->right);
}

?短短的幾行代碼就完成了前序遍歷，讓我們看看它是怎么實現的，如圖：

? ? ? ? ? 其他的代碼實現跟上圖的注釋一樣就不多寫了，包括后面實現的中序遍歷、后序遍歷等。

注：這張圖不太清楚大家可以下載，然后在電腦自帶的畫圖上放大就行。

?2、中序遍歷

? ? ? ? 中序遍歷的規則：先遍歷左子樹，再遍歷根結點、最后是右子樹。

遍歷順序：NULL->D->NULL->B->NULL->A->NULL->E->NULL->C->NULL->F->NULL?

代碼實例：

//Tree.h
//中序遍歷
void InOrder(BTNode* root);

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

3、后序遍歷

? ? ? ? 后序遍歷的規則：先遍歷左子樹，再遍歷右子樹、最后遍歷根結點。

遍歷順序：NULL->NULL->D->NULL->B->NULL->NULL->E->NULL->NULL->F->C->A?

代碼實例：

//Tree.h
//后序遍歷
void postOrder(BTNode* root);

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

4、二叉樹結點個數

? ? ? ? 二叉樹結點個數=根結點+左子樹的結點個數+右子樹結點個數

注：只有一個根結點。

代碼實例：

//Tree.h
//二叉樹結點個數
int BinaryTreesize(BTNode* root);

//Tree.c
//二叉樹結點個數
int BinaryTreesize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreesize(root->left) + BinaryTreesize(root->right);
}

?由于時間的原因后面的實現方法放到下篇文章！！

完！！