树型动态规划补充二叉树的遍历的相关知识：在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对全部结点逐一进行某种处理。
这就是二叉树的遍历问题。
所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点，而且每个结点仅被访问一次。
“访问”的含义很广，可以是对结点作各种处理，如输出结点的信息等。
遍历一般按照从左到右的顺序，共有3 种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。
先序遍历的操作定义如下：若二叉树为空，则空操作，否则①访问根结点②先序遍历左子树③先序遍历右子树先序遍历右图结果为：124753689中序遍历的操作定义如下：若二叉树为空，则空操作，否则①中序遍历左子树②访问根结点③中序遍历右子树中序遍历右图结果为：742513869后序遍历的操作定义如下：若二叉树为空，则空操作，否则①后序遍历左子树②后序遍历右子树③访问根结点后序遍历右图结果为：745289631满二叉树：一棵深度为h且有 2^h-1个结点的二叉树。
满二叉树一定为完全二叉树，但是完全二叉树不一定为满二叉树。
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
满二叉树有如下性质：如果一颗树深度为h，最大层数为k，且深度与最大层数相同，即k=h;1、它的叶子数是：2^(h-1)2、第k层的结点数是：2^(k-1)3、总结点数是：2^k-1 (2的k次方减一)4、总节点数一定是奇数。
若设二叉树的深度为h，除第h 层外，其它各层(1～h-1) 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边，这就是完全二叉树。
1、二叉树的序遍历题目描述Description求一棵二叉树的前序遍历，中序遍历和后序遍历输入描述Input Description第一行一个整数n，表示这棵树的节点个数。
接下来n行每行2个整数L和R。
第i行的两个整数Li和Ri代表编号为i的节点的左儿子编号和右儿子编号。
输出描述Output Description输出一共三行，分别为前序遍历，中序遍历和后序遍历。
编号之间用空格隔开。
样例输入Sample Input52 34 50 00 00 0样例输出Sample Output1 2 4 5 34 25 1 34 5 2 3 1#include<iostream>#include<cstdio>using namespace std;struct node{int l;int r;};int i,n,r,l;node tree[1000];printf("%d ",x);if (tree[x].l!=0) work1(tree[x].l);if (tree[x].r!=0) work1(tree[x].r);}void work2(int x){if (tree[x].l!=0) work2(tree[x].l);printf("%d ",x);if (tree[x].r!=0) work2(tree[x].r);}void work3(int x){if (tree[x].l!=0) work3(tree[x].l);if (tree[x].r!=0) work3(tree[x].r);printf("%d ",x);}int main(){scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d%d",&tree[i].l,&tree[i].r);work1(1);printf("\n");work2(1);printf("\n");work3(1);printf("\n");return 0;}2、二叉树最大宽度和高度（codevs1501）题目描述Description给出一个二叉树，输出它的最大宽度和高度。
输入描述Input Description第一行一个整数n。
下面n行每行有两个数，对于第i行的两个数，代表编号为i的节点所连接的两个左右儿子的编号。
如果没有某个儿子为空，则为0。
输出描述Output Description输出共一行，输出二叉树的最大宽度和高度，用一个空格隔开。
样例输入Sample Input52 34 50 00 00 0#include<iostream>#include<cstdio>#include<cstring>using namespace std;int a[1000][3],s[1000],i,n,x,ans;void dfs(int i, int k){int t,t1,t2;t=i;s[k]+=1;if (ans<s[k]) ans=s[k];if (k>x) x=k;t1=a[t][1];if (a[t][1]!=0) dfs(t1,k+1);t2=a[t][2];if (a[t][2]!=0) dfs(t2,k+1);}int main(){int n;memset(a, 0, sizeof(a));memset(s, 0, sizeof(s));scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d%d", &a[i][1], &a[i][2]);x=0;ans=0;dfs(1, 1);printf("%d %d\n", ans,x);return 0;}3、愚蠢的矿工(RQNOJ30)题目：背景Stupid 家族得知在HYC家的后花园里的中央花坛处,向北走3步,向西走3步,再向北走3步,向东走3步,再向北走6步,向东走3步,向南走12步,再向西走2步( - -||)就能找到宝藏的入口,而且宝藏都是藏在山里的,必须挖出来,于是Stupid家族派狗狗带领矿工队去挖宝藏.(HYC家的宝藏被狗狗挖走后有什么感想?)描述这个宝藏的制造者为了掩盖世人耳目,他做的宝藏是没有出口,只有入口,不少建造宝藏的人都死在里面.现在知道宝藏总共有N个分岔口,在分岔口处是有财宝的,每个宝藏点都有一个财富值.狗狗只带了M个人来,而且为了安全起见,在每个分岔口,必须至少留一个人下来,这个留下来的人可以挖宝藏(每个人只能挖一个地方的宝藏),这样才能保证不会迷路,而且这个迷宫有个特点,任意两点间有且只有一条路可通（这一句是关键，由此我们可以判断用二叉树来做）.狗狗为了让他的00开心,决定要尽可能地多挖些宝藏回去.现在狗狗的圈叉电脑不在身旁,只能求救于你了,你要知道,狗狗的终身幸福就在你手上了..（狗狗ps：00，你不能就这样抛弃偶……）输入——第1行：两个正整数N,M .N表示宝藏点的个数,M表示狗狗带去的人数(那是一条懒狗,他自己可不做事)。
(n<=1000,m<=100)第2行：N个整数,第i个整数表示第i个宝藏的财富值.(保证|wi|<maxint)第N+2行：两个非负整数A和B，表示A通向B,当A=0,表示A是入口.（保证A,B<=n）输出——输出狗狗能带回去的宝藏的价值。
样例：输入14 35 6 2 41 20 12 33 4输出113输入27 44 7 15 10 12 8 30 11 21 31 42 52 64 7输出2:38做法：这道题是一道树形dp，dp倒不是很难，只不过这里他的数据是一个多叉树，需要把多叉树变成二叉树，所以我悲剧地不会了，只好学习了......我先把多叉树转二叉树的示意图弄上来吧注：树形动态规划。
对于多叉树，我们一般采用多叉树转化为二叉树来简化问题即左儿子右兄弟，这也是dfs过程中为什么必须进行f[x,k]=f[r[x],k]。
f[x,y]=max(f[ 所有x结点的子树,分配i-1个人]+当前节点的宝藏财富值+f[ 剩余所有x结点的兄弟,分配y-i个人])；即方将f[x,y]:=f[tree[x].r,y-i] +tree[x].k+f[tree[x].l,i-1];参考程序:#include<cstdio>#define maxn 1010using namespace std;struct node{int l;int r;int k;}tree[maxn];int n,m,i,j,k,v[maxn],f[maxn][100];void dp(int x,int y){int i,tmp;if (f[x][y]!=-1) return;dp(tree[x].r,y);f[x][y]=f[tree[x].r][y];for(i=1;i<=y;i++){dp(tree[x].r,y);dp(tree[x].l,i-1);f[x][y]=max(f[x][y],f[tree[x].r][y-i]+f[tree[x].l][i-1]+tree[x].k);}}int main(){scanf("%d%d",&n,&m);for(i=1;i<=n;i++){tree[i].l=0;tree[i].r=0;}for(i=1;i<=n;i++) scanf("%d",&tree[i].k);for(i=1;i<=n;i++){scanf("%d%d",&j,&k);if(v[j]==0) tree[j].l=k;else tree[v[j]].r=k;v[j]=k;}for(i=1;i<=n;i++)for(j=1;j<=m;j++)f[i][j]=-1;dp(tree[0].l,m);printf("%d",f[tree[0].l][m]);return 0;5、购物问题（RQNOJ188）题目描述由于换季，商场推出优惠活动，以超低价格出售若干种商品。
但是商场为避免过分亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。
身为顾客的你想获得最大的实惠，也就是争取节省最多的钱。
经过仔细研究，我们发现商场出售的超低价商品中，不存在以下这种情况：n(n>=3)种商品C1，C2，C3，……，Cn，其中Ci和Ci+1是不能同时购买的（i=1,2,……,n-1），而且C1和Cn也不能同时购买。