想遍历,先建树! 树可以用结构体来存,一个左大儿,一个右大儿 struct node { int l, r; } Tree[N]; 而且只有满足以下两种情况才能建树 ①知道前序和中序 例题:https:///problem/HRBUST-2040 int build(int l1, int r1, int l2, int r2) { //l1 r1是中序遍历的边界,l2 r2是前序遍历的边界 if (l1 > r1) //非法情况 return 0; int root = pre[l2]; //前序遍历的第一个值位根节点 int p1 = l1; while (in[p1] != root) //遍历中序遍历找根节点位置 p1; int p2 = p1 - l1 l2; //将根树分为左儿子和右儿子 Tree[root].l = build(l1, p1 - 1, l2 1, p2); Tree[root].r = build(p1 1, r1, p2 1, r2); return root; } ②知道后序和中序 例题:https:///problem-sets/994805046380707840/problems/994805069361299456 将根节点变为后序遍历的最后一个,其他不变即可~ int build(int l1, int r1, int l2, int r2) { //l1 r1是中序遍历的边界,l2 r2是后序遍历的边界 if (l1 > r1) //非法情况 return 0; int root = pos[r2]; //后序遍历的最后一个值为根节点 int p1 = l1; while (in[p1] != root) //遍历中序遍历找根节点位置 p1; int p2 = p1 - l1 l2; //将根树分为左儿子和右儿子 Tree[root].l = build(l1, p1 - 1, l2, p2 - 1); Tree[root].r = build(p1 1, r1, p2, r2 - 1); return root; } 可以看出两种情况基本上没啥区别,最后输出就行了 ①前序遍历 根左右 void getpos(int x) { printf("%d ", x); if (Tree[x].l != 0) getpos(Tree[x].l); if (Tree[x].r != 0) getpos(Tree[x].r); } ②中序遍历 左根右 void getpos(int x) { if (Tree[x].l != 0) getpos(Tree[x].l); printf("%d ", x); if (Tree[x].r != 0) getpos(Tree[x].r); } ③后序遍历 左右根 void getpos(int x) { if (Tree[x].l != 0) getpos(Tree[x].l); if (Tree[x].r != 0) getpos(Tree[x].r); printf("%d ", x); } 这仨没啥区别,就是输出位置不一样 void bfs(int x) { queue<int> q; q.push(x); while (q.size()) { int t = q.front(); q.pop(); if (Tree[t].l != 0) q.push(Tree[t].l); if (Tree[t].r != 0) q.push(Tree[t].r); if (t != x) printf(" "); printf("%d", t); } } 可能之后还会补充? ε=(´ο`*)))唉 tnl |
|