【题目来源】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它的左、右子树也分别为二叉排序树。● 二叉排序树遵循“左小右大”规则树中没有相同关键字的结点。● 中序遍历一棵二叉排序树可以得到一个结点值递增的有序序列。● lch[u] 左孩子rch[u] 右孩子初始全部为 00 表示空。【算法代码】#includebits/stdc.husingnamespacestd;constintmaxn1e55;intlch[maxn],rch[maxn];voidinsert(intu,intx){if(xu) {if(lch[u]0) lch[u]x;elseinsert(lch[u],x); }else{if(rch[u]0) rch[u]x;elseinsert(rch[u],x); } }voidin(intu){//in-Orderif(u0)return;in(lch[u]); coutu ;in(rch[u]); }voidpost(intu){//post-Orderif(u0)return;post(lch[u]);post(rch[u]); coutu ; }intmain(){intn,x,root; cinn;for(inti1; in; i) { cinx;if(i1) rootx;elseinsert(root,x); }in(root),coutendl,post(root);return0; }/* 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/163724358https://blog.csdn.net/a10b12c13d14e15/article/details/164401168https://blog.csdn.net/hnjzsyjyj/article/details/120397275https://blog.csdn.net/hnjzsyjyj/article/details/154818899
