C語言數據結構二叉樹簡單應用

在計算機科學中，二叉樹是每個節點最多有兩個子樹的樹結構。本文是本站小編搜索整理的關於C語言數據結構二叉樹簡單應用的相關資料，供參考學習，希望對大家有所幫助!想了解更多相關信息請持續關注我們應屆畢業生考試網!

通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree），接下來我就在這裏給大家介紹一下二叉樹在算法中的簡單使用：

　　我們要完成總共有

（1）二叉樹的創建

（2）二叉樹的先中後序遞歸遍歷

（3）統計葉子結點的總數

（4）求樹的高度

（5）反轉二叉樹

（6）輸出每個葉子結點到根節點的.路徑

（7）輸出根結點到每個葉子結點的路徑。

　　定義二叉樹結點類型的結構體

typedef struct node{

char data;

struct node *Lchild;

struct node *Rchild;

}BiTNode,*BiTree;

int cnt=0;//統計葉子節點個數

二叉樹的創建

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);

}

}

　　統計葉子結點個數：

void LeafCountNode(BiTree root){ //統計葉子結點個數

if(root){

if(!root->Lchild && !root->Rchild)

cnt++;

LeafCountNode(root->Lchild);

LeafCountNode(root->Rchild);

}

}

輸出各個葉子結點值：

void IInOrder(BiTree root){ //輸出各個葉子結點值

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;

}

}

反轉二叉樹：

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);

}

}

輸出每個葉子結點到根節點的路徑：

void OutPutPath(BiTree root,char path[],int len){ //輸出每個葉子結點到根節點的路徑

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);

}

}

輸出根到每個葉子結點的路徑：

void PrintPath(BiTree root,char path[],int l){ //輸出根到每個葉子結點的路徑

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("葉子結點個數為:%dn",cnt);

// IInOrder(root);

h=PostTreeDepth(root);

printf("樹的高度為:High=%dn",h);

// PrintTree(root,0);

// MirrorTree(root);

// PrintTree(root,0);

// OutPutPath(root,path,0);

// PrintPath(root,path,10);

return 0;

}