二叉数运算.c

无递归二叉树插入及中序等顺带求得深度等

/*
  Author:   ViperDodge[DFCG]
  Date: 29-05-04 16:49
  Description:     树的运算
*/

#include <stdio.h>
#include <windef.h>               //包含max()函数
struct node                       //树的结构
{
    int data;
    struct node *lchild,*rchild;
};
typedef struct node *bitree;

void create(bitree *head)          //建数过程
{
  void insert(bitree *head,int x)     //包含插入运算在建数函数内
  {
    struct node *f, *p = *head;
    while (p)
    {
        if (p->data == x )return;    //数据相等则返回
        else
            {                       //否则找到数据应该在左还是在右
                f = p;
                p = (p->data > x) ? p->lchild : p->rchild;
            }
    }
    p = (struct node*) malloc (sizeof(struct node));   //申请空间
    p->data = x;
    p->lchild = p->rchild = 0;        //构成一棵单独的树
    if (*head == 0)     *head = p;    //树空的情况
    else
        {                             //链接成树
            if (f->data > x)    f->lchild = p;
            else                f->rchild = p;
        }
  }
    int key;
    printf("请输入数，输入0则结束输入:\n");
    scanf("%d",&key);
    while(key)                    //不等于0的情况就不断插入
    {
        insert(head,key);
        scanf("%d",&key);
    }
}

int zuo=1,you=1,yezi=0;;         //全局变量，用于求深度及叶子数
void zhonggen(bitree head)
{
    if (head != NULL)
        {
            if (head->lchild != NULL)  zuo++;   //左孩子深度
            zhonggen(head->lchild);
            printf("%-4d",head->data);          //中序输出数据
            if ((head->lchild == NULL) && (head->rchild == NULL))
                                    yezi++;  //叶子是左右指针为空的数
            if (head->rchild != NULL)  you++;   //右孩子深度
            zhonggen(head->rchild);
        }
}

void jiedian(bitree head)   //求结点
{
    if (head != NULL)
    {   //左孩子或者右孩子不为空则是结点
        if ((head->lchild != NULL) || (head->rchild != NULL))
        printf("%-4d",head->data);
        jiedian(head->lchild);
        jiedian(head->rchild);
    }
}

bitree chazhao(bitree head,int key)        //二叉树上的对应数值查找
{
    if (head == NULL)  return (NULL);
    else
        {                                  //根据返回值不为空做为存在该数据的依据
            if (head->data == key)  return (head);
            if (head->data > key)   return (chazhao(head->lchild,key));
            if (head->data < key)   return (chazhao(head->rchild,key));
        }
}

int main()
{
    bitree t=0;
    create(&t);
    printf("中序是：");
    zhonggen(t);
    printf("\n树的深度是：%d",max(zuo,you));    //取最大的深度为树的深度
    printf("\n树的叶子数是：%d",yezi);
    printf("\n树的结点是：\n");
    jiedian(t);                                 //输出哪些是结点
    p=chazhao(t,4);
    if (p == NULL)      printf("无该数据！\n");
    else                printf("查找成功！\n");
    getch();
    return 0;
}