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; }
感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!