程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C語言數據結構二叉樹簡單應用

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

編輯:關於C++

C語言數據結構二叉樹簡單應用。本站提示廣大學習愛好者:(C語言數據結構二叉樹簡單應用)文章只能為提供參考,不一定能成為您想要的結果。以下是C語言數據結構二叉樹簡單應用正文


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

投稿:lqh

這篇文章主要介紹了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("葉子結點個數為:%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; 
} 

感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved