苍溪县建设局网站,响应式电影网站,用自己的照片做头像的网站,上海网站建站服务参考文章#xff1a;L2-004. 这是二叉搜索树吗#xff1f;-PAT团体程序设计天梯赛GPLT 作者#xff1a;柳婼#xff08;非常感谢!!!#xff09; 一棵二叉搜索树可被递归地定义为具有下列性质的二叉树#xff1a;对于任一结点#xff0c; 其左子树中所有结点的键值小于… 参考文章L2-004. 这是二叉搜索树吗-PAT团体程序设计天梯赛GPLT 作者柳婼非常感谢!!! 一棵二叉搜索树可被递归地定义为具有下列性质的二叉树对于任一结点 其左子树中所有结点的键值小于该结点的键值 其右子树中所有结点的键值大于等于该结点的键值 其左右子树都是二叉搜索树。 所谓二叉搜索树的“镜像”即将所有结点的左右子树对换位置后所得到的树。 给定一个整数键值序列现请你编写程序判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。 输入格式 输入的第一行给出正整数 N≤1000。随后一行给出 N 个整数键值其间以空格分隔。 输出格式 如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果则首先在一行中输出 YES 然后在下一行输出该树后序遍历的结果。数字间有 1 个空格一行的首尾不得有多余空格。若答案是否则输出 NO。 输入样例1 7 8 6 5 7 10 8 11 输出样例1 YES 5 7 6 8 11 10 8 输入样例2 7 8 10 11 8 6 7 5 输出样例2 YES 11 8 10 7 5 6 8 输入样例3 7 8 6 8 5 10 9 11 输出样例3 NO #include iostream
#include vector
using namespace std;vectorint preOrder; //前序遍历序列
vectorint postOrder; //后序遍历序列
int n;
bool mirror false; //是否镜像搜索void creatBiTree(int pl, int pr) //搜索树建立
{if (pl pr) return;else if (pl pr) {postOrder.push_back(preOrder[pl]);return;}int l pl 1, r pr;if (!mirror){while (l pr preOrder[l] preOrder[pl])l;while (r pl preOrder[r] preOrder[pl])r--;}else{while (l pr preOrder[l] preOrder[pl])l;while (r pl preOrder[r] preOrder[pl])r--;}if (l - r ! 1) return;creatBiTree(pl 1, r);creatBiTree(l, pr);postOrder.push_back(preOrder[pl]);return;
}int main()
{int temp; cin n;for (int i 0; i n; i) {cin temp;preOrder.push_back(temp);}creatBiTree(0, n - 1);if (postOrder.size() ! n){mirror true;postOrder.clear();creatBiTree(0, n - 1);}if (postOrder.size() n){cout YES endl postOrder[0];for (int i 1; i n; i)cout postOrder[i];cout endl;}elsecout NO endl;return 0;
} 注意事项 不知道为什么下面的代码有两个测试点一直过不去…… #include iostream
#include vector
#include stdlib.h
using namespace std;vectorint preOrder;
int n, counts 0;
bool res1 true, res2 true;typedef struct biTreeNode { //定义二叉树结点int key;biTreeNode* lchild;biTreeNode* rchild;
}biTree, * BiTree;void creatBiTree1(BiTree T,int pl,int pr) //正常搜索树建立
{if (pl pr res1 true) {T (BiTree)malloc(sizeof(biTreeNode));int ll pl 1, rl pl 1 , lr pr, rr pr;T-key preOrder[pl];for (int i pl 1; i pr; i) {if (preOrder[i] T-key) {ll i; break; //找到第一个比key小的键值}else if (i pr) {T-lchild NULL;}}for (int i pl 1; i pr; i) {if (preOrder[i] T-key) {lr i - 1, rl i;break; //找到第一个比key大或相等的键值}else if (i pr) {T-rchild NULL;}}for (int i rl; i rr; i) {if (preOrder[i] T-key) {res1 false; break; //判断右子树序列中是否有非法值}}creatBiTree1(T-lchild, ll, lr);creatBiTree1(T-rchild, rl, rr);}else T NULL; return;
}void creatBiTree2(BiTree T, int pl, int pr) //镜像搜索树建立
{if (pl pr res2 true) {T (BiTree)malloc(sizeof(biTreeNode));int ll pl 1, rl pl 1, lr pr, rr pr;T-key preOrder[pl];for (int i pl 1; i pr; i) {if (preOrder[i] T-key) {ll i;break; //找到第一个比key大或相等的键值}else if (i pr) {T-lchild NULL;}}for (int i pl 1; i pr; i) {if (preOrder[i] T-key) {lr i - 1, rl i;break; //找到第一个比key小的键值}else if (i pr) {T-rchild NULL;}}for (int i rl; i rr; i) {if (preOrder[i] T-key) {res2 false; break; //判断右子树序列中是否有非法值}}creatBiTree2(T-lchild, ll, lr);creatBiTree2(T-rchild, rl, rr);}else T NULL;return;
}void postPrint(BiTree T) {if (T) {postPrint(T-lchild);postPrint(T-rchild);cout T-key; counts;if (counts n) cout ;else cout endl;}else return;
}int main()
{int temp; cin n;for (int i 0; i n; i) {cin temp; preOrder.push_back(temp);}BiTree head1, head2;creatBiTree1(head1, 0, n - 1);creatBiTree2(head2, 0, n - 1);if (res1) {cout YES endl;postPrint(head1);}else if (res2) {cout YES endl;postPrint(head2);}else cout NO endl;return 0;
} 二阶题完结撒花 如有问题欢迎提出。
