二叉树 基本操作

admin

/*二叉树
基本操作：
创建，
凹入法输出，
求叶子结点数，
求结点数，
求深度，
根据给定值进行查找*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>
typedef struct Tnode
{
        int data;
        struct Tnode* lchild;
        struct Tnode* rchild;
}Tnode,*BiTree;
void creat(BiTree *T);
void disTree(BiTree T,int n,char c);
int leafnum(BiTree T);
int nodenum(BiTree T);
int depth(BiTree T);
BiTree search(BiTree T, int e);
void dis(BiTree T, int n, char c);
int main()
{
        BiTree T, p; int e;
        printf("输入节点值，以0结束:\n");
        creat(&T); printf("创建成功！\n");
        printf("凹入表如下;\n");
        disTree(T, 8, 'D');
        dis(T, 10, 'D');
        printf("叶子结点数：%d\n", leafnum(T));
        printf("结点数：%d\n", nodenum(T));
        printf("深度：%d\n", depth(T));
        printf("请输入查询结点的值：");
        scanf_s("%d", &e);
        p = search(T, e);
        if (p==NULL)printf("该节点不存在！\n");
        if (p->rchild == NULL && p->lchild == NULL) printf("该节点为叶子结点！\n");
        if (!p->lchild && p->rchild) printf("该节点的左孩子不存在，右孩子为%d！\n", p->rchild->data);
        if (!p->rchild && p->lchild) printf("该节点的左孩子是%d,右孩子为空！\n", p->lchild->data);
        else
                printf("该节点的左孩子是%d,右孩子是%d\n", p->lchild->data, p->rchild->data);
}
void creat(BiTree *T)
{
        int n;
        scanf_s("%d", &n);
        if (n == 0) *T = NULL;
        else
        {
            *T=(BiTree)malloc(sizeof(Tnode));
                (*T)->data = n;
                creat(&((*T)->rchild));
                creat(&((*T)->lchild));
        }
}
void disTree(BiTree T,int n,char c)
{
        int i;
        if (T)
        {
                for (i = 0; i < n+4; i++)
                        putchar('-');
                putchar('+');
                printf("%d(%c)\n", T->data, c);
                n = n - 1;
                disTree(T->lchild, n, 'L');
                disTree(T->rchild, n, 'R');
        }
}
void dis(BiTree T, int n, char c)
{
        int i;
        if (T)
        {
                for (i = 0; i < n; i++)
                {
                        putchar('-');
                }
                putchar('+');
                printf("%d(%c)\n", T->data, c);

                dis(T->lchild, n-2, 'L');
                dis(T->rchild, n - 2, 'R');
        }
}
int leafnum(BiTree T)
{
        int l, r;
        if (!T) return 0;
        if (!T->lchild && !T->rchild) return 1;
        else
        {
                l = leafnum(T->lchild);
                r = leafnum(T->rchild);
                return(l + r);
        }
}
int nodenum(BiTree T)
{
        int l, r;
        if (!T) return 0;
        if (!T->lchild && !T->rchild) return 1;
        else
        {
                l = nodenum(T->lchild);
                r = nodenum(T->rchild);
                return(l + r+1);

        }
}
int depth(BiTree T)
{
        int l, r,d;
        if (!T) return 0;
        if (!T->lchild && !T->rchild) return 1;
        else
        {
                l = depth(T->lchild);
                r = depth(T->rchild);
                d = l > r ? l : r;
                return (d+1);
        }
}
BiTree search(BiTree T, int e)
{
        if (!T) return NULL;
        else
        {
                if (T->data == e) return T;
                else
                {
                        search(T->lchild, e);
                        search(T->rchild, e);
                }
        }
}