二叉树

二叉树结构的定义

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

二叉树的建立

按照前序扩展二叉树输入

void CreatBiTree(BiTree* T) 
{
    TElemType ch;
    scanf("%c",&ch);
    if(ch == '#')
    {
        *T = NULL;  //如果输入为#就将结点的地址设为NULL 
    }
    else
    {
        *T = (BiTree) malloc(sizeof(BiTNode));
        if(!T)
        {
            exit(OVERFLOW);
        }
        (*T)->data = ch;
        CreatBiTree(&(*T)->lchild);
        CreatBiTree(&(*T)->rchild);
    }
}

在敲这段代码的时候，我一直有一个疑惑，就是问什么它这个地方要传入双重指针，所以我写的时候就把他改成使用指针变量，而不是双重指针，写好之后，在输出的时候出现了错误，发现值并没有传入到二叉树当中，之后又改成原来的版本，使用双重指针，错误就好了，这应该是形参和实参的问题，有点迷糊，还是要多看书……

还有一个问题就是在你创建的输入的时候不能一个一个的字符输入，而是只能一次性全部输完，他才会跳出循环，现在还不知道原因……

二叉树的遍历（递归实现）

前序遍历

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);
}

实验结果

完整的代码

/*二叉树*/

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

#define OVERFLOW 0
typedef char TElemType;

//定义树的结点的结构,BiTree结点的指针变量 
typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void CreatBiTree(BiTree* T) 
{
    TElemType ch;
    scanf("%c",&ch);
    if(ch == '#')
    {
        *T = NULL;  //如果输入为#就将结点的地址设为NULL 
    }
    else
    {
        *T = (BiTree) malloc(sizeof(BiTNode));
        if(!T)
        {
            exit(OVERFLOW);
        }
        (*T)->data = ch;
        CreatBiTree(&(*T)->lchild);
        CreatBiTree(&(*T)->rchild);
    }
}

//前序遍历的递归实现 
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);
}

int main()
{
    printf("请按照前序扩展二叉树进行输入："); 
    BiTree t;
    CreatBiTree(&t);
    printf("二叉树建立成功！！！\n");
    printf("前序遍历："); 
    PreOrderTraverse(t);
    printf("\n");
    printf("中序遍历："); 
    InOrderTraverse(t);
    printf("\n");
    printf("后序遍历："); 
    PostOrderTraverse(t);
    printf("\n");
    
    return 0;
}