【题目来源】
【题目描述】
从键盘读入 n 个不相同的整数，以每个整数作为结点的值，来创建一棵二叉排序树，假设读入的第 1 个点是这棵树的根结点。
请求出这棵二叉排序树中序和后续遍历的结果？
【输入格式】
共两行，第一行为整数 n。;
第二行为 n 个不重复的整数 ai。
(0<n<10^5，1≤ai≤10^5，本题中 ai 为随机生成的数值)
【输出格式】
共两行，第一行为中序遍历的结果，第二行为后序遍历的结果，同一行的输出用空格隔开。
【输入样例】
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
【数据范围】
0<n<10^5，1≤ai≤10^5
【算法分析】
● 二叉排序树（Binary Sort Tree，BST），又称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树。
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）它的左、右子树也分别为二叉排序树。
● 二叉排序树遵循“左小右大”规则，树中没有相同关键字的结点。
● 中序遍历一棵二叉排序树可以得到一个结点值递增的有序序列。
● 去重与不去重的代码，差别在于三个地方：
（1）去重代码中的 insert 函数，加上 if(v==tr[u].val) return u;
（2）去重代码中输出中序遍历的 for 循环判定条件为 i<idx_in
（3）去重代码中输出后序遍历的 for 循环判定条件为 i<idx_post
【算法代码一：去重】
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
int in_seq[N],post_seq[N];
int idx_in,idx_post;
int tot=0;struct Node {int val;int le,ri;
} tr[N];int createNode(int v) {tot++;tr[tot].val=v;tr[tot].le=tr[tot].ri=0;return tot;
}int insert(int u,int v) {if(!u) return createNode(v);if(v==tr[u].val) return u;if(v<tr[u].val) tr[u].le=insert(tr[u].le,v);else tr[u].ri=insert(tr[u].ri,v);return u;
}void inOrder(int u) {if(!u) return;inOrder(tr[u].le);in_seq[idx_in++]=tr[u].val;inOrder(tr[u].ri);
}void postOrder(int u) {if(!u) return;postOrder(tr[u].le);postOrder(tr[u].ri);post_seq[idx_post++]=tr[u].val;
}int main() {ios::sync_with_stdio(0);cin.tie(0);int n,root=0;cin>>n;for(int i=0; i<n; i++) {int x;cin>>x;root=insert(root,x);}inOrder(root);postOrder(root);for(int i=0; i<idx_in; i++) {cout<<in_seq[i]<<" ";}cout<<"\n";for(int i=0; i<idx_post; i++) {cout<<post_seq[i]<<" ";}cout<<"\n";return 0;
}/*
in:
8
23 36 12 6 7 89 13 12out:
6 7 12 13 23 36 89
7 6 13 12 89 36 23
*/
【算法代码二：不去重】
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
int in_seq[N],post_seq[N];
int idx_in,idx_post;
int tot=0;struct Node {int val;int le,ri;
} tr[N];int createNode(int v) {tot++;tr[tot].val=v;tr[tot].le=tr[tot].ri=0;return tot;
}int insert(int u,int v) {if(!u) return createNode(v);if(v<tr[u].val) tr[u].le=insert(tr[u].le,v);else tr[u].ri=insert(tr[u].ri,v);return u;
}void inOrder(int u) {if(!u) return;inOrder(tr[u].le);in_seq[idx_in++]=tr[u].val;inOrder(tr[u].ri);
}void postOrder(int u) {if(!u) return;postOrder(tr[u].le);postOrder(tr[u].ri);post_seq[idx_post++]=tr[u].val;
}int main() {ios::sync_with_stdio(0);cin.tie(0);int n,root=0;cin>>n;for(int i=0; i<n; i++) {int x;cin>>x;root=insert(root,x);}inOrder(root);postOrder(root);for(int i=0; i<n; i++) {cout<<in_seq[i]<<" ";}cout<<"\n";for(int i=0; i<n; i++) {cout<<post_seq[i]<<" ";}cout<<"\n";return 0;
}/*
in:
8
23 45 12 6 7 89 13 47out:
6 7 12 13 23 45 47 89
7 6 13 12 47 89 45 23
*/
【参考文献】