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