【第k小的数】给定一棵n个结点的二叉搜索树要求其中第k小的值kn。数据保证输入的是二叉搜索树。【输入描述】第一行是一个整数 n 表示二叉树的结点个数。 二叉树结点编号从 1到 n1 n 10 根结点为 1。接下来有 n 行 依次对应二叉树的 n 个结点。每行有3个整数 分别表示该结点的值、左儿子和右儿子的结点编号。 如果第2个第3个 数为-1 则表示没有左右 儿子。最后一行一个整数表示kkn。【输出描述】一个整数表示二叉搜索树中第k小的值。【输入样例】713 2 63 3 42 -1 -15 5 -14 -1 -115 -1 717 -1 -14【输出样例】5【提示】中序遍历二叉搜索树遍历到第k个结点输出结束遍历。#includeiostreamusingnamespacestd;#defineSIZE101#defineNULLID-1//本题-1是空节点编号structNode{intvalue;//结点的值intleft;//左子结点的下标intright;//右子结点的下标};Node tree[SIZE];intn,k;intcnt0;// 中序遍历二叉树遍历到k个结点输出voidinOrder(introot){if(rootNULLID)return;inOrder(tree[root].left);//左子树递归//cout tree[root].value ;cnt;if(cntk){couttree[root].value;}inOrder(tree[root].right);//右子树递归}intmain(){cinn;for(inti1;in;i){cintree[i].valuetree[i].lefttree[i].right;}cink;inOrder(1);return0;}/* 本题测试点 【样例输入1】 5 1 2 3 2 4 5 3 -1 -1 4 -1 -1 5 -1 -1 3 【样例输出1】 5 【样例输入2】 3 1 2 -1 2 3 -1 3 -1 -1 1 【样例输出2】 3 【样例输入3】 3 1 2 -1 2 3 -1 3 -1 -1 3 【样例输出3】 1 【样例输入4】 4 1 2 -1 2 3 -1 3 4 -1 4 -1 -1 2 【样例输出4】 3 【样例输入5】 4 1 -1 2 2 -1 3 3 -1 4 4 -1 -1 4 【样例输出5】 4 */遍历问题【题目描述】我们都很熟悉二叉树的前序、中序、后序遍历在数据结构中常提出这样的问题已知一棵二叉树的前序和中序遍历求它的后序遍历相应的已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历你却不能确定其中序遍历序列考虑如下图中的几棵二叉树所有这些二叉树都有着相同的前序遍历和后序遍历但中序遍历却不相同。【输入格式】共两行第一行表示该二叉树的前序遍历结果 s1 第二行表示该二叉树的后序遍历结果 s2 。保证至少存在一棵二叉树满足给出的信息s1,s2 中只含小写字母且在某个字符串中不存在相同的字母。【输出格式】输出可能的中序遍历序列的总数结果不超过 2^63-1。【输入样例】abccba【输出样例】4【提示】观察图例可以发现在知道前序、后序序列的情况下有不同的中序序列只有当这个结点只有一个子结点。例如前序中出现AB后序出现BA则这个A只有一个子结点B统计满足这个条件的长度2的子序列的个数x。每个这种序列的中序序列有2个一棵树有x个这种序列中序序列的数量就是2^x。#includeiostream#includecstringusingnamespacestd;#defineMAXN100010intans;charpreorder[MAXN],postorder[MAXN];intmain(){cinpreorderpostorder;intlenstrlen(preorder);// 统计长度2的子序列 换位相等的情况for(inti0;ilen-1;i){for(intj0;jlen-1;j){if(preorder[i]postorder[j1]preorder[i1]postorder[j])ans;}}cout(1ans)endl;return0;}/* 本题测试点 【样例输入1】 abc cba 【样例输出1】 4 【样例输入2】 abc bca 【样例输出2】 1 【样例输入3】 abcdefg cedbgfa 【样例输出3】 4 【样例输入4】 abdceghf dbhgefca 【样例输出4】 8 【样例输入5】 bacdefgh hgfedcab 【样例输出5】 128 */【x的排名】给定一棵n个结点的二叉搜索树要求数值x在其中的排位。 约定二叉搜索树中最小的值排第1。【输入描述】第一行是一个整数 n 表示二叉树的结点个数。 二叉树结点编号从 1到 n1 n 10 根结点为 1。接下来有 n 行 依次对应二叉树的 n 个结点。 每行有3个整数 分别表示该结点的值、左儿子和右儿子的结点编号。 如果第2个第3个 数为-1 则表示没有左右 儿子。最后一行一个整数 x。数据保证输入的是二叉搜索树【输出描述】一个整数表示 x 在二叉搜索树中的排位。 如果x不在树中输出-1。【输入样例】713 2 63 3 42 -1 -15 5 -14 -1 -115 -1 717 -1 -14【输出样例】3【提示】中序遍历二叉搜索树并对结点计数当遍历到值为x的结点输出计数值。 没找到单独处理。#includeiostreamusingnamespacestd;#defineSIZE101#defineNULLID-1//本题-1是空节点编号structNode{intvalue;//结点的值intleft;//左子结点的下标intright;//右子结点的下标};Node tree[SIZE];intn,x;intcnt0;boolflagfalse;// 中序遍历二叉树遍历到k个结点输出voidinOrder(introot){if(rootNULLID)return;inOrder(tree[root].left);//左子树递归//cout tree[root].value ;cnt;if(tree[root].valuex){coutcnt;flagtrue;}inOrder(tree[root].right);//右子树递归}intmain(){cinn;for(inti1;in;i){cintree[i].valuetree[i].lefttree[i].right;}cinx;inOrder(1);if(!flag)cout-1;return0;}/* 本题测试点 【样例输入1】 7 13 2 6 3 3 4 2 -1 -1 5 5 1 4 -1 -1 15 -1 7 17 -1 -1 4 【样例输出1】 3 【样例输入2】 7 13 2 6 3 3 4 2 -1 -1 5 5 -1 4 -1 -1 15 -1 7 17 -1 -1 18 【样例输出2】 -1 【样例输入3】 7 13 2 6 3 3 4 2 -1 -1 5 5 -1 4 -1 -1 15 -1 7 17 -1 -1 2 【样例输出3】 1 【样例输入4】 7 13 2 6 3 3 4 2 -1 -1 5 5 -1 4 -1 -1 15 -1 7 17 -1 -1 17 【样例输出4】 7 【样例输入5】 1 12 -1 -1 1 【样例输出5】 -1 */【x的前驱和后继】给定一棵n个结点的二叉搜索树要求输出数值x的前驱和后继。x的前驱定义为二叉树结点值中小于x的且最大的那个值。x的后继定义为二叉树结点值中大于x的且最小的那个值。【输入描述】第一行是一个整数 n 表示二叉树的结点个数。 二叉树结点编号从 1到 n1 n 10 根结点为 1。接下来有 n 行 依次对应二叉树的 n 个结点。 每行有3个整数 分别表示该结点的值、左儿子和右儿子的结点编号。 如果第2个第3个 数为-1 则表示没有左右 儿子。最后一行一个整数 x。数据保证输入的是二叉搜索树x是其中的值【输出描述】两行。第1行一个整数表示 x 在二叉搜索树中的前驱值。第1行一个整数表示 x 在二叉搜索树中的后继值。如果x没有前驱或后继输出NON。【输入样例】713 2 63 3 42 -1 -15 5 -14 -1 -115 -1 717 -1 -14【输出样例】35【提示】中序遍历二叉树得到中序序列。在中序序列中找x和x的前驱和后继。#includeiostreamusingnamespacestd;#defineSIZE101#defineNULLID-1//本题-1是空节点编号structNode{intvalue;//结点的值intleft;//左子结点的下标intright;//右子结点的下标};Node tree[SIZE];intn,x;intp0;intarr[SIZE];//中序序列// 中序遍历二叉树得到中序序列voidinOrder(introot){if(rootNULLID)return;inOrder(tree[root].left);//左子树递归p;arr[p]tree[root].value;inOrder(tree[root].right);//右子树递归}intmain(){cinn;for(inti1;in;i){cintree[i].valuetree[i].lefttree[i].right;}cinx;inOrder(1);for(inti1;ip;i){if(arr[i]x){if(i1)coutarr[i-1]endl;elsecoutNONendl;if(ip)coutarr[i1]endl;elsecoutNONendl;}}return0;}/* 本题测试点 【样例输入1】 7 13 2 6 3 3 4 2 -1 -1 5 5 -1 4 -1 -1 15 -1 7 17 -1 -1 2 【样例输出1】 NON 3 【样例输入2】 7 13 2 6 3 3 4 2 -1 -1 5 5 -1 4 -1 -1 15 -1 7 17 -1 -1 17 【样例输出2】 15 NON 【样例输入3】 2 12 2 -1 2 -1 -1 2 【样例输出3】 NON 12 【样例输入4】 1 12 -1 -1 12 【样例输出4】 NON NON 【样例输入5】 7 13 2 6 3 3 4 2 -1 -1 5 5 -1 4 -1 -1 15 -1 7 17 -1 -1 4 【样例输出5】 3 5 */