计算机C语言二级考试真题：6二叉排序树

#include <stdio.h>
#include <malloc.h>
typedef int elemtype ;
typedef struct btreenode
{
elemtype Data;
struct btreenode *lchild;
struct btreenode *rchild;
}TREENODE;
TREENODE *Create(elemtype x,TREENODE *lbt,TREENODE *rbt);
TREENODE *InsertL(elemtype x,TREENODE *Parent);
TREENODE *InsertR(elemtype x,TREENODE *Parent);
void preorder(TREENODE *bt);
void inorder(TREENODE *bt);
void postorder(TREENODE *bt);
int countx(TREENODE *p,elemtype x);
int countleaf(TREENODE *p);
main( )
{
int x,y;
TREENODE *bt,*p,*q;
printf("input root");
scanf("%d",&x);
p=Create(x,NULL,NULL);
bt=p;
printf("please input data,-1--end,");
scanf("%d",&x);
while(x!=-1)
{
p=bt;
q=p;
while(q!=NULL)
{
p=q;
if(x<p->Data)
q=p->lchild;
else
q=p->rchild;
}
if(x<p->Data)
InsertL(x,p);
else
InsertR(x,p);
printf("please input data,-1--end,");
scanf("%d",&x);
}
printf("\n先序遍历结果为：");
preorder(bt);
printf("\n中序遍历结果为：");
inorder(bt);
printf("\n后序遍历结果为：");
postorder(bt);
printf("\nleaf:%d\n",countleaf(bt));
printf("input x you want to summarize:");
scanf("%d",&y);
printf("%d\n",countx(bt,y));
}
TREENODE *Create(elemtype x,TREENODE *lbt,TREENODE *rbt)
{
TREENODE *p;
if((p=(TREENODE * )malloc(sizeof(TREENODE)))==NULL)
return NULL;
p->Data=x;
p->lchild=lbt;
p->rchild=rbt;
return p;
}
TREENODE *InsertL(elemtype x,TREENODE *Parent)
{
TREENODE *p;
if(Parent==NULL)
{
printf("\n插入出错！");
return NULL;
}
if((p=(TREENODE * )malloc(sizeof(TREENODE)))==NULL)
return NULL;
p->Data=x;
p->lchild=NULL;
p->rchild=NULL;
if(Parent->lchild==NULL)
Parent->lchild=p;
else
{
p->lchild=Parent->lchild;
Parent->lchild=p;
}
return p;
}
TREENODE *InsertR(elemtype x,TREENODE *Parent)
{
TREENODE *p;
if(Parent==NULL)
{
printf("\n插入出错！");
return NULL;
}
if((p=(TREENODE *)malloc(sizeof(TREENODE)))==NULL)
return NULL;
p->Data=x;
p->lchild=NULL;
p->rchild=NULL;
if(Parent->rchild==NULL)
Parent->rchild=p;
else
{
p->rchild=Parent->rchild;
Parent->rchild=p;
}
return p;
}
void preorder(TREENODE *bt)
{
if(bt==NULL)
return;
printf(" %d",bt->Data);
preorder(bt->lchild);
preorder(bt->rchild);
}
void inorder(TREENODE *bt)
{
if(bt==NULL)
return;
inorder(bt->lchild);
printf(" %d",bt->Data);
inorder(bt->rchild);
}
void postorder(TREENODE *bt)
{
if(bt==NULL)
return;
postorder(bt->lchild);
postorder(bt->rchild);
printf(" %d",bt->Data);
}
int countx(TREENODE *p,elemtype x)
{
int count=0;
if(p==NULL)
return NULL;
if(p->Data==x)
count++;
count+=countx(p->lchild,x);
count+=countx(p->rchild,x);
return count;
}
int countleaf(TREENODE *p)
{
int count=0;
if(p)
if(p->lchild==NULL && p->rchild==NULL)
count++;
else
{
count+=countleaf(p->lchild);
count+=countleaf(p->rchild);
}
return count;
}