一、前置說明
其他數(shù)據(jù)結(jié)構(gòu)不同，二叉樹的增刪查改接口實現(xiàn)的意義不大（后續(xù)搜索樹的增刪查改才有意義）。普通初階二叉樹更重要的是學習控制結(jié)構(gòu)，為后續(xù)的AVL樹、紅黑樹等高級數(shù)據(jù)結(jié)構(gòu)打下基礎(chǔ)。同時大部分OJ題也出在此處。
二、二叉樹的遍歷
所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點進行相應(yīng)的操作，并且每個節(jié)點只操作一次。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題。
?
按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷：
- 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問順序：根節(jié)點—>左子樹—>右子樹
- 中序遍歷(Inorder Traversal)——訪問順序：左子樹—>根節(jié)點—>右子樹
- 后序遍歷(Postorder Traversal)——訪問順序：左子樹—>右子樹—>根節(jié)點
2.1前序遍歷
【代碼思路】:
- 若二叉樹為空，則直接返回。
- 訪問根節(jié)點。
- 遞歸遍歷左子樹，即調(diào)用前序遍歷函數(shù)，傳入左子樹的根節(jié)點。
- 遞歸遍歷右子樹，即調(diào)用前序遍歷函數(shù)，傳入右子樹的根節(jié)點
代碼：
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
2.2中序遍歷
【代碼思路】：
- 首先判斷二叉樹是否為空，若為空則直接返回。
- 對當前節(jié)點的左子樹進行中序遍歷，即遞歸調(diào)用中序遍歷函數(shù)。
- 訪問當前節(jié)點的值。
- 對當前節(jié)點的右子樹進行中序遍歷，即遞歸調(diào)用中序遍歷函數(shù)。
代碼：
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
2.3 后序遍歷
【代碼思路】：
- 判斷當前節(jié)點是否為空，若為空則返回。
- 遞歸遍歷當前節(jié)點的左子樹。
- 遞歸遍歷當前節(jié)點的右子樹。
- 訪問當前節(jié)點。
代碼：
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
三、以前序遍歷為例，遞歸圖解
前序遍歷遞歸圖解：
上述三種遍歷結(jié)果：
- 前序遍歷結(jié)果：1 2 3 4 5 6
- 中序遍歷結(jié)果：3 2 1 5 4 6
- 后序遍歷結(jié)果：3 2 5 6 4 1
四、層序遍歷
層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設(shè)二叉樹的根節(jié)點所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先訪問第一層的樹根節(jié)點，然后從左到右訪問第2層上的節(jié)點，接著是第三層的節(jié)點，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點的過程就是層序遍歷。
【代碼思路】：（核心思想：上一層出時帶下一層進隊列，即根節(jié)點出棧時，根節(jié)點的孩子節(jié)點入棧）
- 首先將根節(jié)點入棧。
- 循環(huán)進行以下操作，直到棧為空。
。彈出棧頂元素，并將其值輸出；
。如果該節(jié)點有右子節(jié)點，則將右子節(jié)點入棧。
。 如果該節(jié)點有左子節(jié)點，則將左子節(jié)點入棧
棧相關(guān)代碼自行查看：棧和隊列代碼實現(xiàn)
代碼：
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);
if(front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
printf("\n");
QueueDestroy(&q);
}
五、節(jié)點個數(shù)以及高度等
5.1 二叉樹節(jié)點個數(shù)
【代碼思路】：
- 如果二叉樹為空，則節(jié)點個數(shù)為0。
- 否則，節(jié)點個數(shù)等于根節(jié)點的個數(shù)加上左子樹的節(jié)點個數(shù)和右子樹的節(jié)點個數(shù)。
- 遞歸計算左子樹的節(jié)點個數(shù)。
- 遞歸計算右子樹的節(jié)點個數(shù)。
- 返回根節(jié)點個數(shù)加上左子樹和右子樹的節(jié)點個數(shù)。
代碼：
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
5.2二叉樹葉子節(jié)點個數(shù)
【代碼思路】：
- 判斷根節(jié)點是否為空，若為空，則返回0。
- 判斷根節(jié)點的左右子樹是否為空，若都為空，則表示根節(jié)點是葉子節(jié)點，返回1。
- 通過遞歸分別計算左子樹和右子樹的葉子節(jié)點個數(shù)，并返回左子樹和右子樹的葉子節(jié)點個數(shù)之和。
代碼：
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);
}
5.3 二叉樹第k層節(jié)點個數(shù)
【代碼思路】：
- 判斷二叉樹是否為空，如果是則返回0。
- 判斷k是否等于1，如果是則返回1，表示當前層為第k層，只有一個節(jié)點。
- 如果以上條件都不滿足，則遞歸計算二叉樹的左子樹和右子樹的第k-1層節(jié)點個數(shù)，然后將左右子樹的第k-1層節(jié)點個數(shù)相加，即為二叉樹第k層節(jié)點個數(shù)。
代碼：
int BinaryTreeLevelKSize(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
5.4 二叉樹查找值為x的節(jié)點
【代碼思路】：
- 如果當前節(jié)點為空，則返回空。
- 如果當前節(jié)點的值等于x，則返回當前節(jié)點。
- 否則，遞歸查找左子樹，如果找到則返回左子樹中的節(jié)點。
- 否則，遞歸查找右子樹，如果找到則返回右子樹中的節(jié)點。
代碼：
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* ret1 = BTreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = BTreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}
5.5 二叉樹的高度
【代碼思路】：
- 如果樹為空樹，則高度為0。
- 如果樹不為空樹，則高度為左子樹的高度和右子樹的高度中的較大值加1。
- 遞歸地計算左子樹和右子樹的高度，并取較大值。
- 返回左子樹和右子樹高度的較大值加1。
代碼：
int BinaryTreeHeight(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int LeftHeight = BinaryTreeHeight(root->left);
int RightHeight = BinaryTreeHeight(root->right);
return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}
六、二叉樹的創(chuàng)建和銷毀
6.1 構(gòu)建二叉樹
Tips： 構(gòu)建二叉樹的方式有很多， 這里我們通過前序遍組"ABD##E#H##CF##G##"構(gòu)建二叉樹。（‘#’表示空樹）
【代碼思路】：
- 如果節(jié)點為“#”表示空，返回空。
- 遍歷創(chuàng)建左子樹，并和根節(jié)點鏈接。
- 遍歷創(chuàng)建右子樹，并和根節(jié)點鏈接。
- 返回根節(jié)點
代碼：
typedef int BTDataType;
typedef struct BinaryTreeNode//結(jié)構(gòu)體類型
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
//創(chuàng)建節(jié)點
BTNode* BuyNode(BTDataType x)
{
BTNode* Node = (BTNode*)malloc(sizeof(BTNode));
if (Node == NULL)
{
perror("malloc fail");
exit(-1);
}
Node->data = x;
Node->left = NULL;
Node->right = NULL;
return Node;
}
//先序創(chuàng)建二叉樹
BTNode* createrroot(char* a, int* pi)
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = BuyNode(a[*pi]);
(*pi)++;
root->left = createrroot(a, pi);
root->right = createrroot(a, pi);
return root;
}
6.2 二叉樹的銷毀
【代碼思路】：
- 從根節(jié)點開始，遞歸地銷毀左子樹。
- 從根節(jié)點開始，遞歸地銷毀右子樹。
- 將根節(jié)點從內(nèi)存中刪除。
代碼：
void BinaryTreeDestroy(BTNode* root)
{
if (root == NULL)
return;
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
free(root);
}
6.3 判斷二叉樹是否為完全二叉樹
（博主數(shù)據(jù)結(jié)構(gòu)初階是用C語言來實現(xiàn)的，所以此處直接棧代碼從博主代碼倉庫中拷貝過來的，讀者可以用其他語言來實現(xiàn)，大同小異）
【代碼思路】：
- 遍歷二叉樹，使用層次遍歷的方式，從根節(jié)點開始，逐層遍歷每個節(jié)點。
- 當遇到第一顆空樹時停止遍歷。
- 從第一顆空樹開始，后續(xù)節(jié)點如果有非空就不是完全二叉樹，否則為完全二叉樹。
棧相關(guān)代碼自行查看：棧和隊列代碼實現(xiàn)
代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-676784.html
int BinaryTreeComplete(BTNode* root)
{
Que q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
//遇空就跳過
if (front==NULL)
{
break;
}
QueuePush(&q, root->left);
QueuePush(&q, root->right);
}
//檢查后續(xù)節(jié)點是否有非空
//有非空就不是完全二叉樹
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
【數(shù)據(jù)結(jié)構(gòu)入門指南】二叉樹順序結(jié)構(gòu): 堆及實現(xiàn)（全程配圖，非常經(jīng)典）文章來源地址http://www.zghlxwxcb.cn/news/detail-676784.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)入門指南】二叉樹鏈式結(jié)構(gòu)的實現(xiàn)（保姆級代碼思路解讀，非常經(jīng)典）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
