二叉树的遍历深入学习资料

1、6.3.1二叉树遍历的非递归算法，1 .第一个顺序导航的非递归算法，2 .中间顺序导航的非递归算法，3 .下一个顺序导航的非递归算法，1 .第一个顺序导航的非递归算法，(1)二叉树的根节点堆栈。(2)当堆栈不为空时：在堆栈顶部元素不为空时访问堆栈，并将节点左侧子树的根节点放入堆栈，直到堆栈顶部元素为空。如果堆栈不为空，堆栈中的顶级元素将从堆栈中出来，该节点右侧子树的根节点将进入堆栈。执行此操作，直到堆栈为空。void preorder _ non recursive(bitreet)/非递归算法InitStack(S)，Push(S，T)；/根指针位于堆栈while(！stack empty(

2、s)while(gettop(s)printf(% c，gettop(s)-data)；/访问节点，向左推一级(S，GetTop(S)-lchild)；/向左结束Pop(S，p)；/空指针堆栈if(！stack empty(S)Pop(S，p)；Push(S，p-rchild)；/向右一级/while/preorder _ non recursive，2 .中间顺序遍历的非递归算法，(1)二叉树的根节点堆栈。(2)当堆栈不为空时：当堆栈顶部元素不为空时，将该节点左侧子树的根节点放入堆栈，直到堆栈顶部元素为空，然后将空指针移出堆栈。如果堆栈不为空，则堆栈顶部元素将离开堆栈，访问其元素以堆栈节点右

3、侧子树的根节点。执行此操作，直到堆栈为空。void in order _ non recursive(bitreet)/中按顺序循环的非递归算法init stack(S)；Push(S，T)；/根指针位于堆栈while(！stack empty(s)while(gettop(s)push(s，gettop(s)-lchild)；/向左结束Pop(S，p)；/空指针堆栈if(！stack empty(S)/访问节点，向右一级Pop(S，p)；Printf(%c，p-data)；Push(S，p-rchild)；/if/while/inorder _ non recursive，3 .与反向导航的

4、非递归算法不同，在通过二进制树的过程中，一个节点在被访问之前必须经过两次。该节点查找左侧子树，遍历左侧子树，完成遍历后返回到该节点。第二种方法是在节点上找到右侧子树，然后导航到右侧子树，完成遍历后返回到该节点，这样才能访问节点。因此回溯非递归算法也需要堆栈，必须在堆栈结构中设置标志字段以区分节点是第一个堆栈还是第二个堆栈。堆栈节点定义为typedefstructPMTypeBiTreeptr。Intmark/mark=0表示刚刚访问此节点，mark=1表示结束返回左侧子树处理，mark=2表示结束返回右侧子树处理。PMType，6.3.2分层遍历算法，分层遍历过程将根节点入队，并在队列不为空时

5、循环。也就是说，从队列中获取元素并对其进行访问。如果有左侧ii节点，请将左侧ii节点入队。如果右侧的ii节点存在，请将右侧ii节点入队。执行此操作，直到队列为空。voidayerorder (bitreet)/序列遍历二叉树init queue(Q)；/初始化队列EnQueue(Q，T)；/根节点位于while(！queue empty(Q)DeQueue(Q，p)；Printf(，p-data)；If(p-lchild)EnQueue(Q，p-lchild)；If(p-rchild)EnQueue(Q，p-rchild)；/LayerOrder，4，查询二进制树的节点，6.3.3遍历算法应用

6、程序示例，1，统计二进制树的叶节点数，2，查找二进制树的深度，3，复制二进制树，5，设置二进制树存储结构，1，统计二进制树的叶因此，如果在遍历算法中添加参数“count”，并将算法中的操作“access node”更改为：则计数器将增加1。voidcountleaf (bitreet，int/if/countleaf，return，2)，查找二进制树的深度，算法基本思想：从二进制树深度的定义来看，二进制树的深度为左侧和右侧子树深度的最大值1因此，首先求出左右子树的深度，算法中的“访问节点”操作为：求出左右子树深度的最大值，然后加上1。首先分析二叉树的深度与左右子树深度的关系。，(回溯)，int

7、Depth(BiTreeT)/二进制树的深度if(！t)depth val=0；elsedeplthleft=depth(t-lchild)；dept hright=Depth(T-rchild)；Depthval=1 (depthLeftdepthRight？depthleft : depthright)；Returndepthval将二进制树复制到为、Return、3和：创建节点的基本操作。根元素，t，左侧子树，右侧子树，NEWT，左侧子树，右侧子树，左侧子树，右侧子树，(向后遍历)，bitnode(T=new bitnode)exit(1)；t-data=item；t-lchild=lp

8、tr；t-rchild=rptr；ReturnT数据字段item、左指针字段lptr、右指针字段rptr、bitnode *复制树if(！t)return null；if(t-lchild)newl ptr=copy tree(t-lchild)；/复制左侧子树elsenewlptr=NULLif(t-rchild)newr ptr=copy tree(t-rchild)；/复制右侧子树elsenewrptr=NULLNewt=gettreenode (t-data，newl ptr，newr ptr)；ReturnnewT/CopyTree(例如，以下二进制树的复制过程为：newt，retu

9、rn，4，二进制树的节点之一，算法基本思路33333返回。(2)否则，在左侧子树中查找，如果找到，则为TRUE返回。(3)否则，在右侧子树中继续查找，如果找到，则返回TRUE，否则返回FALSE。int preorder (bitreet，elemtype x，bitreereturnok，/ifelsep=null；ReturnFALSE，else if (preorder (t-lchild，x，p)return ok；/else，else return (preorder (t-rchild，x，p)；Return，5，设置二进制树的存储结构，在遍历期间创建节点，设置二进制树的存储结构。

10、下面给出的算法是将二进制树的二进制列表设置为第一顺序的过程。对于图6-5(1)所示的二进制树，按以下顺序读取AB#C#D#EF#(#是空格字符)字符以创建相应的二进制链接表：intcreate bitree(bi tree/create bitree，return，6.3.4二进制树的配置，假定二进制树中每个节点的值都不相同(以下算法基于此假设)，同一二进制树具有唯一的第一个、中间和最后一个顺序，但每个二进制树具有相同的顺序使用数学推导，可以证明以下两个结论成立：(1) n(n0)个其他节点的二进制树在相应的顺序序列和中间顺序序列中唯一确定。(2) n(n0)个不同节点的二进制树可以由中间序列和后序列唯一地确定。仅知道二进制树的第一个顺序“abcdefg”，无法唯一确定由二进制树的第一个顺序和中间顺序序列组成的二进制树。如果还知道二进制树的中间顺序“cbdaegf”，会发生什么情况？二进制树的第一个顺序，中间顺序，左侧子树，左侧子树，右侧子