SDUTOJ2128 二叉排序树。
题目连接:点击打开链接
在树结构中,有一种特殊的二叉树叫做排序二叉树,直观的理解就是——(1).每个节点中包含有一个关键值 (2).任意一个节点的左子树(如果存在的话)的关键值小于该节点的关键值 (3).任意一个节点的右子树(如果存在的话)的关键值大于该节点的关键值。现给定一组数据,请你对这组数据按给定顺序建立一棵排序二叉树,并输出其中序遍历的结果。
输入
输入包含多组数据,每组数据格式如下。
第一行包含一个整数n,为关键值的个数,关键值用整数表示。(n<=1000)
第二行包含n个整数,保证每个整数在int范围之内。
输出
为给定的数据建立排序二叉树,并输出其中序遍历结果,每个输出占一行。
- #include<iostream>
- #include<stdio.h>
- #include<stdlib.h>
- using namespace std;
- struct node
- {
- int data;
- node *l,*r;
- };
- int n;
- void Insert(node *&t,int data)
- {
- if(t==NULL)
- {
- t = new node;
- t->l = t->r = NULL;
- t->data = data;
- }
- else
- {
- if(data < t->data)
- Insert( t->l , data);
- else
- Insert( t->r , data);
- }
- }
- node *root;
- void Creat()
- {
- for(int i=0; i<n; i++)
- {
- int x;
- scanf(“%d”,&x);
- Insert(root,x);
- }
- }
- int stk[1001],l;
- void mid(struct node *T)
- {
- if(T!=NULL)
- {
- mid(T->l);
- stk[l++] = T->data;
- mid(T->r);
- }
- }
- void Delete(struct node *t)
- {
- if(t!=NULL)
- {
- Delete(t->l);
- Delete(t->r);
- }
- delete(t);
- }
- int main()
- {
- while(scanf(“%d”,&n)!=EOF)
- {
- l = 0;
- root = NULL;
- Creat();
- mid(root);
- Delete(root);
- for(int i = 0;i<l-1;i++)
- {
- printf(“%d “,stk[i]);
- }
- printf(“%d\n”,stk[l-1]);
- }
- return 0;
- }