C語言實現(xiàn)二叉樹的示例詳解
二叉樹的遍歷算法
先序遍歷算法
先序遍歷的實現(xiàn)方式在前面已經說過了，比如下面的一棵二叉樹：
我們需要先訪問根結點A，然后以先序遍歷的方式遍歷左子樹，左子樹同樣是一棵二叉樹，以同樣的方式訪問根結點B，然后先序遍歷B的左子樹，會發(fā)現(xiàn)，這是一個遞歸的過程，所以我們可以通過遞歸實現(xiàn)。 先序遍歷算法實現(xiàn)如下：
void PreOrderTraverse(BiTree t){
//判斷當前結點是否為空
if(t == NULL){
return;
}
//輸出根結點
printf("%c\t",t->data);
//先序遍歷左子樹
PreOrderTraverse(t->lchild);
//先序遍歷右子樹
PreOrderTraverse(t->rchild);
}代碼實現(xiàn)非常簡單，但是需要一定的時間理解： 我們首先傳入二叉樹的根結點，根結點不為空，所以輸出A，此時調用自身，將左孩子傳入，此時將先序遍歷左子樹。 傳入結點B依然不為空，此時輸出B，然后又調用自身，將結點B的左孩子傳入，此時將先序遍歷結點B的左子樹。 傳入結點D依然不為空，此時輸出D，然后又調用自身，將結點D的左孩子傳入，此時左孩子為空，所以函數(shù)返回，返回后就執(zhí)行先序遍歷右子樹，傳入的右孩子仍然為空，此時繼續(xù)返回，先序遍歷結點B的右孩子。 以此類推，注意理解。
我們來測試一下，因為剛剛接觸遍歷算法，所以這里，我們通過一個比較笨的方式實現(xiàn)二叉樹，然后調用先序遍歷函數(shù)：
int main(){
//創(chuàng)建根結點
BiTree root = (BiTree) malloc(sizeof(BiNode));
root->data = 'A';
//創(chuàng)建根結點的左孩子
root->lchild = (BiTree) malloc(sizeof(BiNode));
root->lchild->data = 'B';
//創(chuàng)建根結點的右孩子
root->rchild = (BiTree) malloc(sizeof(BiNode));
root->rchild->data = 'C';
//創(chuàng)建根結點的左孩子的左孩子
root->lchild->lchild = (BiTree) malloc(sizeof(BiNode));
root->lchild->lchild->data = 'D';
//創(chuàng)建根結點的左孩子的右孩子
root->lchild->rchild = (BiTree) malloc(sizeof(BiNode));
root->lchild->rchild->data = 'E';
//根結點的右孩子無左右孩子
root->rchild->lchild = NULL;
root->rchild->rchild = NULL;
//根結點的左孩子的左孩子無左右孩子
root->lchild->lchild->lchild = NULL;
root->lchild->lchild->rchild = NULL;
//根結點的左孩子右孩子無左右孩子
root->lchild->rchild->lchild = NULL;
root->lchild->rchild->rchild = NULL;
//先序遍歷
PreOrderTraverse(root);
return 0;
}運行結果：
A B D E C
中序遍歷算法
中序遍歷和后序遍歷的算法就不用分析了，過程是一樣的，只不過是操作根結點的順序變了。 中序遍歷算法實現(xiàn)如下：
void InOrderTraverse(BiTree t){
//判斷當前結點是否為空
if(t == NULL){
return;
}
//先序遍歷左子樹
InOrderTraverse(t->lchild);
//輸出根結點
printf("%c\t",t->data);
//先序遍歷右子樹
InOrderTraverse(t->rchild);
}后序遍歷算法
后序遍歷算法實現(xiàn)如下：
void PostOrderTraverse(BiTree t){
//判斷當前結點是否為空
if(t == NULL){
return;
}
//先序遍歷左子樹
PostOrderTraverse(t->lchild);
//先序遍歷右子樹
PostOrderTraverse(t->rchild);
//輸出根結點
printf("%c\t",t->data);
}非遞歸遍歷算法
遍歷思想
前面介紹了三種遍歷算法，都是通過遞歸實現(xiàn)的，雖然遞歸實現(xiàn)的代碼量非常少，但是遞歸較難理解，而且空間消耗大，所以這里我也介紹一下遍歷算法的非遞歸實現(xiàn)，具體想用哪種辦法就看自己了。
這里以中序遍歷算法的非遞歸實現(xiàn)作為例子重點講述。 當然思想還是一樣的，我們需要優(yōu)先遍歷左子樹，然后訪問根結點，最后訪問右子樹，既然是這樣，根結點我們就需要先保存下來，這里可以用棧實現(xiàn)。 比如下面的這棵二叉樹：
如何實現(xiàn)非遞歸的中序遍歷呢？
中序遍歷算法是先遍歷左子樹，然后訪問根結點的，所以一開始傳入根結點A，我們不能訪問，此時將根結點A入棧，然后遍歷根結點A的左子樹。
此時以同樣的方式遍歷左子樹，遇到左子樹的根結點B，同樣不能訪問，將根結點B入棧，然后遍歷根結點B的左子樹。
我們接著遍歷結點B的左子樹，同樣將根結點D入棧。
此時結點D無左孩子，這樣就可以訪問根結點了，對棧進行出棧操作，因為棧的特性，此時出棧結點為D。
然后遍歷根結點D的右子樹，因為結點D無右孩子，此時需要退回到結點B，這時候結點B的左子樹已經遍歷完了，可以訪問根結點了，對棧進行出棧操作，出棧結點為B。
此時根結點A的左子樹也遍歷完了，又進行出棧操作，出棧結點為A。
以同樣的方式遍歷右子樹，遇到結點C，先入棧，然后訪問其左子樹，結點C無左孩子，所以結點C出棧，接著遍歷右子樹，以此類推。
遍歷結果為：D B A C E
算法實現(xiàn)
實現(xiàn)思想講解清楚了，接下來是算法實現(xiàn)，在實現(xiàn)這個算法之前我們還需要實現(xiàn)一個棧結構，這里采用順序棧。
#define TElemType char
int top=-1;//top變量時刻表示棧頂元素所在位置
//構造結點的結構體
typedef struct BiTNode{
TElemType data;//數(shù)據(jù)域
struct BiTNode *lchild,*rchild;//左右孩子指針
}BiTNode,*BiTree;
//前序和中序遍歷使用的進棧函數(shù)
void push(BiTNode** a,BiTNode* elem){
a[++top]=elem;
}
//彈棧函數(shù)
void pop( ){
if (top==-1) {
return ;
}
top--;
}
//模擬操作結點元素的函數(shù)，輸出結點本身的數(shù)值
void displayElem(BiTNode* elem){
printf("%c ",elem->data);
}
//拿到棧頂元素
BiTNode* getTop(BiTNode**a){
return a[top];
}
//中序遍歷非遞歸實現(xiàn)
void InOrderTraverse(BiTree Tree){
BiTNode* a[20];//定義一個順序棧
BiTNode * p;//臨時指針
p=Tree;
//當p為NULL并且棧為空時，表明樹遍歷完成
while (p != NULL || top!=-1) {
//如果p不為NULL，將其壓棧并遍歷其左子樹
if (p != NULL) {
push(a, p);
p=p->lchild;
}
//如果p==NULL，表明左子樹遍歷完成，需要遍歷上一層結點的右子樹
else{
p=getTop(a);
pop();
displayElem(p);
p=p->rchild;
}
}
}層次遍歷算法
層次遍歷算法是通過二叉樹的層次決定的，如下面的一棵二叉樹：
它的層次遍歷結果為：A B C D E，即從上到下，從左到右進行遍歷。 對于層次遍歷，我們可以使用隊列實現(xiàn)。 首先傳入根結點A，此時將根結點A入隊，然后就可以執(zhí)行出隊操作，出隊結點為A；
出隊之后判斷根結點A是否有左右孩子，如果有，則將結點B、C分別入隊，然后執(zhí)行出隊操作，由于隊列的特性，出隊結點為B；
結點B出隊之后判斷結點B是否有左右孩子，有左孩子，則入隊，然后執(zhí)行出隊操作，出隊結點為C；
繼續(xù)判斷結點C是否有左右孩子，結點C有右孩子E，將結點E入隊，然后執(zhí)行出隊操作，出隊結點為D；
判斷結點D是否有左右孩子，結點D無左右孩子，直接執(zhí)行出隊操作，出隊結點為E； 結點E也無左右孩子，而隊列也已經空了，此時遍歷完成。
該算法和剛才介紹的非遞歸遍歷算法有異曲同工之妙，這里就不具體寫出該算法了，大家可以嘗試著自己實現(xiàn)一下。
先序遍歷建立二叉樹算法
在學習遍歷算法的時候，還記得我們是如何建立二叉樹的嗎？
int main(){
//創(chuàng)建根結點
BiTree root = (BiTree) malloc(sizeof(BiNode));
root->data = 'A';
//創(chuàng)建根結點的左孩子
root->lchild = (BiTree) malloc(sizeof(BiNode));
root->lchild->data = 'B';
//創(chuàng)建根結點的右孩子
root->rchild = (BiTree) malloc(sizeof(BiNode));
root->rchild->data = 'C';
//創(chuàng)建根結點的左孩子的左孩子
root->lchild->lchild = (BiTree) malloc(sizeof(BiNode));
root->lchild->lchild->data = 'D';
//創(chuàng)建根結點的左孩子的右孩子
root->lchild->rchild = (BiTree) malloc(sizeof(BiNode));
root->lchild->rchild->data = 'E';
//根結點的右孩子無左右孩子
root->rchild->lchild = NULL;
root->rchild->rchild = NULL;
//根結點的左孩子的左孩子無左右孩子
root->lchild->lchild->lchild = NULL;
root->lchild->lchild->rchild = NULL;
//根結點的左孩子右孩子無左右孩子
root->lchild->rchild->lchild = NULL;
root->lchild->rchild->rchild = NULL;
return 0;
}可以看到，這個方法非常麻煩，但是建立算法又建立在遍歷算法之上，所以我們應該先掌握遍歷算法，再來學習建立算法。
先序遍歷建立算法即通過一個先序的遍歷序列建立出一棵二叉樹，比如下面的一個先序序列： A B C D E G F 需要注意的是，單憑這個先序序列并不能唯一確定一棵二叉樹。
比如這兩棵二叉樹的先序遍歷結果均為：A B C D E G F。 所以我們需要對這棵二叉樹進行補充，補充一些空結點，然后按照順序進行建立：
先序遍歷建立二叉樹算法實現(xiàn)如下：
BiTree CreateBiTreePre(){
BiTree root;
char ch;
printf("請輸入結點數(shù)據(jù)：\n");
scanf("%c",&ch);
getchar(); //接收一個回車
if(ch == '#'){
root = NULL;
}else{
//創(chuàng)建結點
root = (BiTree) malloc(sizeof(BiNode));
root->data = ch;
//遞歸建立左子樹
root->lchild = CreateBiTreePre();
//遞歸建立右子樹
root->rchild = CreateBiTreePre();
}
return root;
}測試一下：
int main(){
BiTree root;
//先序建立二叉樹
root = CreateBiTreePre();
printf("先序遍歷:");
PreOrderTraverse(root);
printf("\n");
printf("中序遍歷:");
InOrderTraverse(root);
printf("\n");
printf("后序遍歷:");
PostOrderTraverse(root);
return 0;
}運行程序，輸入：A B C # # D E # G # # F # # # 運行結果：
先序遍歷:A B C D E G F
中序遍歷:C B E G D F A
后序遍歷:C G E F D B A
遍歷二叉樹算法的應用
下面介紹一下遍歷二叉樹算法的應用。
復制二叉樹
通過遍歷一棵二叉樹，我們能夠將一棵二叉樹復制到另一棵二叉樹上。
BiTree CopyTree(BiTree t){
BiTree newT;
if(t == NULL){
return NULL;
}else{
//創(chuàng)建新結點
newT = (BiTree) malloc(sizeof(BiNode));
if(newT == NULL){
exit(-1);
}
//復制結點的數(shù)據(jù)域
newT->data = t->data;
//遞歸復制左子樹
newT->lchild=CopyTree(t->lchild);
//遞歸復制右子樹
newT->rchild=CopyTree(t->rchild);
return newT;
}
}中序和后序復制二叉樹的實現(xiàn)與其類似，不重復討論。
計算二叉樹的深度
遍歷二叉樹算法還可以用于計算二叉樹的深度，算法如下：
int Depth(BiTree t){
int m,n;
//判斷二叉樹是否為空
if(t == NULL){
return 0; //深度為0
}
//計算左子樹深度
m = Depth(t->lchild);
//計算右子樹深度
n = Depth(t->rchild);
//判斷左右子樹哪棵樹深度最大，最后記得加1(加的是根結點)
if(m > n){
return m + 1;
}else{
return n + 1;
}
}這些算法都比較簡單，就不一一分析了，看代碼注釋應該就能夠理解了。
計算二叉樹的結點總數(shù)
遍歷算法因為要訪問二叉樹中的每個結點，所以它還能夠用于計算結點總數(shù)，算法實現(xiàn)如下：
int GetNodeCount(BiTree t){
if(t == NULL){ //若當前結點為NULL，返回0
return 0;
}
//返回左子樹結點數(shù) + 右子樹結點數(shù) + 根結點
return GetNodeCount(t->lchild) + GetNodeCount(t->rchild) + 1;
}計算二叉樹的葉子結點數(shù)
計算葉子結點數(shù)的方式和剛才的算法類似，下面是代碼實現(xiàn)：
int GetLeafCount(BiTree t){
if(t == NULL){ //若當前結點為NULL，返回0
return 0;
}
if(t->lchild == NULL && t->rchild == NULL){
//若當前結點無左右孩子，則表明是葉子結點
return 1;
}
//返回左子樹葉子結點數(shù) + 右子樹葉子結點數(shù)
return GetLeafCount(t->lchild) + GetLeafCount(t->rchild);
}線索二叉樹的由來
先來看下面這棵二叉樹：
這是二叉樹存儲結構中的二叉鏈表，其優(yōu)點是能夠很方便地找到任意結點的左右孩子，然而，它也有缺點：一般情況下，無法直接找到某個結點在某種遍歷序列下的前驅結點和后繼結點。
為了能夠方便地找到任意結點的前驅和后繼結點，我們可以在結點中保存其前驅和后繼的結點地址，但如果為其增設兩個指針域顯然會犧牲很多空間，為此，我們可以利用二叉鏈表中的空指針域。
假設一棵具有n個結點的二叉樹，其一共有2n個指針域，而n個結點的二叉樹有n - 1個孩子結點，也就是說，該二叉樹一共使用了n - 1個指針域用來指向左右孩子，這樣就有n + 1個指針域是空著的，我們剛好可以利用這些指針域，用它們指向結點的前驅或者后繼結點。
如何利用二叉鏈表中的空指針域
對于一棵二叉樹的二叉鏈表結構，若某個結點的左孩子為空，則將空的左孩子指針域指向其前驅結點；同理，若某個結點的右孩子為空，則將空的友好孩子指針域指向其后繼結點。我們將這種改變指向的指針稱為"線索"，加上了線索的二叉樹稱為線索二叉樹。
看這樣的一個例子，比如下面的一棵二叉樹：
我們說二叉樹的線索化是相對于某個遍歷序列而言的，上面這棵二叉樹的中序遍歷結果為：C B E G D F A 則對于中序遍歷序列來說，該如何實現(xiàn)線索化呢？
先看結點A，其右孩子指針域為空，此時我們應該利用起來這個空指針域，讓其指向它的后繼結點，而從中序遍歷結果得知，結點A無后繼結點，所以我們最后還是讓結點A的右孩子指針域為空，不作處理。
再看結點C，其左右孩子指針域均為空，此時我們先處理左孩子指針域。從中序遍歷結果得知，結點C無前驅結點，但其后繼結點為B，所以我們不對左孩子指針域作處理，而讓右孩子指針域指向結點B。
繼續(xù)看結點E，其左孩子指針域為空，而其前驅結點為B，所以讓其左孩子指針域指向結點B。
處理結點F和結點G的方式也是一樣的，最后線索化完成的結果應為：
看到線索化后的二叉樹，很多同學可能懵了，這么多的指針指向，到底哪些是指向前驅和后繼結點的，哪些是指向孩子結點的呢？
為了區(qū)分，我們可以對二叉鏈表的結點結構增設兩個標志域ltag和rtag，并作出如下約定：
- ltag = 0，lchild指向該結點的左孩子
- ltag = 1，lchild指向該結點的前驅
- rtag = 0，rchild指向該結點的右孩子
- rtag = 1，rchild指向該結點的后繼
所以其結點結構應為：
typedef struct BiThrNode{
char data;
struct BiThrNode *lchild,*rchild;
int ltag,rtag; //標志域
}BiThrNode,*BiThrTree;看下面的一棵二叉樹：
對其進行先序線索化，先得出先序遍歷結果：A B C D E，其線索化結果為：
其中序線索化結果為(中序遍歷結果：B C A E D)：
后序線索化就留給大家自己畫一畫了。
到此這篇關于C語言實現(xiàn)二叉樹的示例詳解的文章就介紹到這了,更多相關C語言二叉樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
VSCode 使用 Code Runner 插件無法編譯運行文件名帶空格的文件問題
這篇文章主要介紹了VSCode 使用 Code Runner 插件無法編譯運行文件名帶空格的文件問題,本文通過圖文實例相結合給大家介紹的非常詳細，需要的朋友可以參考下2021-07-07
CRC（Cyclic Redundancy Check，循環(huán)冗余校驗）是一種常用的錯誤檢測技術，用于驗證數(shù)據(jù)在傳輸或存儲過程中是否發(fā)生了錯誤，本文主要介紹了C語言如何實現(xiàn)CRC校驗算法，需要的可以參考一下2023-08-08
本文主要介紹了Qt項目打包的實現(xiàn)步驟，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-05-05
這篇文章主要介紹了C++實現(xiàn)Linux下彈出U盤的方法,實例分析了C++在Linux平臺上進行IO操作的相關技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
這篇文章主要為大家詳細介紹了C語言版的三子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
在?C++?編程中,字符變量的取地址行為和內存布局對程序行為有著深遠的影響,尤其是在打印變量地址和訪問內存內容時,本文將給大家介紹C++?字符變量取地址的特殊性與內存管理機制,感興趣的朋友一起看看吧2024-12-12
C++ 隨機數(shù)字以及隨機數(shù)字加字母生成的案例
這篇文章主要介紹了C++ 隨機數(shù)字以及隨機數(shù)字加字母生成的案例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12
在應用程序開發(fā)時經常會遇到數(shù)據(jù)分頁的需求,每一頁展示特定數(shù)量的數(shù)據(jù),通過點擊按鈕翻頁或者輸入頁碼跳轉到指定頁,本文就來介紹一下Qt 自定義分頁控件的實現(xiàn),感興趣的可以了解一下2023-11-11
這篇文章主要介紹了C++實現(xiàn)LeetCode(72.編輯距離),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了基于Unity3D制作一做個經典小游戲Pacman，文中的示例代碼講解詳細，對我們學習Unity3D有一定的幫助，感興趣的小伙伴可以了解一下2021-12-12