SDUTOJ2128 二叉排序树



SDUTOJ2128 二叉排序树。

题目连接：点击打开链接

 

在树结构中，有一种特殊的二叉树叫做排序二叉树，直观的理解就是——(1).每个节点中包含有一个关键值 (2).任意一个节点的左子树（如果存在的话）的关键值小于该节点的关键值 (3).任意一个节点的右子树（如果存在的话）的关键值大于该节点的关键值。现给定一组数据，请你对这组数据按给定顺序建立一棵排序二叉树，并输出其中序遍历的结果。

输入

输入包含多组数据，每组数据格式如下。
第一行包含一个整数n，为关键值的个数，关键值用整数表示。(n<=1000)
第二行包含n个整数，保证每个整数在int范围之内。

输出

为给定的数据建立排序二叉树，并输出其中序遍历结果，每个输出占一行。

 

  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. using namespace std;
  6. struct node
  7. {
  8.     int data;
  9.     node *l,*r;
  10. };
  11. int n;
  12. void Insert(node *&t,int data)
  13. {
  14.     if(t==NULL)
  15.     {
  16.         t = new node;
  17.         t->l = t->r = NULL;
  18.         t->data = data;
  19.     }
  20.     else
  21.     {
  22.         if(data < t->data)
  23.             Insert( t->l , data);
  24.         else
  25.             Insert( t->r , data);
  26.     }
  27. }
  29. node *root;
  31. void Creat()
  32. {
  33.     for(int i=0; i<n; i++)
  34.     {
  35.         int x;
  36.         scanf(“%d”,&x);
  37.         Insert(root,x);
  38.     }
  39. }
  40. int stk[1001],l;
  41. void mid(struct node *T)
  42. {
  43.     if(T!=NULL)
  44.     {
  45.         mid(T->l);
  46.         stk[l++] = T->data;
  48.         mid(T->r);
  49.     }
  50. }
  51. void Delete(struct node *t)
  52. {
  53.     if(t!=NULL)
  54.     {
  55.         Delete(t->l);
  56.         Delete(t->r);
  57.     }
  58.     delete(t);
  59. }
  61. int main()
  62. {
  64.         while(scanf(“%d”,&n)!=EOF)
  65.         {
  66.             l = 0;
  67.             root = NULL;
  68.             Creat();
  69.             mid(root);
  70.             Delete(root);
  71.             for(int i = 0;i<l-1;i++)
  72.             {
  73.                 printf(“%d “,stk[i]);
  74.             }
  75.             printf(“%d\n”,stk[l-1]);
  76.         }
  77.     return 0;
  78. }