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

二叉树的递归遍历2016Fall《数据结构》2020/5/241中国海洋大学数学科学学院二叉树的存储表示2020/5/24空树：None非空树：[data,left,right]方式1：list2020/5/24中国海洋大学数学科学学院3leftdataright递归的终结状态tree=[‘*’,[3,None,None],[‘+’,[5,None,None],[7,None,None]]]例：2020/5/24*3+57空树：None非空树：若结点的左右子树均为空，则为data否则：[data,left,right]方式1’：简化的list2020/5/24中国海洋大学数学科学学院5leftdataright也是递归的终结状态tree=[‘*’,3,[‘+’,5,7]]例：简化的list2020/5/24*3+57list表示是利用了Python的list可以含有不同类型的元素，将树表示成长度为3的表，其中最后两个元素仍是表，即表的表，形成层次结构；由于list是一个一般意义下的表，其实现本身有一定的复杂性，所以这种表示的效率不如自定义的二叉链表。说明2020/5/24classBinTNode:def__init__(self,data,left=None,right=None):self.data=dataself.left=leftself.right=right方式2：二叉链表leftdataright2020/5/24*^3^+^5^^7^*3+57root=BinTNode(‘*’,BinTNode(3,None,None),BinTNode(‘+’,BinTNode(5,None,None),BinTNode(7,None,None)))例：2020/5/24*3+57root=BinTNode(‘*’,BinTNode(3),BinTNode(‘+’,BinTNode(5),BinTNode(7)))例：利用默认参数值，可简化一点！2020/5/24*3+57三叉链表2020/5/2412中国海洋大学数学科学学院leftdataparentrightleftdataparentrightAAABBBCCCDDDFFFEEErootrootroot二叉链表和三叉链表2020/5/2413中国海洋大学数学科学学院三叉链表相当于线性表中的“双向”链表，方便由孩子找到双亲。说明2020/5/24二叉树的递归遍历2020/5/2415中国海洋大学数学科学学院按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。可能的三种遍历次序：先序：vLR中序：LvR后序：LRv二叉树的遍历vLR2020/5/2416中国海洋大学数学科学学院vLR递归的终结条件：盒子是“空”！二叉树的递归结构vLR2020/5/2417中国海洋大学数学科学学院Traverse(树T){if(T是空树)return！！！else访问根结点;//先序！Traverse(T的左子树);Traverse(T的右子树);return}二叉树的递归遍历模板vLR2020/5/2418中国海洋大学数学科学学院若二叉树为空，则空操作；否则：访问根结点(v)；先序遍历左子树(L)；先序遍历右子树(R)。先序遍历(PreorderTraversal)2020/5/2419中国海洋大学数学科学学院先序：-+a*b-cd/ef遍历序列--/+*abcdef2020/5/2420中国海洋大学数学科学学院defpreorder(tree):iftree!=None:print(tree[0],end='')#对根的访问preorder(tree[1])preorder(tree[2])递归的先序遍历算法——基于list表示2020/5/2421中国海洋大学数学科学学院defpreorder(root):ifroot!=None:print(root.data,end=‘’)#对根的访问preorder(root.left)preorder(root.right)递归的先序遍历算法——基于二叉链表表示2020/5/2422中国海洋大学数学科学学院若二叉树为空，则空操作；否则：中序遍历左子树(L)；访问根结点(v)；中序遍历右子树(R)。中序遍历(InorderTraversal)2020/5/2423中国海洋大学数学科学学院中序：a+b*c-d-e/f后序：abcd-*+ef/-遍历序列--/+*abcdef2020/5/2424中国海洋大学数学科学学院definorder(root):ifroot!=None:inorder(root.left)print(root.data,end=‘’)#对根的访问inorder(root.right)递归的中序遍历算法——基于二叉链表表示2020/5/2425中国海洋大学数学科学学院deforder(树T):iftree!=None:order(T的左子树);order(T的右子树);}}第一次到达T时visit由左子树返回T时visit由右子树返回T时visit三种遍历的递归模板相同，访问时机不同！2020/5/2426中国海洋大学数学科学学院-/+baef递归的执行过程是相同的！！！2020/5/2427中国海洋大学数学科学学院基于遍历的递归算法2020/5/2428中国海洋大学数学科学学院defcount(root):ifroot==None:return0else:n1=count(root.left)n2=count(root.right)n=1+n1+n2;returnn例1：基于后序遍历计算结点总数vLR2020/5/2429中国海洋大学数学科学学院defnum(root):ifroot==None:return0else:return1+num(root.left)+num(root.right)简写——明白这里是后序遍历模板2020/5/2430中国海洋大学数学科学学院defheight(root):ifroot==None:return-1else:return1+max(height(root.left),height(root.right))//注意：层次从0编号时，空树深度为-1!例2：基于后序遍历计算高度vLR2020/5/2431中国海洋大学数学科学学院二叉树的建立2020/5/2432中国海洋大学数学科学学院先序序列：ABHFDECKG中序序列：HBDFAEKCG由先序和中序序列可唯一确定一棵二叉树！HBDFEKCGAEKCGABHDFEKCGABHDF2020/5/2433中国海洋大学数学科学学院先序序列：ABHFDECKG中序序列：HBDFAEKCG由先序和中序序列可唯一确定一棵二叉树！EKCGABHFDKCGEABHFDEABHFDCKG2020/5/2434中国海洋大学数学科学学院根根左子树结点右子树结点左子树结点右子树结点k个结点p1p1+1p1+k+1p2i1i1+ki1+k+1i2中：先：2020/5/2435中国海洋大学数学科学学院defcreateTreeBy2Orders(preorderList,p1,p2,inorderList,i1,i2):ifp1=p2:returnNonedata=preorderList[p1]k=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/24中国海洋大学数学科学学院36先序序列：ABDEC先序扩展序列：AB#DE###C##先序“扩展”序列CABED2020/5/2437中国海洋大学数学科学学院defTreeToExtendedPreorder(root,lst):ifroot==None:lst.append(‘#')else:lst.append(root.data)TreeToExtendedPreorder(root.left,lst)TreeToExtendedPreorder(root.right,lst)将二叉树输出为先序扩展序列2020/5/2438中国海洋大学数学科学学院defcreateTreeByExtendedPreorder(lst,i):‘‘’由lst的i位置开始读入先序遍历序列，返回建立的二叉树，以及lst的下一个读入位置'''iflst[i]==‘#':returnNone,i+1root=BinTNode(lst[i])root.left,j1=createTreeByExtendedPreorder(lst,i+1)root.right,j2=createTreeByExtendedPreorder(lst,j1)returnroot,j2由先序的扩展序列建立二叉树2020/5/2439中国海洋大学数学科学学院