企业官网建设流程全解析

【第k小的数】

给定一棵n个结点的二叉搜索树，要求其中第k小的值（k<=n）。数据保证输入的是二叉搜索树。
【输入描述】
第一行是一个整数 n， 表示二叉树的结点个数。 二叉树结点编号从 1到 n（1<= n <= 10） ， 根结点为 1。接下来有 n 行， 依次对应二叉树的 n 个结点。
每行有3个整数， 分别表示该结点的值、左儿子和右儿子的结点编号。 如果第2个（第3个） 数为-1 则表示没有左（右） 儿子。最后一行一个整数表示k（k<=n）。
【输出描述】
一个整数表示二叉搜索树中第k小的值。
【输入样例】
7
13 2 6
3 3 4
2 -1 -1
5 5 -1
4 -1 -1
15 -1 7
17 -1 -1
4
【输出样例】
5
【提示】中序遍历二叉搜索树，遍历到第k个结点输出，结束遍历。

#include<iostream>usingnamespacestd;#defineSIZE10+1#defineNULLID-1//本题-1是空节点编号structNode{intvalue;//结点的值intleft;//左子结点的下标intright;//右子结点的下标};Node tree[SIZE];intn,k;intcnt=0;// 中序遍历二叉树，遍历到k个结点输出voidinOrder(introot){if(root==NULLID)return;inOrder(tree[root].left);//左子树递归//cout << tree[root].value << " ";cnt++;if(cnt==k){cout<<tree[root].value;}inOrder(tree[root].right);//右子树递归}intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>tree[i].value>>tree[i].left>>tree[i].right;}cin>>k;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。
【输入样例】
abc
cba
【输出样例】
4
【提示】观察图例可以发现，在知道前序、后序序列的情况下有不同的中序序列，只有当这个结点只有一个子结点。
例如前序中出现AB，后序出现BA，则这个A只有一个子结点B，统计满足这个条件的长度2的子序列的个数x。
每个这种序列的中序序列有2个，一棵树有x个这种序列，中序序列的数量就是2^x。

#include<iostream>#include<cstring>usingnamespacestd;#defineMAXN100010intans;charpreorder[MAXN],postorder[MAXN];intmain(){cin>>preorder>>postorder;intlen=strlen(preorder);// 统计长度2的子序列 换位相等的情况for(inti=0;i<len-1;i++){for(intj=0;j<len-1;j++){if(preorder[i]==postorder[j+1]&&preorder[i+1]==postorder[j])ans++;}}cout<<(1<<ans)<<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到 n（1<= n <= 10） ， 根结点为 1。
接下来有 n 行， 依次对应二叉树的 n 个结点。 每行有3个整数， 分别表示该结点的值、左儿子和右儿子的结点编号。 如果第2个（第3个） 数为-1 则表示没有左（右） 儿子。
最后一行一个整数 x。（数据保证输入的是二叉搜索树）
【输出描述】
一个整数表示 x 在二叉搜索树中的排位。 如果x不在树中，输出-1。
【输入样例】
7
13 2 6
3 3 4
2 -1 -1
5 5 -1
4 -1 -1
15 -1 7
17 -1 -1
4
【输出样例】
3
【提示】中序遍历二叉搜索树并对结点计数，当遍历到值为x的结点输出计数值。 没找到单独处理。

#include<iostream>usingnamespacestd;#defineSIZE10+1#defineNULLID-1//本题-1是空节点编号structNode{intvalue;//结点的值intleft;//左子结点的下标intright;//右子结点的下标};Node tree[SIZE];intn,x;intcnt=0;boolflag=false;// 中序遍历二叉树，遍历到k个结点输出voidinOrder(introot){if(root==NULLID)return;inOrder(tree[root].left);//左子树递归//cout << tree[root].value << " ";cnt++;if(tree[root].value==x){cout<<cnt;flag=true;}inOrder(tree[root].right);//右子树递归}intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>tree[i].value>>tree[i].left>>tree[i].right;}cin>>x;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到 n（1<= n <= 10） ， 根结点为 1。
接下来有 n 行， 依次对应二叉树的 n 个结点。 每行有3个整数， 分别表示该结点的值、左儿子和右儿子的结点编号。 如果第2个（第3个） 数为-1 则表示没有左（右） 儿子。
最后一行一个整数 x。（数据保证输入的是二叉搜索树，x是其中的值）
【输出描述】
两行。第1行一个整数表示 x 在二叉搜索树中的前驱值。第1行一个整数表示 x 在二叉搜索树中的后继值。
如果x没有前驱或后继，输出"NON"。
【输入样例】
7
13 2 6
3 3 4
2 -1 -1
5 5 -1
4 -1 -1
15 -1 7
17 -1 -1
4
【输出样例】
3
5
【提示】中序遍历二叉树，得到中序序列。在中序序列中找x和x的前驱和后继。

#include<iostream>usingnamespacestd;#defineSIZE10+1#defineNULLID-1//本题-1是空节点编号structNode{intvalue;//结点的值intleft;//左子结点的下标intright;//右子结点的下标};Node tree[SIZE];intn,x;intp=0;intarr[SIZE];//中序序列// 中序遍历二叉树，得到中序序列voidinOrder(introot){if(root==NULLID)return;inOrder(tree[root].left);//左子树递归p++;arr[p]=tree[root].value;inOrder(tree[root].right);//右子树递归}intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>tree[i].value>>tree[i].left>>tree[i].right;}cin>>x;inOrder(1);for(inti=1;i<=p;i++){if(arr[i]==x){if(i>1)cout<<arr[i-1]<<endl;elsecout<<"NON"<<endl;if(i<p)cout<<arr[i+1]<<endl;elsecout<<"NON"<<endl;}}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 */