首页 > 代码库 > UVa 548 (二叉树的递归遍历) Tree
UVa 548 (二叉树的递归遍历) Tree
题意：
给出一棵由中序遍历和后序遍历确定的点带权的二叉树。然后找出一个根节点到叶子节点权值之和最小(如果相等选叶子节点权值最小的)，输出最佳方案的叶子节点的权值。
二叉树有三种递归的遍历方式：
- 先序遍历，先父节点 然后左孩子 最后右孩子
- 中序遍历，先左孩子 然后父节点 最后父节点
- 后序遍历，先左孩子 然后右孩子 最后父节点
这里有更详细的解释：
http://blog.csdn.net/sicofield/article/details/9066987
紫书上面写错了，后序遍历最后一个元素才是根节点。确定根节点以后，我们再根据这个值在中序遍历的序列中找到他。然后以根节点为界，左边的元素是左子树的元素，右边的元素是右子树的元素。再进行递归。
关于中序遍历和后序遍历的关系，这里写的很具体：
http://blog.csdn.net/frankiller/article/details/7759871
因为权值各不相同，所以用权值的大小来作为节点编号。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <string> 5 #include <sstream> 6 #include <algorithm> 7 using namespace std; 8 9 const int maxv = 10000 + 10;10 int in_order[maxv], post_order[maxv], lch[maxv], rch[maxv];11 int n;12 13 bool read_list(int* a)14 {15 string line;16 if(!getline(cin, line)) return false;17 stringstream ss(line);18 n = 0;19 int x;20 while(ss >> x) a[n++] = x;21 return n > 0;22 }23 24 int build(int L1, int R1, int L2, int R2)25 {26 if(L1 > R1) return 0;27 int root = post_order[R2];28 int p = L1;29 while(in_order[p] != root) p++;30 int cnt = p - L1; //左子树节点的个数31 lch[root] = build(L1, p - 1, L2, L2 + cnt - 1);32 rch[root] = build(p + 1, R1, L2 + cnt, R2 - 1);33 return root;34 }35 36 int best, best_sum;37 38 void DFS(int u, int sum)39 {40 sum += u;41 if(!lch[u] && !rch[u])42 {//叶子43 if(sum < best_sum || (sum == best_sum && u < best))44 {45 best = u;46 best_sum = sum;47 }48 }49 if(lch[u]) DFS(lch[u], sum);50 if(rch[u]) DFS(rch[u], sum);51 }52 53 int main(void)54 {55 #ifdef LOCAL56 freopen("548in.txt", "r", stdin);57 #endif58 59 while(read_list(in_order))60 {61 read_list(post_order);62 build(0, n-1, 0, n-1);63 best_sum = 1000000000;64 DFS(post_order[n-1], 0);65 printf("%d\n", best);66 }67 68 return 0;69 }
UVa 548 (二叉树的递归遍历) Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。