二叉树的建立与遍历(递推)

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(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码,是要算字符的,但是输入 完之后可以按回车退出),这时候就能够看到结果了。

0

Leave a Reply

Your email address will not be published.