数据结构二叉树

8086zzl

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef char TElemtype;
typedef int status;
typedef struct BiTNode
{
        TElemtype date;//数据域
        struct BiTNode *lchild;//左孩子指针
        struct BiTNode *rchild;//右孩子指针
}BiTNode,*BiTree;
status Insert(BiTree &T,TElemtype e);
status SearchBST(BiTree T,TElemtype e,BiTree m,BiTree &p);
status CreateBST(BiTree &T)
{
        int n,i,a[100];
        printf("输入要创建的二叉排序树的节点个数:\n");
        scanf("%d",&n);
        if(n<=0)//判断输入的合法性
        {
                printf("输入有误!\n");
                return ERROR;
        }
        else
        printf("请输入节点值:\n");
        T=NULL;//初始化树
        for(i=1;i<=n;i++)
        {
                scanf("%d",&a[i]);
                Insert(T,a[i]);
        }
        return OK;
}
status Insert(BiTree &T,TElemtype e)//当二叉树T中不存在为e的数据元素，插入e
{
        BiTree s,p;
        if(!SearchBST(T,e,NULL,p))
        {
                s=(BiTNode *)malloc(sizeof(BiTNode));
                s->date=e;
                s->lchild=s->rchild=NULL;
                if(!p)//当二叉排序树为空时，插入的节点s作为根节点
                T=s;
                else if(e<p->date)//当插入的节点值小于关键节点值
                p->lchild=s;//被插节点作为左孩子
                else
                p->rchild=s;//被插节点作为右孩子
                return OK;
        }
        else
        return ERROR;
}
status SearchBST(BiTree T,TElemtype e,BiTree m,BiTree &p)//动态查找
{
        if(!T)//树为空，查找不成功
        {
                p=m;
                return ERROR;
        }
        else if(e==T->date)//从根开始，查找成功，指针p指向该节点
        {
                p=T;
                return OK;
        }
        else if(e<T->date)
        return SearchBST(T->lchild,e,T,p);//此时m为双亲 (T)
        else if(e>T->date)
        return SearchBST(T->rchild,e,T,p);//递归遍历每一个节点
}
status InorderTraverse(BiTree T)//中序遍历二叉树
{
        if(T)
        {
                InorderTraverse(T->lchild);//先遍历左子树
                printf(" %d",T->date);//再遍历根节点
                InorderTraverse(T->rchild);//最后遍历右子树
        }
        return OK;
}

int main()
{
        BiTree T,M,p;
        CreateBST(T);
        printf("中序遍历排序二叉树\n");
        InorderTraverse(T);
        printf("\n");
        TElemtype e,n;
        printf("请输入要查找的元素:\n");
        scanf("%d",&e);
        n=SearchBST(T,e,M,p);
        if(n)
        printf("查找成功!树中存在%d\n",e);
        else
        printf("查找失败!树中不存在%d\n",e);
}