[2022/4/13]树示例程序

包含树的基本功能：创建、显示、先序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD)、层次遍历、求叶子节点数、求所有节点数、求树的深度

效果图

简单的示例程序，代码主要源自教材，但本人对部分函数进行了优化

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

#define MAX 100
typedef char DataType;

typedef struct tnode{
    DataType data;
    struct tnode *rc;//右孩子 
    struct tnode *lc;//左孩子 
}BT;

//先序遍历 
void DLR(BT *T)
{
    if(T != NULL)
    {
        printf("%c",T->data);
        DLR(T->lc);//遍历左子树 
        DLR(T->rc);
    }
}

//中序遍历 
void LDR(BT *T)
{
    if(T != NULL)
    {
        LDR(T->lc);
        printf("%c",T->data);
        LDR(T->rc);
    }
}

//后序遍历 
void LRD(BT *T)
{
    if(T != NULL)
    {
        LRD(T->lc);
        LRD(T->rc);
        printf("%c",T->data);
    }
}

//层次遍历 
void LevelOrder(BT *T)
{
    int f,r;        //定义队头队尾指针 
    BT *p,*q[MAX];    //定义循环队列，存放节点指针 
    p=T;
    if(p!=NULL)        //若二叉树非空，则根节点地址入队 
    {
        f = 1;
        q[f] = p;
        r = 2;
    }
    while(f!=r)
    {
        p=q[f];
        printf("%c",p->data);
        if(p->lc != NULL)//队首节点的左孩子入队 
        {
            q[r] = p->lc;
            r = (r+1)%MAX;
        }
        if(p->rc != NULL)//队首节点的有孩子入队 
        {
            q[r] = p->rc;
            r = (r+1)%MAX;
        }
        f = (f+1)%MAX;
    }
}


//建立二叉树
BT *CreateBTree()
{
    BT* t;
    char ch;
    printf("请输入根节点\n"); 
    scanf("%c",&ch);
    getchar();
    if(ch == '0')
    {
        t = NULL;
    }
    else
    {
        t = (BT*)malloc(sizeof(BT));
        t->data = ch;
        printf("请输入%c节点的左孩子节点(输入0取消输入)\n",t->data);
        t->lc = CreateBTree();
        printf("请输入%c节点的右孩子节点(输入0取消输入)\n",t->data);
        t->rc = CreateBTree();
    }
    return t;
} 

//展示树 
void ShowBTree(BT *T)
{
    if(T != NULL)
    {
        printf("%c",T->data);
        if(T->lc != NULL)
        {
            printf("(");
            ShowBTree(T->lc);
            if(T->rc != NULL)
            {
                printf(",");
                ShowBTree(T->rc);
            }
            printf(")");
        }
        else if(T->rc != NULL)
        {
            printf("(");
            ShowBTree(T->lc);
            if(T->rc != NULL)
            {
                printf(",");
                ShowBTree(T->rc);
            }
            printf(")");
        }
    }
}

//返回叶子节点数量 
int leaf_num(BT *T)
{
    if (T == NULL)
        return 0;
    if (T->lc == NULL && T->rc == NULL)
        return 1;

    return (leaf_num(T->lc) + leaf_num(T->rc));
}

//求总结点数 
int node_num(BT *T)
{
    int tmp1 = 0, tmp2 = 0;
    if(T == NULL)
        return 0;
    tmp1 = node_num(T->lc);
    tmp2 = node_num(T->rc);
    return 1+tmp1+tmp2;
}

//求树的深度 
int TreeDepth(BT *T)
{
    int ldepth = 0;//左深度 
    int rdepth = 0;//右深度 
    if(T == NULL)
    {
        return 0;
    }
    else
    {
        ldepth = TreeDepth(T->lc);
        rdepth = TreeDepth(T->rc);
        if(ldepth > rdepth)
            return ldepth+1;
        else
            return rdepth+1;
    }
}

//菜单 
void menu()
{
    char word[][30]={{"1.建立二叉树\n"},{"2.输出二叉树\n"},{"3.先序遍历\n"},{"4.中序遍历\n"},{"5.后序遍历\n"},{"6.层次遍历\n"},
                    {"7.输出叶子节点数量\n"},{"8.输出二叉树总节点数\n"},{"9.输出树的深度\n"},{"0.退出\n"}};
    for(int i = 0;i<10;i++)
    {
        printf("%s",word[i]);
    }
}


int main()
{
    //menu();
    BT* tree = NULL;
    char ch = '0';
    while(1)
    {
        system("cls");
        menu();
        scanf("%c",&ch);
        getchar();
        
        switch(ch)
        {
            case '1':
                tree = CreateBTree();
                printf("建立树成功！\n");
                break;
            case '2':
                ShowBTree(tree);
                printf("\n");
                break;
            case '3':
                DLR(tree);
                break;
            case '4':
                LDR(tree);
                break;
            case '5':
                LRD(tree);
                break;
            case '6':
                LevelOrder(tree);
                break;
            case '7':
                printf("\n");
                printf("叶子节点的数量是%d\n",leaf_num(tree));
                break;
            case '8':
                printf("树的总节点数为%d\n",node_num(tree));
                break;
            case '9':
                printf("树的深度为%d\n",TreeDepth(tree));
                break;
            case '0':
                return 0;
                 
        }
        system("pause");
    }
}

源代码下载
tree.c

作者：WWQ