辽宁建设执业继续教育协会网站,2003 您的安全设置不允许网站使用安装,优秀的展厅设计网站,wordpress建设QQ登录这是一道面试题#xff0c;可以说是数据结构中的基础题了#xff0c;由先序遍历以及中序遍历生成一棵树#xff0c;然后输出后序遍历。 一个递归函数传递5个参数#xff0c;顶点编号#xff0c;先序左右区间#xff0c;中序左右区间#xff0c;每次进行区间长度判定可以说是数据结构中的基础题了由先序遍历以及中序遍历生成一棵树然后输出后序遍历。 一个递归函数传递5个参数顶点编号先序左右区间中序左右区间每次进行区间长度判定当只有一个元素就进行元素判定递归构树。 代码如下 #include cstdlib
#include cstdio
#include cstring
#include algorithm
#include iostream
#define MAXN 1005
using namespace std;int N, p[MAXN], m[MAXN], idx;struct Node
{int l, r, val;
}e[MAXN];int init()
{idx;e[idx].l e[idx].r 0;return idx;
}bool build(int rt, int l, int r, int ll, int rr)
{ // l, r 表示先序的区间ll, rr表示中序的区间 int pos -1;e[rt].val p[l]; // 先序确定根节点if (r - l ! rr - ll) return false;if (l r) {if (p[l] m[ll]) return true;else return false;}for (int i ll; i rr; i) { // 中序寻根 if (m[i] p[l]) {pos i;break;}}if (pos -1) return false;if (pos ll) { // 没有左孩子e[rt].r init();return build(e[rt].r, l1, r, ll1, rr);}else if (pos rr) { // 没有右孩子 e[rt].l init();return build(e[rt].l, l1, r, ll, rr-1);}else {int a, b;e[rt].l init();a build(e[rt].l, l1, l(pos-ll), ll, pos-1);e[rt].r init();b build(e[rt].r, l(pos-ll)1, r, pos1, rr);return a b;}
}void print(int p)
{if (e[p].l) {print(e[p].l); }if (e[p].r) {print(e[p].r); }printf(%d , e[p].val);
}int main()
{int rt;while (scanf(%d, N) 1) {idx -1;rt init();for (int i 1; i N; i) {scanf(%d, p[i]);}for (int i 1; i N; i) {scanf(%d, m[i]);}if (build(rt, 1, N, 1, N)) {print(rt);puts();}else puts(No);}return 0;
} 转载于:https://www.cnblogs.com/Lyush/archive/2012/08/24/2653573.html
