[学科竞赛]树型动态规划

《[学科竞赛]树型动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树型动态规划补充二叉树的遍历的相关知识：在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对全部结点逐一进行某种处理。这就是二叉树的遍历问题。所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点，而且每个结点仅被访问一次。“访问”的含义很广，可以是对结点作各种处理，如输出结点的信息等。遍历一般按照从左到右的顺序，共有3种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。先序遍历的操作定义如下：若二叉树为空，则空操作，否则①访问根结点②先序遍历左子树③先序遍历右子树先序遍历右图结果为：124753689中序遍历的操作定义如下：若二叉

2、树为空，则空操作，否则①中序遍历左子树②访问根结点③中序遍历右子树中序遍历右图结果为：742513869后序遍历的操作定义如下：若二叉树为空，则空操作，否则①后序遍历左子树②后序遍历右子树③访问根结点后序遍历右图结果为：745289631满二叉树：一棵深度为h且有2^h-1个结点的二叉树。满二叉树一定为完全二叉树，但是完全二叉树不一定为满二叉树。若设二叉树的深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。满二叉树有如下性质：如果一颗树深度为h，最大层数为k，且深度与最大层数相同，

3、即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、求pascal中二叉树的前序遍历给你一棵二叉树Input输入第一行为该树中结点的个数n，第二行到第n＋1行分别为这n个结点的值（也代表序号），左子树和右子树，Output输出二叉树的中序遍历SampleInput5123245300400500SampleOut

4、put42513参考程序：constmax=100;vara:array[1..max,1..3]oflongint;i,j,n:longint;s:setof1..max;proceduretree(k:longint);beginifa[k,2]<>0thentree(a[k,2]);writeln(a[k,1]);ifa[k,3]<>0thentree(a[k,3]);end;beginreadln(n);s:=[1..n];fori:=1tondobeginreadln(a[i,1],a[i,2],a[i,3]);s:=s-[a[i,2],a[

5、i,3]];end;fori:=1tondoifiinsthenbreak;tree(i);end.2、愚蠢的矿工(RQNOJ30)题目：背景Stupid家族得知在HYC家的后花园里的中央花坛处,向北走3步,向西走3步,再向北走3步,向东走3步,再向北走6步,向东走3步,向南走12步,再向西走2步(--

6、

7、)就能找到宝藏的入口,而且宝藏都是藏在山里的,必须挖出来,于是Stupid家族派狗狗带领矿工队去挖宝藏.(HYC家的宝藏被狗狗挖走后有什么感想?)描述这个宝藏的制造者为了掩盖世人耳目,他做的宝藏是没有出口,只有入口,不少建造宝藏的人都死在里面.现在知

8、道宝藏总共有N个分岔口,在分岔口处是有财宝的,每个宝藏点都有一个财富值.狗狗只带了M个人来,而且为了安全起见,在每个分岔口,必须至少留一个人下来,这个留下来的人可以挖宝藏(每个人只能挖一个地方的宝藏),这样才能保证不会迷路,而且这个迷宫有个特点,任意两点间有且只有一条路可通（这一句是关键，由此我们可以判断用二叉树来做）.狗狗为了让他的00开心,决定要尽可能地多挖些宝藏回去.现在狗狗的圈叉电脑不在身旁,只能求救于你了,你要知道,狗狗的终身幸福就在你手上了..（狗狗ps：00，你不能就这样抛弃偶……）输入/输出格式：输入——第1行：两个正整数N,M.N表示

9、宝藏点的个数,M表示狗狗带去的人数(那是一条懒狗,他自己可不做事)。(n<=1000,m<=100)第2行：N个整数,第i个整数表示第i个宝藏的财富值.(保证

10、wi

11、

12、。对于多叉树，我们一般采用多叉树转化为二叉树来简化问题即左儿子右兄弟，这也是dfs过程中为什么