??? 文章由@不準備禿的大偉原創(chuàng) ???
??? 若有轉(zhuǎn)載，請聯(lián)系博主哦~????
??? 致力學(xué)好編程的寶藏博主，代碼興國！???
? ? ? ? halo鐵汁們，沒錯又是你們?nèi)艘娙藧?，花見花開的大偉啊，今天也是周六，大偉心情也是非常的美妙啊~ 所以就迫不及待的給大家來更新我們的博客啦，那么今天要學(xué)習(xí)的內(nèi)容就是大家早已棋盤不已的二叉樹啦，但是在學(xué)習(xí)二叉樹之前，鐵汁們有沒有把堆認真的學(xué)完呢？沒有？趕快去看！：堆?
? ? ? ? OK，那么廢話不多說，我們開始今天的學(xué)習(xí)內(nèi)容吧！
? ? ? ? 那么我們上一篇博客也是簡單的介紹了一下二叉樹的基本概念，那么今天我們就來看一看二叉樹的一些操作以及代碼的實現(xiàn)。
? ? ? ? 首先呢，我們先來思考一下一個很重要的問題：我們的二叉樹，用什么方法實現(xiàn)好呢？是數(shù)組，還是鏈式結(jié)構(gòu)？
? ? ? ? 回想一下，我們的堆是不是用數(shù)組的方法實現(xiàn)的，但是有一點不知道大家有沒有注意到大偉上一篇在介紹堆時說的一句話：“堆的邏輯結(jié)構(gòu)是啥樣的？和完全二叉樹一個樣”，也就是說，我們的完全二叉樹也就是用和堆一樣的實現(xiàn)方法：數(shù)組（這樣可以保證數(shù)據(jù)浪費量很小，大家可以想一想為什么）。
????????那么問題來了，如果是別的二叉樹呢？如果深度比較深，但是最后一層只有一個數(shù)據(jù)呢？這個時候的空間浪費是不是就是比較大了？ 所以，普通的二叉樹（當(dāng)然包括完全二叉樹）我們使用鏈式結(jié)構(gòu)實現(xiàn)就比較銀杏。
????????在學(xué)習(xí)二叉樹的基本操作前，需先要創(chuàng)建一棵二叉樹，然后才能學(xué)習(xí)其相關(guān)的基本操作。由于現(xiàn)在大家對二叉樹結(jié)構(gòu)掌握還不夠深入，為了降低大家學(xué)習(xí)成本，咱們此刻手動快速創(chuàng)建一棵簡單的二叉樹，快速進入二叉樹的操作學(xué)習(xí)，等二叉樹結(jié)構(gòu)了解的差不多時，我們反過頭再來研究二叉樹真正的創(chuàng)建方式。?OK不OK？(^▽^ )
? ? ? ? 鐵汁們還記得上一篇博客里面我們提到的二叉樹是怎么實現(xiàn)的嗎？沒錯，左孩子右兄弟法，于是我們結(jié)構(gòu)體中就需要一個left指針，一個right指針，還需要一個當(dāng)前節(jié)點的數(shù)據(jù)data。OK，前提需要已經(jīng)準備好了，現(xiàn)在，開碼！
? ? ? ? BT.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
// 通過前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹（直接在.c中實現(xiàn)）
BTNode* BTCreate();
// 二叉樹銷毀
void BinaryTreeDestory(BTNode* root);
// 二叉樹節(jié)點個數(shù)
int BinaryTreeSize(BTNode* root);
// 二叉樹葉子節(jié)點個數(shù)
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹第k層節(jié)點個數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹查找值為x的節(jié)點
BTNode* BinaryTreeFind(BTNode* root,int x);
// 二叉樹前序遍歷
void BinaryTreePrevOrder(BTNode* root);
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root);
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root);
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root);
// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root);? ? ? ? BT.c
? ? ? ? ? ? ? ? 手動創(chuàng)建一個二叉樹：
BTNode* BTCreate()
{
BTNode* n1 = BuyBTNode(1);
BTNode* n2 = BuyBTNode(2);
BTNode* n3 = BuyBTNode(3);
BTNode* n4 = BuyBTNode(4);
BTNode* n5 = BuyBTNode(5);
BTNode* n6 = BuyBTNode(6);
BTNode* n7 = BuyBTNode(7);
n1->left = n2;
n1->right = n4;
n2->left = n3;
n4->left = n5;
n4->right = n6;
n5->left = n7;
return n1;
}? ? ? ? 邏輯結(jié)構(gòu)如下：
? ? ? ? ? ? ? ? 銷毀二叉樹：
void BinaryTreeDestory(BTNode* root)
{
if (root == NULL) return;
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
//從根節(jié)點開始，遞歸釋放左右節(jié)點
free(root);
}????????????????二叉樹節(jié)點個數(shù)：?
int BinaryTreeSize(BTNode* root)
{
//若根不為空，則遞歸向下找，每到一個節(jié)點加一
return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}? ? ? ? ? ? ? ? ?二叉樹葉子節(jié)點個數(shù)：
int BinaryTreeLeafSize(BTNode* root)
{
//若根為空
if (root == NULL) return 0;
//若根不為空，但是沒有孩子節(jié)點，才加一
if (root && root->left == NULL && root->right == NULL) return 1;
//遞歸向下尋找
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}????????????????二叉樹第k層節(jié)點個數(shù)：
int BinaryTreeLevelKSize(BTNode* root, int k)
{
//若當(dāng)前節(jié)點為空，則返回為0
if (root == NULL) return 0;
//若尋找到需要的尋找的層數(shù)的某一個節(jié)點，則返回1
if (k == 1) return 1;
//從根依次往下找，并且使的k == 1時，就是需要的層數(shù)
return BinaryTreeLevelKSize(root->left, --k) + BinaryTreeLevelKSize(root->right, --k);
}
????????????????二叉樹查找值為x的節(jié)點：
BTNode* BinaryTreeFind(BTNode* root,int x)
{
if (root == NULL) return false;
if (root->data == x) return root;
//若需要尋找的值不是根節(jié)點，則需要記錄一下后面的值為x的節(jié)點，以便于返回上一層
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1) return ret1;
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2) return ret2;
return NULL;
}? ? ? ? 鐵汁們肯定還不知道前序遍歷是個啥玩意吧，哈哈。那么乘次機會，大偉把前序遍歷，中序遍歷，后序遍歷已經(jīng)層序遍歷都給大家講一講：
????????學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉 樹中的節(jié)點進行相應(yīng)的操作，并且每個節(jié)點只操作一次。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題。 遍歷 是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎(chǔ)。
1. 前序遍歷 —— 訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之前。
2. 中序遍歷 —— 訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之中（間）。
3. 后序遍歷 —— 訪問根結(jié)點的操作發(fā)生在遍歷其左右子樹之后。
4. 層序遍歷 —— 從根節(jié)點開始按照一層一層的訪問節(jié)點?
? ? ? ? 實例如下圖：?
? ? ? ? 前序遍歷是：?1 2 4 N N 5 N N 3 6 N N 7 N N
? ? ? ? 中序遍歷是： N 4 N 2 N 5 N 1 N 6 N 3 N 7 N
? ? ? ? 后序遍歷是：?N N 4 N N 5 2 N N 6 N N 7 3 1
? ? ? ? ?層序遍歷是： 1 2 3 4 5 6 7 N N N N N N N N? ? ? ??
?????????????????二叉樹前序遍歷 ：
????????根據(jù)邏輯，我們知道每個最小子樹，前序遍歷都是 左-根-右的方式遍歷的，那接下來我們來看看代碼：
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
//先打印當(dāng)前根節(jié)點
printf("%d ", root->data);
//再向下往左找
BinaryTreePrevOrder(root->left);
//再向下往右找
BinaryTreePrevOrder(root->right);
}
? ? ? ? ? ? ? ? 二叉樹的中序遍歷：
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
//先從根節(jié)點往左找
BinaryTreeInOrder(root->left);
//等左邊最小子樹找完了再打印
printf("%d ", root->data);
//再往右找
BinaryTreeInOrder(root->right);
}? ? ? ? ? ? ? ? 二叉樹的后序遍歷：
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
//先從根節(jié)點往左找
BinaryTreePostOrder(root->left);
//再找向右找
BinaryTreePostOrder(root->right);
//等右邊最小子樹找完了再打印
printf("%d ", root->data);
}????????????????二叉樹的層序遍歷：?
? ? ? ? 這個就比較困難了，其實也沒有什么很好的方法，不過一般人估計也不會想到，大偉這里就直接給大家答案吧：我們需要借助隊列來實現(xiàn)二叉樹的層序遍歷，那么思路是什么樣子的呢？
?????????其實我們實現(xiàn)層序就是要借助隊列的性質(zhì)：后進先出，我們就先把根節(jié)點放進隊列，然后放根的左節(jié)點，再放右節(jié)點，將根打印出來后出隊列，將隊頭出隊列，將根改為隊列的的頭，再進當(dāng)前隊頭的左右節(jié)點，依次循環(huán)，直到隊列為空。代碼簡單（這里就不給隊列的一系列的操作了，忘記的，或者想去復(fù)習(xí)復(fù)習(xí)的鐵汁們點這里 ：-> 隊列）
void LevelOrder(BTNode* root)
{
Queue q;
if (root == NULL)
return;
//隊列初始化
QueueInit(&q);
//入隊列
QueuePush(&q, root);
//若隊列不為空
while (!QueueEmpty(&q))
{
printf("%d\n", QueueFront(&q)->val);
BTNode* a = root->left;
BTNode* b = root->right;
//出隊列的頭
QueuePop(&q);
//若左不為空
if (a)
QueuePush(&q, a);
//若右不為空
if (b)
QueuePush(&q, b);
//若不為空，則根改為當(dāng)前隊列的頭
if (!QueueEmpty(&q))
root = QueueFront(&q);
}
}? ? ? ? ? ? ? ? ?判斷二叉樹是不是完全二叉樹：
????????其實我們判斷二叉樹是不是完全二叉樹也有很多辦法，但是大偉這里講一種不是很常見的方法，但是是很容易理解的方法：那就是先假設(shè)二叉樹是一個完全二叉樹，然后通過最后一層所有孩子節(jié)點的下標(biāo)的索引來判斷，若有下標(biāo)索引超過實際二叉樹的總節(jié)點個數(shù)，那么這個二叉樹就不是完全二叉樹了。代碼如下：
bool BinaryTreeComplete(BTNode* root, int index,int n) {
//n為二叉樹的總節(jié)點個數(shù)
// 如果當(dāng)前節(jié)點為空，直接返回 true
if (root == NULL) {
return true;
}
// 如果當(dāng)前節(jié)點的索引超過節(jié)點總數(shù)，則返回 false
if (index >= n) {
return false;
}
// 遞歸檢查左子樹和右子樹
return BinaryTreeComplete(root->left, 2 * index + 1,n) &&
BinaryTreeComplete(root->right, 2 * index + 2,n);
}? ? ? ? ? ? ? ? OK，到這里我們所有的二叉樹的基本操作就寫完了，那么接下來，來玩玩？
? ? ? ? test.c
????????
int main()
{
BTNode* root = BTCreate();
//總節(jié)點個數(shù)
int n = BinaryTreeSize(root);
printf("%d\n", n)
//前序
BinaryTreePrevOrder(root);
printf("\n");
//中序
BinaryTreeInOrder(root);
printf("\n");
//后序
BinaryTreePostOrder(root);
printf("\n");
if (BinaryTreeComplete(root, 0,n))
printf("是完全二叉樹");
else
printf("不是完全二叉樹");
return 0;
}? ? ? ? 我們來看一看結(jié)果：
? ? ? ? 是不是和我們想的一模一樣呢~ <(*￣▽￣*)/?
? ? ? ? 其實大偉對遞歸部分的講解不是十分詳細，但是也是希望鐵汁們能好好理解，其實我們學(xué)到這里最重要的還是代碼的練習(xí)量，所以當(dāng)鐵汁們沒事做的時候，多刷刷題，多理解理解，O不O K？
?????????到這里本篇博客已經(jīng)可以是完結(jié)了，接著二叉樹后面就是排序了，在緊接著就進入c++啦，下篇文章我會對大家介紹數(shù)據(jù)結(jié)構(gòu)初階的最后一個內(nèi)容，請大家繼續(xù)支持大偉，謝啦!!☆⌒(*＾-゜)v?文章來源：http://www.zghlxwxcb.cn/news/detail-856006.html
????????·你要做一個不動聲色的大人了。不準情緒化，不準偷偷想念，不準回頭看。去過自己另外的生活。你要聽話，不是所有的魚都會生活在同一片海里。---村上春樹
????????本篇博客也就到此為止了，送大家一碗雞湯，勉勵自己以及這世界上所有追逐夢想的赤子趁年華尚好努力提升自己，莫欺少年窮！?
文章來源地址http://www.zghlxwxcb.cn/news/detail-856006.html
到了這里，關(guān)于你真的會數(shù)據(jù)結(jié)構(gòu)嗎：二叉樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
