算法中递归树

Ⅰ 算法导论 4-3 递归式 T(n)=2T(n/2)+n/lgn的复杂度求解

     在阅读算法导论第四章的时候，求解一些递归式的复杂度时，遇到了一些问题，因此将思路分享一下。

     首先对于可以用主方法求解的形式，这里不再说明，符合主方法的三种情况只要套用公式即可得到正确答案。关于主方法使用递归树法进行证明，算法导论上已经解释的很详细，感兴趣可以参考一下散汪咐。

    在练习题 4.6-2 中提到了    ， 其中   ，要求证明主递归式的的解为  

    以   为例，很明显不符合主方法的条件，因为第三章讲到过  ，那么可以考虑使用递归树法，进行求解，然后再使用代入法进行数学归纳法的证明。

    首先递归树高度为  （书中  以2为底，而不是10），叶节点数量为  ，即数量为n，每个叶节点复杂度为  ，因此叶节点总的复杂度为 

    然后计算中间节点包括根陵雹节点的复杂度，每一层有   个子节点

    

    接下来计算等差数列之和即可

              

        

即   

总的复杂度 

     因此可以很清楚的看到，由于递归树的每层代价类似，最后结果多出来的   可以认为树的总层数进行累加的结果。

    下面使用代入法验证该结论，由于证明渐近上界与证明渐近下界的过程类似，因此只证明上界。

    设 

    则，

得证，其中 

    在思考题 4-3中 有类似   形式的递归式存在，其解为  ，有些解答认为是   实际上并不准确。

    同样这种形式也不符合主方法的条件，同样使用递归树法进行近似的求解，然后再使用代入法证明答案的正确性。

    在计算这个递归式需要使用一些调和级数的知识，在算冲纯法导论的附录A中有公式 A.7，调和级数求和的证明需要使用到积分的定理，这里就不赘述了。

    同样，首先计算叶节点的复杂度，同上 叶节点数量为  ，即每个叶节点复杂度为  ，总的复杂度为 

    接下来计算中间节点包括根节点的复杂度，同上，一共有  层，各层之和为

        

这里的累加项不再是一个等比数列，而是一个调和级数，即为

所以可以看出进行多出一次对数运算的原因在于分数的累加，因此总的复杂度 

同样，下面使用代入法证明结果的正确性，因为证明步骤类似，这里也只证明渐近上界为  , 设 ，所以有

下面证明  ，为了证明的简便，我们假设n为2的幂次，即  ，则

对于极限  ，那么有

于是，得证  

Ⅱ 先序遍历二叉树的递归算法怎样理解

二叉树的结点结构是:
1、根结点（存放结点数据）
2、左子树指针
3、右子树指计
对二叉树的遍历就是访问各个结点中根结点里存放的数据。例如：
如果结点A有左结点B，右结点C，记作A(B,C)，不同结点我用"\"隔开。那么有这样一个(BitTree)二叉树表A(B,C) \B（D,E)\E(F.G)\C(空,H)\H(I.空)， 自己画出来，不然我后面白讲了。
要想把所有的数据都访问到则必需按照一定的原则，即当前结点的下一个结点是哪个结点。
无论是先、中还是后序算法都是先将左结点视为下一个结点，当左结点不存在（即为空时）才将右结点视作下一个结点，如果右结点也不存在就返回当前结点的上层结点再向右访问，如此类推。
于是对二叉树的遍历问题就被抽象成三个基本步骤:
1、访问根结点。
2、访问该点的所有左子树。
3、访问该点的所有右子树。
先序遍历的策略是按123的步骤执行，中序是按213来，后序则是231,它们之间的不同只是“访问根结点”在这三个步骤中的位置。
看着你刚画好的那个BitTree跟着我的思路走。在先序遍历算法PriorOrder中,先将BitTree的头结点A传进来，按步骤123的处理。123是抽象实现，记住所表达的思想，下面是具体实现。为了避免混乱用中文数字记录步骤。
一、即是读取结点A的数据内容A（此时A为当前函数处理结点)，将A的右结点C放入栈S中，S中的内容为S（C）[注意这一步是算法的一个辅助，并不是先向右访问,下同]，将左结点B传给PriorOrder处理。此时读取了A
二、读取B的内容B（此时B为当前结点），将B的右结点E放入S中，S中的内容为S(C,E),将B的左结点D传给PriorOrder处理。此时读取了AB
三、D为当前结点，D的右为空没有东西放入S，S中的内容仍为S(C,E)，D的左也为空，没有访问可访问的。此时就从S中取出E(因为栈是先进后出的所以取的就是E，此时S中的内容为S(C),正好是上一层没访问过的右子树)，将E传给PriorOrder处理。此时读取了AB D
四、E为当前结点，对于结点E类似的有S(C,G),读取了ABDE,将F传入PriorOrder
五、F为当前结点，右为空，左也为空，读取了ABDEF,从栈中取出G传给PriorOrder处理,S的内容为S(C);
六、类似的读取了ABDEFG,从S中取出了C，传给PriorOrder处理。此时S（）。
七、当前结点为C，从将C的右结点放入S，S中内容为S(H),C的左为空，从S取出H，将H传给PriorOrder处理。此时S为S().于是就读取了ABDEFGC
八，类似的读取了ABDEFGCH
九，最后ABDEFGCHF
你再对照的书上的算法想想，画画就应该能明白点。特别要理角的一点是为什么用递归算法时计算机能按这样的方式是因为函数调用是“先调用，后执行完”，或者说“后调用，先执行完”。注意我加一个“完”字