树结构练习——排序二叉树的中序遍历
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
在树结构中，有一种特殊的二叉树叫做排序二叉树，直观的理解就是——(1).每个节点中包含有一个关键值 (2).任意一个节点的左子树（如果存在的话）的关键值小于该节点的关键值 (3).任意一个节点的右子树（如果存在的话）的关键值大于该节点的关键值。现给定一组数据，请你对这组数据按给定顺序建立一棵排序二叉树，并输出其中序遍历的结果。
输入
输入包含多组数据，每组数据格式如下。
第一行包含一个整数n，为关键值的个数，关键值用整数表示。(n<=1000)
第二行包含n个整数，保证每个整数在int范围之内。
输出
为给定的数据建立排序二叉树，并输出其中序遍历结果，每个输出占一行。
示例输入
1 2 2 1 20
示例输出
2 1 20
投机取巧代码1：（直接对结点值进行从小到大的排序，并输出）
1 #include<stdio.h>
2 int main()
3 {
4 int n;
5 while(~scanf("%d",&n))
6 {
7 int f[2000];
8 int i;
9 for(i=0;i<=n-1;i++)
10 scanf("%d",&f[i]);
11 int j;
12 for(i=0;i<=n-2;i++)
13 for(j=i;j<=n-1;j++)
14 {
15 if(f[i]>f[j])
16 {
17 int t;
18 t=f[i];
19 f[i]=f[j];
20 f[j]=t;
21 }
22 }
23 for(i=0;i<=n-1;i++)
24 if(i!=n-1)printf("%d ",f[i]);
25 else printf("%d
",f[i]);
26 }
27 return 0;
28 }
常规思路代码2：（建立排序二叉树，并中序遍历输出）
1 #include <stdio.h>
2 #include <stdlib.h>
3 typedef struct node
4 {
5 int data;
6 struct node*l, *r;
7 } tree, *root;
8 int k, count;//k和count是全局变量
9 void middle(root t)
10 {
11 if(t != NULL)
12 {
13 middle(t->l);
14 printf("%d",t->data);
15 if(count > 1)
16 {
17 printf(" ");
18 count--;
19 }
20 middle(t->r);
21 }
22 }
23 root build(root t)
24 {
25 int n, i;
26 root q=t;//q在这里是根节点,起到暂时存储根节点的作用
27 for(i = 1; i <= k-1; i++)//输入剩余的k-1个结点
28 {
29 t=q;//每次都从根节点开始查找
30 scanf("%d",&n);
31 while(1)
32 {
33 if(n < t->data)
34 {
35 if(t->l == NULL)
36 {
37 root p;
38 p = (root) malloc(sizeof(tree));
39 p ->l = NULL;
40 p->r = NULL;
41 p->data = n;
42 t->l = p;
43 break;//break的作用是终止当前循环
44 }
45 else
46 t = t->l;
47 }
48 else
49 {
50 if(t->r == NULL)
51 {
52 root p;
53 p = (root) malloc(sizeof(tree));
54 p->data = n;
55 p->l = NULL;
56 p->r = NULL;
57 t->r = p;
58 break;
59 }
60 else
61 t = t->r;
62 }
63 }
64 }
65 return q;
66 }
67 int main()
68 {
69 root t;
70 while(~scanf("%d",&k))
71 {
72 count = k;
73 //初始化树
74 t = (root) malloc(sizeof(tree));
75 scanf("%d",&t->data);
76 t->l = NULL;
77 t->r = NULL;
78 t=build(t);//建树
79 middle(t);//中序遍历
80 printf("
");
81 }
82 return 0;
83 }