数据结构与算法(Python语言描述)课件DS_051_树的递归遍历

2020/5/28,中国海洋大学数学科学学院,1,二叉树的递归遍历,2016Fall数据结构,2020/5/28,二叉树的存储表示,空树：None非空树：data,left,right,方式1：list,2020/5/28,中国海洋大学数学科学学院,3,递归的终结状态,2020/5/28,tree=*,3,None,None,+,5,None,None,7,None,None,例：,空树：None非空树：若结点的左右子树均为空，则为data否则：data,left,right,方式1：简化的list,2020/5/28,中国海洋大学数学科学学院,5,也是递归的终结状态,2020/5/28,tree=*,3,+,5,7,例：简化的list,2020/5/28,list表示是利用了Python的list可以含有不同类型的元素，将树表示成长度为3的表，其中最后两个元素仍是表，即表的表，形成层次结构；由于list是一个一般意义下的表，其实现本身有一定的复杂性，所以这种表示的效率不如自定义的二叉链表。,说明,classBinTNode:def_init_(self,data,left=None,right=None):self.data=dataself.left=leftself.right=right,方式2：二叉链表,2020/5/28,2020/5/28,root=BinTNode(*,BinTNode(3,None,None),BinTNode(+,BinTNode(5,None,None),BinTNode(7,None,None),例：,2020/5/28,root=BinTNode(*,BinTNode(3),BinTNode(+,BinTNode(5),BinTNode(7),例：利用默认参数值，可简化一点！,2020/5/28,中国海洋大学数学科学学院,12,三叉链表,2020/5/28,中国海洋大学数学科学学院,13,二叉链表和三叉链表,2020/5/28,三叉链表相当于线性表中的“双向”链表，方便由孩子找到双亲。,说明,二叉树的递归遍历,2020/5/28,15,中国海洋大学数学科学学院,按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。可能的三种遍历次序：先序：vLR中序：LvR后序：LRv,二叉树的遍历,2020/5/28,16,中国海洋大学数学科学学院,2020/5/28,中国海洋大学数学科学学院,17,递归的终结条件：盒子是“空”！,二叉树的递归结构,Traverse(树T)if(T是空树)return！else访问根结点;/先序！Traverse(T的左子树);Traverse(T的右子树);return,二叉树的递归遍历模板,2020/5/28,18,中国海洋大学数学科学学院,若二叉树为空，则空操作；否则：访问根结点(v)；先序遍历左子树(L)；先序遍历右子树(R)。,先序遍历(PreorderTraversal),2020/5/28,19,中国海洋大学数学科学学院,先序：-+a*b-cd/ef,遍历序列,2020/5/28,20,中国海洋大学数学科学学院,defpreorder(tree):iftree!=None:print(tree0,end=)#对根的访问preorder(tree1)preorder(tree2),递归的先序遍历算法基于list表示,2020/5/28,21,中国海洋大学数学科学学院,defpreorder(root):ifroot!=None:print(root.data,end=)#对根的访问preorder(root.left)preorder(root.right),递归的先序遍历算法基于二叉链表表示,2020/5/28,22,中国海洋大学数学科学学院,若二叉树为空，则空操作；否则：中序遍历左子树(L)；访问根结点(v)；中序遍历右子树(R)。,中序遍历(InorderTraversal),2020/5/28,23,中国海洋大学数学科学学院,中序：a+b*c-d-e/f后序：abcd-*+ef/-,遍历序列,2020/5/28,24,中国海洋大学数学科学学院,definorder(root):ifroot!=None:inorder(root.left)print(root.data,end=)#对根的访问inorder(root.right),递归的中序遍历算法基于二叉链表表示,2020/5/28,25,中国海洋大学数学科学学院,deforder(树T):iftree!=None:order(T的左子树);order(T的右子树);,第一次到达T时visit,由左子树返回T时visit,由右子树返回T时visit,三种遍历的递归模板相同，访问时机不同！,2020/5/28,26,中国海洋大学数学科学学院,2020/5/28,中国海洋大学数学科学学院,27,递归的执行过程是相同的！,基于遍历的递归算法,2020/5/28,28,中国海洋大学数学科学学院,defcount(root):ifroot=None:return0else:n1=count(root.left)n2=count(root.right)n=1+n1+n2;returnn,例1：基于后序遍历计算结点总数,2020/5/28,29,中国海洋大学数学科学学院,defnum(root):ifroot=None:return0else:return1+num(root.left)+num(root.right),简写明白这里是后序遍历模板,2020/5/28,30,中国海洋大学数学科学学院,defheight(root):ifroot=None:return-1else:return1+max(height(root.left),height(root.right)/注意：层次从0编号时，空树深度为-1!,例2：基于后序遍历计算高度,2020/5/28,31,中国海洋大学数学科学学院,二叉树的建立,2020/5/28,32,中国海洋大学数学科学学院,先序序列：ABHFDECKG中序序列：HBDFAEKCG,由先序和中序序列可唯一确定一棵二叉树！,2020/5/28,33,中国海洋大学数学科学学院,先序序列：ABHFDECKG中序序列：HBDFAEKCG,由先序和中序序列可唯一确定一棵二叉树！,2020/5/28,34,中国海洋大学数学科学学院,2020/5/28,35,中国海洋大学数学科学学院,defcreateTreeBy2Orders(preorderList,p1,p2,inorderList,i1,i2):ifp1=p2:returnNonedata=preorderListp1k=inorderList.index(data,i1,i2)-i1root=BinTNode(data)root.left=createTreeBy2Orders(preorderList,p1+1,p1+k+1,inorderList,i1,i1+k)root.right=createTreeBy2Orders(preorderList,p1+k+1,p2,inorderList,i1+k+1,i2)returnroot,由先序和中序序列建立二叉树,2020/5/28,中国海洋大学数学科学学院,36,先序序列：ABDEC先序扩展序列：AB#DE#C#,先序“扩展”序列,2020/5/28,37,中国海洋大学数学科学学院,defTreeToExtendedPreorder(root,lst):ifroot=None:lst.append(#)else:lst.append(root.data)TreeToExtendedPreorder(root.left,lst)TreeToExtendedPreorder(root.right,lst),将二叉树输出为先序扩展序列,2020/5/28,38,中国海洋大学数学科学学院,defcreateTreeByExtendedPreorder(lst,i):由lst的i位置开始读入先序遍历序列，返回建立的二叉树，以及lst的下一个读入位置iflsti=#:returnN