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