程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 二叉樹建立、遍歷(前序,中序,後序),求葉節點個數,求節點個數

二叉樹建立、遍歷(前序,中序,後序),求葉節點個數,求節點個數

編輯:關於C

二叉樹是筆試面試中考試最頻繁的數據結構之一,主要包括,程序建立一個二叉樹,三種次序遍歷二叉樹,返回葉子節點的數目,求二叉樹節點的總數等。建立一個二叉樹節點的數據結構

typedef struct Node
{
int data;
struct Node *left,*right;
}Node;,結構體內包括數據,左子樹,又子樹;

一、建立二叉樹的程序代碼如下


[cpp]  Node *CreatBTree() //建立二叉樹  

    Node *t; 
    int x; 
    scanf("%d",&x); 
    if(x==0) 
    { 
        t=NULL; 
    } 
    else 
    { 
        t=(Node*)malloc(sizeof(Node)); 
        t->data=x; 
        printf("\n請輸入%d結點的左子結點:",t->data ); 
        t->left=CreatBTree(); 
        printf("\n請輸入%d結點的右子結點:",t->data ); 
        t->right=CreatBTree(); 
    } 
    return t; 

Node *CreatBTree() //建立二叉樹
{
 Node *t;
 int x;
 scanf("%d",&x);
 if(x==0)
 {
  t=NULL;
 }
 else
 {
  t=(Node*)malloc(sizeof(Node));
  t->data=x;
  printf("\n請輸入%d結點的左子結點:",t->data );
  t->left=CreatBTree();
  printf("\n請輸入%d結點的右子結點:",t->data );
  t->right=CreatBTree();
 }
 return t;
}

二、前序遍歷二叉樹


[cpp] void preVisit(Node *T) 

    if(T==NULL) return; 
    else 
    { 
        printf("%3d",T->data); 
        preVisit(T->left); 
        preVisit(T->right); 
    } 

void preVisit(Node *T)
{
 if(T==NULL) return;
 else
 {
  printf("%3d",T->data);
  preVisit(T->left);
  preVisit(T->right);
 }
}
三、中序遍歷二叉樹


[cpp] void middVisit(Node *T) 

    if(T==NULL) return; 
    else 
    { 
        middVisit(T->left); 
        printf("%3d",T->data); 
        middVisit(T->right); 
    } 

void middVisit(Node *T)
{
 if(T==NULL) return;
 else
 {
  middVisit(T->left);
  printf("%3d",T->data);
  middVisit(T->right);
 }
}
四、後序遍歷二叉樹


[cpp]  void lastVisit(Node *T) 

    if(T==NULL) return; 
    else 
    { 
        lastVisit(T->left); 
        lastVisit(T->right); 
        printf("%3d",T->data); 
    } 

void lastVisit(Node *T)
{
 if(T==NULL) return;
 else
 {
  lastVisit(T->left);
  lastVisit(T->right);
  printf("%3d",T->data);
 }
}
五、返回葉子節點數目


[cpp]  int leafnum(Node *T) 

    if (!T) 
    { 
        return 0; 
    } 
    else if ((!T->left)&&(!T->right)) 
    { 
        return 1; 
    } 
    else 
    { 
        return ((leafnum(T->left)+leafnum(T->right))); 
    } 

int leafnum(Node *T)
{
 if (!T)
 {
  return 0;
 }
 else if ((!T->left)&&(!T->right))
 {
  return 1;
 }
 else
 {
  return ((leafnum(T->left)+leafnum(T->right)));
 }
}
六、返回節點總數目


[cpp] view plaincopyprint?int Nodenum(Node *T) 

    if (T) 
    { 
        return 1+Nodenum(T->left)+Nodenum(T->right); 
    } 
    if (T==NULL) 
    { 
        return 0; 
    } 
 

