- 相關(guān)推薦
C語言數(shù)據(jù)結(jié)構(gòu)二叉樹簡單應(yīng)用
在計算機科學中，二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)。本文是百分網(wǎng)小編搜索整理的關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)二叉樹簡單應(yīng)用的相關(guān)資料，供參考學習，希望對大家有所幫助!想了解更多相關(guān)信息請持續(xù)關(guān)注我們應(yīng)屆畢業(yè)生考試網(wǎng)!
通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree），接下來我就在這里給大家介紹一下二叉樹在算法中的簡單使用：
我們要完成總共有
�。�1）二叉樹的創(chuàng)建
�。�2）二叉樹的先中后序遞歸遍歷
�。�3）統(tǒng)計葉子結(jié)點的總數(shù)
�。�4）求樹的高度
（5）反轉(zhuǎn)二叉樹
�。�6）輸出每個葉子結(jié)點到根節(jié)點的路徑
（7）輸出根結(jié)點到每個葉子結(jié)點的路徑。
定義二叉樹結(jié)點類型的結(jié)構(gòu)體
typedef struct node{
char data;
struct node *Lchild;
struct node *Rchild;
}BiTNode,*BiTree;
int cnt=0;//統(tǒng)計葉子節(jié)點個數(shù)
二叉樹的創(chuàng)建
BiTNode *Create(){ //二叉樹的先序建立
char ch;
BiTNode *s;
ch=getchar();
if(ch=='#')erchashu
return NULL;
s=(BiTNode *)malloc(sizeof(BiTNode));
s->data=ch;
s->Lchild=Create();
s->Rchild=Create();
return s;
}
二叉樹的先序、中序、后序遞歸遍歷
void PreOrder(BiTree root){ //前序遍歷
if(root){
printf("%c ",root->data);
PreOrder(root->Lchild);
PreOrder(root->Rchild);
}
}
void InOrder(BiTree root){ //中序遍歷
if(root){
InOrder(root->Lchild);
printf("%c ",root->data);
InOrder(root->Rchild);
}
}
void PostOrder(BiTree root){ //后序遍歷
if(root){
PostOrder(root->Lchild);
PostOrder(root->Rchild);
printf("%c ",root->data);
}
}
統(tǒng)計葉子結(jié)點個數(shù)：
void LeafCountNode(BiTree root){ //統(tǒng)計葉子結(jié)點個數(shù)
if(root){
if(!root->Lchild && !root->Rchild)
cnt++;
LeafCountNode(root->Lchild);
LeafCountNode(root->Rchild);
}
}
輸出各個葉子結(jié)點值：
void IInOrder(BiTree root){ //輸出各個葉子結(jié)點值
if(root){
IInOrder(root->Lchild);
if(!root->Lchild && !root->Rchild)
printf("%c ",root->data);
IInOrder(root->Rchild);
}
}
求樹的高度：
int PostTreeDepth(BiTree root){ //求樹的高度
int h1,h2,h;
if(root==NULL){
return 0;
}
else{
h1=PostTreeDepth(root->Lchild);
h2=PostTreeDepth(root->Rchild);
h=(h1>h2?h1:h2)+1;
return h;
}
}
反轉(zhuǎn)二叉樹：
void MirrorTree(BiTree root){ //二叉樹鏡像樹
BiTree t;
if(root==NULL)
return;
else{
t=root->Lchild;
root->Lchild=root->Rchild;
root->Rchild=t;
MirrorTree(root->Lchild);
MirrorTree(root->Rchild);
}
}
輸出每個葉子結(jié)點到根節(jié)點的路徑：
void OutPutPath(BiTree root,char path[],int len){ //輸出每個葉子結(jié)點到根節(jié)點的路徑
if(root){
if(!root->Lchild && !root->Rchild){
printf("%c ",root->data);
for(int i=len-1;i>=0;i--)
printf("%c ",path[i]);
printf("\n");
}
path[len]=root->data;
OutPutPath(root->Lchild,path,len+1);
OutPutPath(root->Rchild,path,len+1);
}
}
輸出根到每個葉子結(jié)點的路徑：
void PrintPath(BiTree root,char path[],int l){ //輸出根到每個葉子結(jié)點的路徑
int len=l-1;
if(root){
if(root->Lchild==NULL && root->Rchild==NULL){
path[len]=root->data;
for(int i=9;i>=len;i--)
printf("%c ",path[i]);
printf("\n");
}
path[len]=root->data;
PrintPath(root->Lchild,path,len);
PrintPath(root->Rchild,path,len);
}
}
測試代碼：
int main(void){
int h,len;
char path[20];
BiTree root;
root=Create();
// PreOrder(root);
// printf("\n");
// InOrder(root);
// printf("\n");
// PostOrder(root);
// printf("\n");
// LeafCountNode(root);
// printf("葉子結(jié)點個數(shù)為:%d\n",cnt);
// IInOrder(root);
h=PostTreeDepth(root);
printf("樹的高度為:High=%d\n",h);
// PrintTree(root,0);
// MirrorTree(root);
// PrintTree(root,0);
// OutPutPath(root,path,0);
// PrintPath(root,path,10);
return 0;
}
【C語言數(shù)據(jù)結(jié)構(gòu)二叉樹簡單應(yīng)用】相關(guān)文章：
C語言的應(yīng)用05-29
C語言的主要應(yīng)用07-29
C語言的應(yīng)用知識08-30
C語言知識點及其簡單應(yīng)用05-27
C語言的reduce方法應(yīng)用10-22
C語言應(yīng)用領(lǐng)域09-23
C語言的應(yīng)用有哪些08-05
C語言的應(yīng)用領(lǐng)域08-20