二元樹的建立與遍歷

暑假期間，自己在複習數據結構，嗯嗯嗯，加油。

前程似錦，未來可期

這裏給一個樣例樹：

程式碼：

#include <stdio.h> 
#include <string.h>
#include <stdlib.h>

/*    二元樹的二叉鏈表結點結構定義     */

typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

BiTree T=NULL;

/*    先序遍歷建立一個二元樹    */

void Create (BiTree *T)       //    二級指針改變地址的地址
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else
    {
        *T=(BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            return ;
        else
        {
            (*T)->data=ch;
            Create(&(*T)->lchild);
            Create(&(*T)->rchild);
        }
    }
}

/*    二元樹的前序遞回遍歷演算法    */
void PreOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    printf("%c ",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}
/*    二元樹的中序遞回遍歷演算法    */
void InOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    InOrderTraverse(T->lchild);
    printf("%c ",T->data);
    InOrderTraverse(T->rchild);
}
/*    二元樹的後序遞回遍歷演算法    */
void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ",T->data);
}
int main()
{
    printf("請按先序遍歷的結果輸入樹，例如：ABDH#K###E##CFI###G#J##\n");
    Create(&T);
    printf("先序遍歷的結果爲：\n");
    PreOrderTraverse(T);
    printf("\n");
    printf("中序遍歷的結果爲：\n");
    InOrderTraverse(T);
    printf("\n");
    printf("後序遍歷的結果爲：\n");
    PostOrderTraverse(T);
    printf("\n");
    return 0;
}

輸出結果如下

PS：下面 下麪是一個用C++裏面的取參照代替了二級指針

#include<bits/stdc++.h>
using namespace std;

/*    二元樹的二叉鏈表結點結構定義     */

typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

BiTree T=NULL;

/*    先序遍歷建立一個二元樹    */

void Create (BiTree &T)        //    C++取參照
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        T=NULL;
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        if(!T)
            return ;
        else
        {
            T->data=ch;
            Create(T->lchild);
            Create(T->rchild);
        }
    }
}

/*    二元樹的前序遞回遍歷演算法    */
void PreOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    printf("%c ",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}
/*    二元樹的中序遞回遍歷演算法    */
void InOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    InOrderTraverse(T->lchild);
    printf("%c ",T->data);
    InOrderTraverse(T->rchild);
}
/*    二元樹的後序遞回遍歷演算法    */
void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ",T->data);
}
int main()
{
    printf("請按先序遍歷的結果輸入樹，例如：ABDH#K###E##CFI###G#J##\n");
    Create(T);
    printf("先序遍歷的結果爲：\n");
    PreOrderTraverse(T);
    printf("\n");
    printf("中序遍歷的結果爲：\n");
    InOrderTraverse(T);
    printf("\n");
    printf("後序遍歷的結果爲：\n");
    PostOrderTraverse(T);
    printf("\n");
    return 0;
}