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