二叉树的遍历和应用

《二叉树的遍历和应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二叉树的遍历和应用数据结构与算法1预备知识—递归2什么是递归？递归是极强大的问题解决技术。当一个函数用它自己来定义时就是递归。递归将一个复杂问题分解为一些更小的问题。3举例：查词典顺序查找：可以从词典第一页开始，按顺序查找每个单词，直到找到。递归解决方案：分而治之的策略；把问题划分成小问题，直到到达基例。查找词典查找词典的前半部分查找词典的后半部分4递归解决方案的一般形式怎样按同类型的更小的问题来定义问题各个递归调用怎么减小问题规模哪个问题实例可用做基例随着问题规模的减小，最终能否到达基例5举例1：n的阶乘publicstaticintfact(int

2、n){//computethefactorialofanonnegativeinteger//precondition:nmustbegreaterthanorequalto0//postcondition:returnsthefactorialofn//-----------------------if(n==0){return1;}Else{returnn*fact(n-1);}//endif}//endfact6举例2：逆置字符串减小规模：去掉最后一个字符writeBackward(s){if(thestringsisempty){donothi

3、ng–thisisthebasecase}Else{WritethelastcharacterofswriteBackward(sminusitslastcharacter)}//endif}//end减小规模：去掉第一个字符writeBackward2(s){if(thestringsisempty){donothing–thisisthebasecase}Else{writeBackward2(sminusitsfirstcharacter)Writethefirstcharacterofs}//endif}//end7举例3：Hanoi塔solv

4、eTowers(count,source,destination,spare){if(countis1){Moveadiskdirectlyfromsourcetodestination;}Else{sloveTowers(count-1,source,spare,destination)sloveTowers(1,source,destination,spare)sloveTowers(count-1,spare,destination,source)}//endif}//end8举例4：兔子繁殖(递归法)publicstaticintrabbit(

5、intn){if(n<=2){return1;}Else{returnrabbit(n-1)+rabbit(n-2);}//endif}//endrabbit(n)=1n=1或n＝2rabbit(n-1)+rabbit(n-2)n>29举例4：兔子繁殖(迭代法)publicstaticintiterativeRabbit(intn){//iterativesolutiontotherabbitproblem//initializebasecases:intprevious=1;//rabbit(1)intcurrent=1;//rabbit(2)int

6、next=1;//resultwhennis1or2//computernextrabbitvalueswhenn>=3for(inti=3;i<=n;i++){next=current+previous;previous=current;current=next;}//endforreturnnext;}//end10二叉树的遍历11一、问题的提出二、遍历算法三、算法的递归描述四、遍历算法的应用举例12顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。问题的提出“访问”的含义可以很广，如：输出结点的信息等。13“遍历”

7、是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。14层次遍历首先创建一个队列；若二叉树非空，将根放入队列；从队列取出一个元素并访问，如果该元素有左孩子就将它放入队列，如果该元素有右孩子就将它放入队列；若队列非空，继续第2步，直至队列为空，则二叉树的层次遍历过程结束。例如,图5.1中的二叉树按照层次遍历的结果为:ABCDEFGHI15前序周游(preordertraversal)若二叉树非空,则依次进行如下操作:

8、(1)访问根结点;(2)前序周游左子树;(3)前序周游右子树。前序遍历二叉树(preorder