L2-004. 这是二叉搜索树吗?

IT/互联网 / 编程语言 养生小编 来源:互联网 114浏览 0评论

L2-004. 这是二叉搜索树吗?

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,

其左子树中所有结点的键值小于该结点的键值;其右子树中所有结点的键值大于等于该结点的键值;其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

 

输入格式:

输入的第一行给出正整数N(<=1000)。随后一行给出N个整数键值,其间以空格分隔。

 

输出格式:

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果,则首先在一行中输出“YES”,然后在下一行输出该树后序遍历的结果。数字间有1个空格,一行的首尾不得有多余空格。若答案是否,则输出“NO”。

 

输入样例1:

78 6 5 7 10 8 11

 

输出样例1:

YES5 7 6 8 11 10 8

 

输入样例2:

78 10 11 8 6 7 5

 

输出样例2:

YES11 8 10 7 5 6 8

 

输入样例3:

78 6 8 5 10 9 11

 

输出样例3:

NO

 

题解:

  水题,自己构建树,比较一下即可…………

 

代码 C++:

 1 #include <cstdio> 2 #include <cstring> 3 #define INF 0x7F7F7F7F 4 #define MX 1005 5 int tre[MX][3], t, rd[MX], opt[MX]; 6 void addPoint(int data){ 7     int now = 0, to; 8     while (tre[now][0] != INF){ 9         if (data < tre[now][0]) to = 1;10         else to = 2;11         if (tre[now][to] == INF) tre[now][to] = ++t;12         now = tre[now][to];13     }14     tre[now][0] = data;15 }16 17 void getPre(int now){18     opt[t++] = tre[now][0];19     if (tre[now][1] != INF) getPre(tre[now][1]);20     if (tre[now][2] != INF) getPre(tre[now][2]);21 }22 void getPreAnt(int now){23     opt[t++] = tre[now][0];24     if (tre[now][2] != INF) getPreAnt(tre[now][2]);25     if (tre[now][1] != INF) getPreAnt(tre[now][1]);26 }27 28 void getPst(int now){29     if (tre[now][1] != INF) getPst(tre[now][1]);30     if (tre[now][2] != INF) getPst(tre[now][2]);31     opt[t++] = tre[now][0];32 }33 void getPstAnt(int now){34     if (tre[now][2] != INF) getPstAnt(tre[now][2]);35     if (tre[now][1] != INF) getPstAnt(tre[now][1]);36     opt[t++] = tre[now][0];37 }38 39 int main() {40     int n, i;41     memset(tre, INF, sizeof tre);42     scanf("%d", &n);43     for (i = 0; i < n; ++i){ scanf("%d", rd + i); addPoint(rd[i]); }44     t = 0; getPre(0);45     if (memcmp(rd, opt, sizeof rd) == 0){46         puts("YES");47         t = 0; getPst(0);48         for (i = 0, --n; i <= n; ++i) printf("%d%c", opt[i], " n"[i == n]);49         return 0;50     }51     t = 0; getPreAnt(0);52     if (memcmp(rd, opt, sizeof rd) == 0){53         puts("YES");54         t = 0; getPstAnt(0);55         for (i = 0, --n; i <= n; ++i) printf("%d%c", opt[i], " n"[i == n]);56         return 0;57     }58     puts("NO");59     return 0;60 }

 

L2-004. 这是二叉搜索树吗?

原文:http://www.cnblogs.com/Simon-X/p/6623648.html