int Nodenum(Node *T)
{
 if (T)
 {
  return 1+Nodenum(T->left)+Nodenum(T->right);
 }
 if (T==NULL)
 {
  return 0;
 }

}
七、測試程序;[cpp] int menu(); 
void main() 

    Node *T=NULL; 
    int choice; 
    do{ 
        choice=menu(); 
        if(choice==1) 
        { 
            printf("二叉樹的建立,以輸入“0”表示結束:!\n"); 
            printf("請輸入根結點:\n"); 
            T=CreatBTree(); 
            printf("二叉樹成功建立"); 
        } 
        else if(choice==2) 
        { 
            printf("先序遍歷二叉樹 :\n"); 
            preVisit(T); 
        } 
        else if(choice==3) 
        { 
            printf("中序遍歷二叉樹:\n"); 
            middVisit(T); 
        } 
        else if(choice==4) 
        { 
            printf("後序遍歷二叉樹 :\n "); 
            lastVisit(T); 
        } 
        else if(choice==5) 
        { 
            int ct=10; 
            ct=leafnum(T); 
            printf(" 二叉樹的葉子結點數為 : \n"); 
            printf("%d\n",ct); 
             
        } 
        else if(choice==7) 
        { 
            int count=Nodenum(T); 
            printf("該二叉樹總共有%d個結點。\n",count); 
        } 
        else if(choice==8) 
        exit(0); 
    }while(choice<=8); 

int menu();
void main()
{
 Node *T=NULL;
 int choice;
 do{
  choice=menu();
  if(choice==1)
  {
   printf("二叉樹的建立,以輸入“0”表示結束:!\n");
   printf("請輸入根結點:\n");
   T=CreatBTree();
   printf("二叉樹成功建立");
  }
  else if(choice==2)
  {
   printf("先序遍歷二叉樹 :\n");
   preVisit(T);
  }
  else if(choice==3)
  {
   printf("中序遍歷二叉樹:\n");
   middVisit(T);
  }
  else if(choice==4)
  {
   printf("後序遍歷二叉樹 :\n ");
   lastVisit(T);
  }
  else if(choice==5)
  {
   int ct=10;
   ct=leafnum(T);
   printf(" 二叉樹的葉子結點數為 : \n");
   printf("%d\n",ct);
   
  }
  else if(choice==7)
  {
   int count=Nodenum(T);
   printf("該二叉樹總共有%d個結點。\n",count);
  }
  else if(choice==8)
  exit(0);
 }while(choice<=8);
}
[cpp] int menu() 

        int choice; 
        printf("\n"); 
        printf(" 二叉樹 \n"); 
        printf(" ***************************\n"); 
        printf(" * *\n"); 
        printf(" * 主菜單 *\n"); 
        printf(" * 1 建立二叉樹 *\n"); 
        printf(" * 2 先序遍歷二叉樹 *\n"); 
        printf(" * 3 中序遍歷二叉樹 *\n"); 
        printf(" * 4 後序遍歷二叉樹 *\n"); 
        printf(" * 5 二叉樹的葉子結點數 *\n"); 
        printf(" * 7 二叉樹的所有結點數 *\n"); 
        printf(" * 8 退出程序運行 *\n"); 
        printf(" ****************************\n"); 
        printf(" 請輸入您的選擇(1,2,3,4,5,6,7,8): \n"); 
        scanf("%d",&choice); 
        return choice; 

int menu()
{
     int choice;
  printf("\n");
  printf(" 二叉樹 \n");
  printf(" ***************************\n");
  printf(" * *\n");
  printf(" * 主菜單 *\n");
  printf(" * 1 建立二叉樹 *\n");
  printf(" * 2 先序遍歷二叉樹 *\n");
  printf(" * 3 中序遍歷二叉樹 *\n");
  printf(" * 4 後序遍歷二叉樹 *\n");
  printf(" * 5 二叉樹的葉子結點數 *\n");
  printf(" * 7 二叉樹的所有結點數 *\n");
  printf(" * 8 退出程序運行 *\n");
  printf(" ****************************\n");
  printf(" 請輸入您的選擇(1,2,3,4,5,6,7,8): \n");
  scanf("%d",&choice);
  return choice;
}


 

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