数据结构二叉树
#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;
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);
Insert(T,a);
}
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);
}
页:
[1]