938
九度题目1201：二叉排序树
题目1201：二叉排序树时间限制：1 秒内存限制：32 兆特殊判题：否提交：3008解决：1262
题目描述：
输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
输入：
输入第一行包括一个整数n(1=n=100)。
接下来的一行包括n个整数。
输出：
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。
每种遍历结果输出一行。每行最后一个数据之后有一个空格。
样例输入：
5
1 6 5 9 8
样例输出：
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1
提示：
输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。
来源：
2005年华中科技大学计算机保研机试真题
AC代码：
ps：这一回算是正儿八经学一回指针了。。。。
#include<stdio.h>
#include<string.h>
struct node
{
int data;
struct node *Ltree;
struct node *Rtree;
};
//Node *head;就是Node*head=0;head没指向任何对象.
//Node *head=new Node；head指向一个Node型的对象.
node *head=new node(); //申请二叉树的指针且分配了结构体空间
//前序遍历
void PreOrder(node *head)
{
if(head)
{
printf("%d ",head->data);
PreOrder(head->Ltree);
PreOrder(head->Rtree);
}
}
//中序遍历
void InOrder(node *head)
{
if(head)
{
InOrder(head->Ltree);
printf("%d ",head->data);;
InOrder(head->Rtree);
}
}
//后序遍历
void PostOrder(node *head)
{
if(head)
{
PostOrder(head->Ltree);
PostOrder(head->Rtree);
printf("%d ",head->data);
}
}
//撤销二叉树
void deleteTree(node *head)
{
if(head)
{
deleteTree(head->Ltree);
deleteTree(head->Rtree);
delete head;
}
}
//建立二叉排序树
void buildBinarySortTree(node *head,int elem[],int length)
{
node *p,*pre;
int flagLeftOrRight;
int success;
head->data=elem[0];
head->Ltree=NULL;
head->Rtree=NULL;
for(int i=1;i<length;i++)
{
success=0;
pre=NULL;
p=head;
while(p)//寻找插入的位置
{
pre=p;
if(p->data==elem[i])//查找成功
{
success=1;
break;
}
else if(p->data<elem[i])
{
p=p->Rtree;
flagLeftOrRight=1;
}
else
{
p=p->Ltree;
flagLeftOrRight=0;
}
}
if(!success)
{
p=new node();//生成新节点
p->data=elem[i];
p->Ltree=NULL;
p->Rtree=NULL;
if(flagLeftOrRight==0)
{
pre->Ltree=p;
}
else if(flagLeftOrRight==1)
{
pre->Rtree=p;
}
}
}
}
int main()
{
int i,j,n,m;
int elem[110];
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%d",&elem[i]);
}
buildBinarySortTree(head,elem,n);
PreOrder(head);
puts("");
InOrder(head);
puts("");
PostOrder(head);
puts("");
}
return 0;
}
最后更新：2017-04-03 12:56:43