二叉树的建立与遍历（递推）

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉树的建立需要用到结构体:

typedef struct BiTNode
{
    char data;
    struct BiTNode *leftChild,*rightChild;
}BiTNode,*BiTree;

这里我用递推进行建立二叉树：

BiTree Create(BiTree T)
{
    char ch;
    ch=getchar();
    if(ch=='#')
    T=NULL;
    else
    {

        if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
        printf("Error!");
        T->data=ch;
        T->leftChild=Create(T->leftChild);
        T->rightChild=Create(T->rightChild);
    }
    return T;
}

二叉树的遍历有三种方式：

DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。

先根次序遍历：

void Preorder(BiTree T)
{
    if(T)
    {
        printf("%c",T->data);
        Preorder(T->leftChild);
        Preorder(T->rightChild);
    }
}

中根次序遍历：

void zhongxu(BiTree T)
{
    if(T)
    {
        zhongxu(T->leftChild);
        printf("%c",T->data);
        zhongxu(T->rightChild);
    }
}

后根次序遍历：

void houxu(BiTree T)
{
    if(T)
    {
        houxu(T->leftChild);
        houxu(T->rightChild);
        printf("%c",T->data);
    }
}

然后树的深度：

int Depth(BiTree T)
{
    int dep=0,depl,depr;
    if(!T) dep=0;
    else
    {
        depl=Depth(T->leftChild);
        depr=Depth(T->rightChild);
        dep=1+(depl>depr?depl:depr);
    }
    return dep;
}

还有树的节点：

int Sumleaf(BiTree T)
{
    int sum=0,m,n;
    if(T)
    {
        if((!T->leftChild)&&(!T->rightChild))
        sum++;
        m=Sumleaf(T->leftChild);
        sum+=m;
        n=Sumleaf(T->rightChild);
        sum+=n;
    }
    return sum;
}

完整代码：

#include "stdio.h"
#include "string.h"
#include "malloc.h"
#define NULL 0

typedef struct BiTNode
{
    char data;
    struct BiTNode *leftChild,*rightChild;
}BiTNode,*BiTree;

BiTree Create(BiTree T)
{
    char ch;
    ch=getchar();
    if(ch=='#')
    T=NULL;
    else
    {

        if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
        printf("Error!");
        T->data=ch;
        T->leftChild=Create(T->leftChild);
        T->rightChild=Create(T->rightChild);
    }
    return T;
}

void Preorder(BiTree T)
{
    if(T)
    {
        printf("%c",T->data);
        Preorder(T->leftChild);
        Preorder(T->rightChild);
    }
}

int Sumleaf(BiTree T)
{
    int sum=0,m,n;
    if(T)
    {
        if((!T->leftChild)&&(!T->rightChild))
        sum++;
        m=Sumleaf(T->leftChild);
        sum+=m;
        n=Sumleaf(T->rightChild);
        sum+=n;
    }
    return sum;
}

void zhongxu(BiTree T)
{
    if(T)
    {
        zhongxu(T->leftChild);
        printf("%c",T->data);
        zhongxu(T->rightChild);
    }
}


void houxu(BiTree T)
{
    if(T)
    {
        houxu(T->leftChild);
        houxu(T->rightChild);
        printf("%c",T->data);
    }
}

int Depth(BiTree T)
{
    int dep=0,depl,depr;
    if(!T) dep=0;
    else
    {
        depl=Depth(T->leftChild);
        depr=Depth(T->rightChild);
        dep=1+(depl>depr?depl:depr);
    }
    return dep;
}

int main()
{
    BiTree T;
    int sum,dep;
    T=Create(T);
    Preorder(T);
    printf("\n\n");
    zhongxu(T);
    printf("\n\n");
    houxu(T);
    printf("\n\n");
    sum=Sumleaf(T);
    printf("sum=%d",sum);
    dep=Depth(T);
    printf("\ndep=%d\n",dep);
    return 0;
}

例如输入序列ABC##DE#G##F###（其中的“#”表示空，并且输入过程中不要加回车，因为回车也有对应的ASCII码，是要算字符的，但是输入 完之后可以按回车退出），这时候就能够看到结果了。