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空格空格，即可驗證本文提供的遍歷算法。