Description
在树结构中，有一种特殊的二叉树叫做排序二叉树，直观的理解就是——(1).每个节点中包含有一个关键值 (2).任意一个节点的左子树（如果存在的话）的关键值小于该节点的关键值 (3).任意一个节点的右子树（如果存在的话）的关键值大于该节点的关键值。现给定一组数据，请你对这组数据按给定顺序建立一棵排序二叉树，并输出其中序遍历的结果。
Input
输入包含多组数据，每组数据格式如下。 第一行包含一个整数n，为关键值的个数，关键值用整数表示。(n<=1000) 第二行包含n个整数，保证每个整数在int范围之内。
Output
为给定的数据建立排序二叉树，并输出其中序遍历结果，每个输出占一行。
Sample Input
1
2
2
120
Output
2
120
参考程序（C语言实现）
#include <stdio.h>
#include <stdlib.h>
#define ROOM sizeof(struct TreeNode)
#define LEN 1000
int result[LEN+5],cnt;
struct TreeNode
{
int data;
struct TreeNode *LeftChild;
struct TreeNode *RightChild;
};
void InVisit(struct TreeNode *p)
{
if(p)
{
InVisit(p->LeftChild);
result[cnt++]=p->data;
InVisit(p->RightChild);
}
}
int main()
{
int n,key,i;
while(scanf("%d",&n)!=EOF)
{
struct TreeNode *root,*p1,*p2;
cnt=0;
scanf("%d",&key);
root=(struct TreeNode*)malloc(ROOM);
root->data=key;
root->LeftChild=NULL;
root->RightChild=NULL;
p2=root;
for(i=1;i<=n-1;i++)
{
scanf("%d",&key);
p1=(struct TreeNode*)malloc(ROOM);
p1->data=key;
p1->LeftChild=NULL;
p1->RightChild=NULL;
while(1)
{
if(key<p2->data)
{
if(!p2->LeftChild)
{
p2->LeftChild=p1;
break;
}
else
{
p2=p2->LeftChild;
}
}
else
{
if(!p2->RightChild)
{
p2->RightChild=p1;
break;
}
else
{
p2=p2->RightChild;
}
}
}
p2=root;
}
InVisit(root);
for(i=0;i<cnt-1;i++)
{
printf("%d ",result[i]);
}
printf("%d\n",result[i]);
}
return 0;
}
注意事项：
1、 在输出遍历序列时，要求数据和数据之间用空格分隔开，因而考虑在遍历时先将数据存放在一个数组中，最后再一并输出，这里设置全局变量result数组、计数变量cnt，要特别注意每组数据cnt都要置0；
2、 将结点加入二叉树中，类似于“单链表中插入结点的操作”，即需要找到恰当的位置插入结点，因此设置一个不变的值root表示根结点，p2表示一个活动的指针，初始时p2=root，p2用于寻找恰当的位置结点插入完成后，要重新将p2指向root，以便于下一次插入结点从根结点开始寻找合适的位置；
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: