溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“c語言數據結構之鏈式二叉樹怎么實現”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“c語言數據結構之鏈式二叉樹怎么實現”文章能幫助大家解決問題。
所謂二叉樹遍歷 (Traversal) 是按照某種特定的規則，依次對二叉樹中的節點進行相應的操作，并且每個節點只操作一次。 訪問結點所做的操作依賴于具體的應用問題。遍歷 是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎。
按照規則，二叉樹的遍歷分為： 前序遍歷、中序遍歷、后序遍歷的遞歸遍歷，層序遍歷的非遞歸遍歷下面將以下面的二叉樹為例講解四種遍歷
二叉樹的前序遍歷也叫先序遍歷，遍歷的順序為：根、左子樹、右子樹，即遇到一棵樹，先訪問根節點，再訪問左子樹和右子樹，訪問左子樹和右子樹的過程又分為先訪問根節點，再訪問左子樹和右子樹，這是一個遞歸訪問的過程，因此前序遍歷屬于遞歸遍歷
遍歷的過程將以文字和圖片兩種方式展現
遍歷過程：
先遇到根節點1，訪問根節點1，再訪問1的左子樹
1的左子樹：遇到根節點2，訪問根節點2，再訪問2的左子樹，2的左子樹只有一個根節點3，3的左右子樹為空因此不需要訪問3的左右子樹，訪問根節點3便結束，2的左子樹遍歷結束訪問2的右子樹，2的右子樹為空即不用訪問，此時2的整顆樹遍歷結束，即1的左子樹遍歷結束，然后接著訪問1的右子樹
1的右子樹：遇到根節點4，訪問根節點4，再訪問4的左子樹，4的左子樹只有一個根節點5，5的左右子樹為空因此不需要訪問5的左右子樹，訪問根節點5便結束，4的左子樹遍歷結束訪問4的右子樹，4的右子樹只有一個根節點6，6的左右子樹為空因此不需要訪問6的左右子樹，訪問根節點6便結束，此時4的整顆樹遍歷結束，即1的右子樹遍歷結束
整棵樹遍歷完成，遍歷序列為：1 2 3 4 5 6
遍歷圖示：
二叉樹的中序遍歷也叫中根遍歷，遍歷的順序為：左子樹、根、右節點，即遇到一棵樹，先訪問它的左子樹，再訪問根，最后訪問右子樹，訪問左子樹和右子樹的過程又分為先訪問左子樹，再訪問根和右子樹，這是一個遞歸訪問的過程，因此中序遍歷也屬于遞歸遍歷
遍歷的過程將以文字和圖片兩種方式展現
遍歷過程：
遇到根節點1，先不訪問根節點，先訪問1的左子樹
1的左子樹：遇到根節點2，先不訪問根節點2，先訪問2的左子樹：2的左子樹只有一個根節點3，3的左右子樹為空因此不需要訪問3的左右子樹，訪問根節點3便結束，此時2的左子樹結束，訪問根節點2，然后訪問2的右子樹，2的右子樹為空則不訪問，此時2的整顆樹遍歷結束，即1的左子樹遍歷結束
訪問根節點1，接著訪問1的右子樹
1的右子樹：遇到根節點4，先不訪問根節點4，先訪問4的左子樹：遇到根節點5，5的左右子樹為空因此不需要訪問5的左右子樹，訪問根節點5便結束，此時4的左子樹訪問結束，訪問根節點4，接著訪問4的右子樹，4的右子樹只有一個根節點6，6的左右子樹為空因此不需要訪問6的左右子樹，訪問根節點6便結束，此時4的整棵樹訪問結束，即1的右子樹訪問結束
整棵樹遍歷完成，遍歷序列：3 2 1 5 4 6
遍歷圖示：
二叉樹的后序遍歷也叫后根遍歷，遍歷的順序為：左子樹、右子樹、根，即遇到一棵樹，先訪問它的左子樹，再訪問右子樹，最后訪問根，訪問左子樹和右子樹的過程又分為先訪問左子樹，再訪問右子樹和根，這是一個遞歸訪問的過程，因此后序遍歷也屬于遞歸遍歷
遍歷的過程將以文字和圖片兩種方式展現
遍歷過程：
遇到根節點1，先不訪問根節點1，先訪問左子樹
1的左子樹：遇到根節點2，先不訪問根節點2，先訪問2的左子樹：2的左子樹只有根節點3，3的左右子樹為空因此不需要訪問3的左右子樹，訪問根節點3便結束，此時2的左子樹訪問結束，接著訪問2的右子樹，2的右子樹為空因此不需要訪問，此時2的左右子樹訪問結束，最后訪問根節點2，此時2的整顆樹訪問結束，即1的左子樹訪問結束，接著訪問1的右子樹
1的右子樹：遇到根節點4，先不訪問根節點4，先訪問4的左子樹：5的左右子樹為空因此不需要訪問5的左右子樹，訪問根節點5便結束，此時4的左子樹訪問結束，接著訪問4的右子樹，6的左右子樹為空因此不需要訪問6的左右子樹，訪問根節點6便結束，此時4的左右子樹遍歷結束，最后訪問根節點4,4的整顆樹訪問結束，即1的右子樹訪問結束
最后訪問根節點1，整棵樹遍歷結束，遍歷序列：3 2 5 6 4 1
遍歷圖示：
除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設二叉樹的根節點所在層數為1， 層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然后從左到右訪問第 2 層上的節點，接著是第三層的節點，以此類推， 自上而下，自左至右逐層訪問樹的結點的過程就是層序遍歷。
遍歷圖示：
由上圖可以看出，層序遍歷為非遞歸遍歷
鏈式二叉樹的實現包括二叉樹的創建、遍歷、銷毀、求節點個數、求葉子節點個數、求二叉樹的深度、求第k層節點個數、查找、判斷是否是完全二叉樹等
下面我們一一來實現這些接口
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;給定一個前序遍歷字符串，按照此字符串以指針方式構建一顆二叉樹
給定字符串ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空樹
代碼設計思路：
函數參數為字符串指針和下標指針，利用遞歸的思想，首先判斷是否遇到空格，遇到空格則跳過該空格即下標加1并返回，接著構建一個節點，當前字符指針指向的字符賦值給節點的值域然后下標加1，將字符指針和下標傳參調用遞歸函數然后用節點的左指針接收。再將字符指針和下標傳參調用遞歸函數然后用節點的右指針接收，最后返回節點指針
BTNode *TreeBuild(char *arr,int* i)
{
if(arr[*i]=='#')//遇到空格則跳過該空格
{
(*i)++;
return NULL;
}
// 建立節點
BTNode *root=(BTNode *)malloc(sizeof(BTNode));
//節點的值為當前下標指向的字符
rot->data=arr[(*i)++];
//調用遞歸，并用節點的左指針接收
root->left=TreeBuild(arr,i);
//調用遞歸，并用節點的左指針接收
root->right=TreeBuild(arr,i);
return root;
}前序遍歷的過程在前面已經介紹，我們按照過程設計相應的函數
代碼設計思路：
利用遞歸的思想，首先判斷當前節點是否為空，為空則直接返回，先打印當前節點的值，再將自己的左子樹作為參數調用遞歸遍歷，最后將自己的右子樹作為參數調用遞歸遍歷
代碼：
void PreOrder(BTNode* root)
{
if (root == NULL)//當前節點為空則直接返回
return NULL;
printf("%d ", root->data);//打印當前節點的值
PreOrder(root->left);//遞歸遍歷左子樹
PreOrder(root->right);//遞歸調用右子樹
}中序遍歷的過程在前面已經介紹，我們按照過程設計相應的函數
代碼設計思路：
利用遞歸的思想，首先判斷當前節點是否為空，為空則直接返回，先將自己的左子樹作為參數調用遞歸遍歷，再打印當前節點的值，最后將自己的右子樹作為參數調用遞歸遍歷
代碼：
void InOrder(BTNode* root)
{
if (root == NULL)//當前節點為空則直接返回
return NULL;
InOrder(root->left);//遞歸遍歷左子樹
printf("%d ", root->data);//打印當前節點的值
InOrder(root->right);//遞歸調用右子樹
}后序遍歷的過程在前面已經介紹，我們按照過程設計相應的函數
代碼設計思路：
利用遞歸的思想，首先判斷當前節點是否為空，為空則直接返回，先將自己的左子樹作為參數調用遞歸遍歷，再將自己的右子樹作為參數調用遞歸遍歷，最后打印當前節點的值
void PostOrder(BTNode* root)
{
if (root == NULL)//當前節點為空則直接返回
return NULL;
PostOrder(root->left);//遞歸遍歷左子樹
PostOrder(root->right);//遞歸調用右子樹
printf("%d ", root->data);//打印當前節點的值
}層序遍歷的過程在前面已經介紹，我們按照過程設計相應的函數
代碼設計思路：
利用隊列，首先判斷當前節點是否為空，為空則直接返回。把第一個節點的指針入隊，然后進去循環（循環條件是隊列不為空），定義一個指針拿到隊列的第一個節點，然后出隊并打印節點的值，出隊之后將節點的左右孩子入隊，如果節點的左孩子存在，則將左孩子指針入隊，如果節點的右孩子存在，則將右孩子指針入隊，然后又繼續取隊頭元素打印，直到隊列為空
代碼：
void LevelOrder(BTNode *root)
{
Queue q;//定義一個隊列
QueueInit(&q);//隊列初始化
if (root == NULL)//當前節點為空則返回
return;
QueuePush(&q, root);//將第一個節點指針入隊
while (!(QueueEmpty(&q)))//循環條件是隊列不為空，隊列為空則結束
{
BTNode* front = QueueFront(&q);//取隊頭節點
printf("%d ", front->data);//打印節點的值
QueuePop(&q);//出隊
if (front->left)//左孩子存在，則將左孩子指針入隊
{
QueuePush(&q, front->left);
}
if (front->right)//右孩子存在，則將右孩子指針入隊
{
QueuePush(&q, front->right);
}
}
QueueDestroy(&q);//銷毀隊列
}銷毀的過程：先從最后一層開始銷毀，先銷毀左子樹，再銷毀右子樹，最后銷毀根，即用到后序遍歷的思想，遞歸銷毀
代碼設計思路：
利用后序遍歷的思想，首先判斷當前節點是否為空，為空則返回。先將左孩子指針作為參數調用遞歸，再將左孩子指針作為參數調用遞歸，最后將根節點釋放
代碼：
void BinaryTreeDestory(BTNode* root)
{
if(root == NULL)//為空則返回
return;
BinaryTreeDestory(root->left);//遞歸銷毀左子樹
BinaryTreeDestory(root->right);//遞歸銷毀右子樹
free(root);//最后銷毀根節點
}一顆樹的節點個數可以分為左子樹的節點數加上右子樹的節點數再加1即根節點，同樣是遞歸求節點個數
代碼設計思路：
利用遞歸的思想，首先判斷當前節點是否為空，為空則返回0，然后將左孩子指針作為參數調用遞歸，再將右孩子指針作為參數調用遞歸，最后將兩者的值加1返回，即節點個數等于左子樹的節點個數+右子樹的節點個數+1
代碼：
int TreeSize(BTNode* root)
{
if (root == NULL)//當前節點為空則返回0
return 0;
//遞歸左子樹和右子樹，然后將兩者的和加1返回
return TreeSize(root->left) + TreeSize(root->right) + 1;
}一顆樹的葉子節點個數可以分為左子樹的葉子節點個數+右子樹的葉子節點個數，即同樣利用遞歸求葉子節點個數
代碼設計思路：
利用遞歸的思想，首先判斷當前節點是否為空，為空則返回0，然后判斷當前節點是否為葉子結點，左孩子和右孩子都為空的節點即為葉子節點，為葉子節點則返回1，接著遞歸左子樹和右子樹，并返回兩者的和
代碼：
int TreeLeafSize(BTNode* root)
{
if (root ==NULL)//當前節點為空則返回0
return 0;
if (root->left == NULL && root->right == NULL)//當前節點為葉子結點則返回1
return 1;
//遞歸左子樹和右子樹，并返回兩者的和
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}一顆樹的深度等于左右子樹的較大的深度加1（加根節點），即利用遞歸求左右子樹的深度，將左右子樹較大的深度加1返回
代碼設計思路：
利用遞歸的思想，首先判斷當前節點是否為空，為空則返回0，再判斷當前節點是否為葉節點，是葉節點則返回1，接著遞歸左子樹和右子樹，取較大的深度加1返回
代碼：
int TreeHeight(BTNode* root)
{
if (root == NULL)//當前節點為空則返回空
return 0;
if (root->left == NULL && root->right == NULL)//當前節點為葉節點則返回1
return 1;
int left = TreeHeight(root->left);//遞歸左子樹
int right = TreeHeight(root->right);//遞歸右子樹
return left > right ? left + 1 : right + 1;//將左右子樹較大的深度加1返回
}整顆樹的第k層可以看成第二層的第k-1層，第三層的k-2層，第k層的第1層，即整棵樹的第k層的節點數等于左右子樹的第k-1層節點子樹，即利用遞歸求左右子樹的k-1層節點個數
代碼設計思路：
利用遞歸的思想，首先判斷當前節點是否為空，為空則返回0，再判斷當前層數是否為1，為1則返回1，然后遞歸左子樹，傳左子樹指針和k-1，然后遞歸右子樹，傳右子樹指針和k-1，最后返回兩者的和
代碼：
int TreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)//當前節點為空則返回0
return 0;
if (k == 1)//當前層數為1則返回1
return 1;
//遞歸左子樹和右子樹，返回兩者的值
return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}查找值為x的節點，并返回節點的指針
代碼設計思路：
利用遞歸的思想，首先判斷當前節點是否為空，為空則返回空，不為空則判斷當前節點的值是否等于x，等于則返回該節點，然后遞歸查找左子樹，如果遞歸左子樹返回的值不為空說明找到則返回該值，接著遞歸右子樹，如果遞歸右子樹返回的值不為空說明找到則返回該值，遞歸左右子樹都未找到說明x不存在，返回空
代碼：
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)//當前節點為空則返回空
return NULL;
if (root->data == x)//當前節點的值等于x則返回該節點
return root;
//遞歸左子樹查找
BTNode* left = BinaryTreeFind(root->left,x);
//返回的值不為空說明已找到，返回該值
if (left)
return left;
//遞歸右子樹查找
BTNode* right = BinaryTreeFind(root->right, x);
//返回的值不為空說明已找到，返回該值
if (right)
return right;
//遞歸左右子樹均為找到，則趕回空
return NULL;
}上一篇文章介紹了完全二叉樹的概念，完全二叉樹可以看成是滿二叉樹以最后一層開始從右往左挖去了幾個節點而成，即完全二叉樹的倒數第二層是滿的，倒數第一層不可能存在只有右孩子而沒有左孩子的情況
代碼設計思路：
類似于層序遍歷的思想，利用隊列，首先判斷第一個節點是否為空，為空則返回，然后將第一個節點入隊，接著進入循環（循環條件為隊列不為空），取隊頭元素并出隊，如果取到的隊頭元素為空，說明此時已經此時二叉樹剛好遍歷結束，則退出循環檢查后面隊列值地情況如果是完全二叉樹，則隊列后面應該都是空，如果存在不為空的元素則證明不是完全二叉樹。如果取到的隊頭元素不為空，則將其左右孩子（為空也一樣）入隊，如果循環正常結束，則證明是完全二叉樹
代碼：
bool BinaryTreeComplete(BTNode* root)
{
Queue q;//定義一個隊列
QueueInit(&q);//隊列初始化
if (root == NULL)//當前節點為空則返回
return;
QueuePush(&q, root);//將第一個節點入隊
while (!(QueueEmpty(&q)))
{
//取隊頭元素并出隊
BTNode* front = QueueFront(&q);
QueuePop(&q);
//取到的隊頭元素為空則退出循環，檢查隊列后面值地情況
if (front==NULL)
{
break;
}
else//不為空則將左右孩子入隊
{
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;//循環正常結束則返回true
}關于“c語言數據結構之鏈式二叉樹怎么實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
