二叉樹

二叉樹結(jié)構(gòu)的定義

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

二叉樹的建立

按照前序擴(kuò)展二叉樹輸入

void CreatBiTree(BiTree* T) 
{
    TElemType ch;
    scanf("%c",&ch);
    if(ch == '#')
    {
        *T = NULL;  //如果輸入為#就將結(jié)點(diǎn)的地址設(shè)為NULL 
    }
    else
    {
        *T = (BiTree) malloc(sizeof(BiTNode));
        if(!T)
        {
            exit(OVERFLOW);
        }
        (*T)->data = ch;
        CreatBiTree(&(*T)->lchild);
        CreatBiTree(&(*T)->rchild);
    }
}

在敲這段代碼的時候，我一直有一個疑惑，就是問什么它這個地方要傳入雙重指針，所以我寫的時候就把他改成使用指針變量，而不是雙重指針，寫好之后，在輸出的時候出現(xiàn)了錯誤，發(fā)現(xiàn)值并沒有傳入到二叉樹當(dāng)中，之后又改成原來的版本，使用雙重指針，錯誤就好了，這應(yīng)該是形參和實(shí)參的問題，有點(diǎn)迷糊，還是要多看書……

還有一個問題就是在你創(chuàng)建的輸入的時候不能一個一個的字符輸入，而是只能一次性全部輸完，他才會跳出循環(huán)，現(xiàn)在還不知道原因……

二叉樹的遍歷（遞歸實(shí)現(xiàn)）

前序遍歷

void PreOrderTraverse(BiTree T)
{
    if(!T)
    {
        return;
    }
    printf("%c",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

中序遍歷

void InOrderTraverse(BiTree T)
{
    if(!T)
    {
        return;
    }
    InOrderTraverse(T->lchild);
    printf("%c",T->data);
    InOrderTraverse(T->rchild);
}

后序遍歷

void PostOrderTraverse(BiTree T)
{
    if(!T)
    {
        return;
    }
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c",T->data);
}

實(shí)驗(yàn)結(jié)果

完整的代碼

/*二叉樹*/

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

#define OVERFLOW 0
typedef char TElemType;

//定義樹的結(jié)點(diǎn)的結(jié)構(gòu),BiTree結(jié)點(diǎn)的指針變量 
typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void CreatBiTree(BiTree* T) 
{
    TElemType ch;
    scanf("%c",&ch);
    if(ch == '#')
    {
        *T = NULL;  //如果輸入為#就將結(jié)點(diǎn)的地址設(shè)為NULL 
    }
    else
    {
        *T = (BiTree) malloc(sizeof(BiTNode));
        if(!T)
        {
            exit(OVERFLOW);
        }
        (*T)->data = ch;
        CreatBiTree(&(*T)->lchild);
        CreatBiTree(&(*T)->rchild);
    }
}

//前序遍歷的遞歸實(shí)現(xiàn) 
void PreOrderTraverse(BiTree T)
{
    if(!T)
    {
        return;
    }
    printf("%c",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

//中序遍歷的遞歸實(shí)現(xiàn) 
void InOrderTraverse(BiTree T)
{
    if(!T)
    {
        return;
    }
    InOrderTraverse(T->lchild);
    printf("%c",T->data);
    InOrderTraverse(T->rchild);
}

//后續(xù)遍歷的遞歸實(shí)現(xiàn) 
void PostOrderTraverse(BiTree T)
{
    if(!T)
    {
        return;
    }
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c",T->data);
}

int main()
{
    printf("請按照前序擴(kuò)展二叉樹進(jìn)行輸入："); 
    BiTree t;
    CreatBiTree(&t);
    printf("二叉樹建立成功！??！\n");
    printf("前序遍歷："); 
    PreOrderTraverse(t);
    printf("\n");
    printf("中序遍歷："); 
    InOrderTraverse(t);
    printf("\n");
    printf("后序遍歷："); 
    PostOrderTraverse(t);
    printf("\n");
    
    return 0;
}