4518: 【例】【入门】二叉排序树(2195)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：3
题目描述
从键盘读入 个不相同的整数，以每个整数作为结点的值，来创建一棵二叉排序树，假设读入的第 个点是这棵树的根结点。
请求出这棵二叉排序树中序和后续遍历的结果？
输入
共两行，第一行为整数 ；
第二行为 个不重复的整数 。（，，本题中为随机生成的数值）
输出
共两行，第一行为中序遍历的结果，第二行为后序遍历的结果，同一行的输出用空格隔开。
样例输入 复制
8
23 45 12 6 7 89 13 47样例输出 复制
6 7 12 13 23 45 47 89
7 6 13 12 47 89 45 23提示
（1）定义
二叉排序树具有这样的性质：任何结点的值都大于它左子树上结点的值小于右子树上结点的值，然后采用中序遍历就可以生成一个有序序列。
（2）建立二叉排序树
生成一个结点，加入到树中，如果不是根结点，再根据大小决定这个结点是插在某个结点的左子树上还是右子树上，如此重复。
（3）二叉排序树的查找
从根结点开始，如果要查找的数与该结点不相等，则根据与该结点的值比较，选择查找左子树，还是右子树，直到没有结点。
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
struct node {
int data;
int lc,rc;
}a[N];
int n;
void dfs2(int x) {
if (a[x].lc) dfs2(a[x].lc);
cout<<a[x].data<<" ";
if (a[x].rc) dfs2(a[x].rc);
}
void dfs3(int x) {
if (a[x].lc) dfs3(a[x].lc);
if (a[x].rc) dfs3(a[x].rc);
cout<<a[x].data<<" ";
}
int main(){
cin>>n;
int x,p;
for(int i=1;i<=n;i++) {
cin>>x;
a[i].data=x;
if(i==1) continue;
p=1;
while(1) {
if(x<a[p].data) {
if(a[p].lc) p=a[p].lc;
else {
a[p].lc=i;
break;
}
}
if(x>a[p].data) {
if(a[p].rc) p=a[p].rc;
else {
a[p].rc=i;
break;
}
}
}
}
dfs2(1);
cout<<endl;
dfs3(1);
return 0;
}