程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言入門知識 >> C語言遞歸實現二叉樹的先序、中序、後序遍歷

C語言遞歸實現二叉樹的先序、中序、後序遍歷

編輯:C語言入門知識
#include   
#include   
//*****二叉樹的二叉鏈表存儲表示*****//  
typedef struct BiNode  
{  
    char data;  
    struct BiNode *lchild, *rchild;  
}BiNode, *BiTree;  

//*****按先序次序輸入二叉樹中結點的值(一個字符),空格字符表示空樹構造二叉鏈表表示的二叉樹T*****//   
void CreateBiTree(BiTree &T)          
{                                     
    char ch;  
    scanf("%c", &ch);  
    if(ch == ' ')  
    {  
        T = NULL;  
    }  
    else  
    {  
        if(!(T = (BiNode *)malloc(sizeof(BiNode))))   
        {  
            return;  
        }  
        T->data = ch;                    //生成根結點  
        CreateBiTree(T->lchild);     //構造左子樹  
        CreateBiTree(T->rchild);     //構造右子樹  
    }  
	
    return;  
}  

//*****先序遍歷二叉樹*****//   
void PreOrderTraverse(BiTree T)  
{  
    if(!T)   
    {  
        return;                             //若T為空樹,則直接返回  
    }  
    printf("%c ", T->data);                  //訪問根結點  
    PreOrderTraverse(T->lchild);         //先序遍歷左子樹  
    PreOrderTraverse(T->rchild);         //先序遍歷右子樹  
	
    return;  
}  

//*****中序遍歷二叉樹*****//   
void InOrderTraverse(BiTree T)  
{  
    if(!T)  
    {  
        return;                             //若T為空樹,則直接返回  
    }  
    InOrderTraverse(T->lchild);              //中序遍歷左子樹  
    printf("%c ", T->data);                  //訪問根結點  
    InOrderTraverse(T->rchild);              //中序遍歷右子樹  
	
    return;  
}  

//*****後序遍歷二叉樹*****//   
void PostOrderTraverse(BiTree T)  
{  
    if(!T)  
    {  
        return;                             //若T為空樹,則直接返回  
    }  
    PostOrderTraverse(T->lchild);            //後序遍歷左子樹  
    PostOrderTraverse(T->rchild);            //後序遍歷右子樹  
    printf("%c ", T->data);                  //訪問根結點  
	
    return;  
}  

int main(void)  
{  
    BiTree T;      
    printf("請按先序次序輸入二叉樹中結點的值(字符),空格字符表示空樹:\n");  
    CreateBiTree(T);      
	
    printf("先序遍歷結果為:");  
    PreOrderTraverse(T);  
    printf("\n\n");   
	
    printf("中序遍歷結果為:");  
    InOrderTraverse(T);  
    printf("\n\n");   
	
    printf("後序遍歷結果為:");  
    PostOrderTraverse(T);      
    printf("\n\n");      
	
    return 0;      
}    

以如下二叉樹為例,給出按先序次序輸入二叉樹中結點的值(字符),從而按照本文給出的算法構造二叉樹。


輸入字符的順序是:-+a空格空格*b空格空格-c空格空格d空格空格/e空格空格f空格空格,即可驗證本文提供的遍歷算法。

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