[feiq]DS_060_树的递归遍历

第五章二叉树2016Fall《数据结构》2020/4/281中国海洋大学数学科学学院结点、结点的度、树的度、叶结点、孩子、双亲、兄弟、祖先、子孙、结点层次、树的深度0层1层3层2层Depth=3ACGBDEFKLHMIJ概念2020/4/282中国海洋大学数学科学学院叶结点：度是零的结点结点的度：结点的孩子总数树的度：结点的度的最大值2020/4/28概念一棵二叉树是结点的有限集合：或者为空，或者由：根结点+左子树+右子树组成。二叉树(BinaryTree)LRLR2020/4/284中国海洋大学数学科学学院二叉树的性质2020/4/285中国海洋大学数学科学学院性质1：第i层最多有2i个结点。(i0)数学归纳法！2020/4/286中国海洋大学数学科学学院性质2：深度为h的二叉树最多有2h-1个结点。(h0)20+21+22+…+2h=2h+1-12020/4/287中国海洋大学数学科学学院性质3：设叶结点有n0个，度为2的结点有n2个,则有n0＝n2＋1顶点总数：n=n0+n1+n2总边数：e=2n2+n1=n-1因此：2n2+n1=n0+n1+n2-1推出：n0=n2+12020/4/288中国海洋大学数学科学学院定义1：满二叉树(FullBinaryTree)定义2：完全二叉树(CompleteBinaryTree)2020/4/289中国海洋大学数学科学学院性质4：含n个结点的完全二叉树的深度为：log2n设完全二叉树的深度为h，则有：2hn2h+1取对数：hlog2nh+1则有：h=log2n2020/4/2810中国海洋大学数学科学学院深度定义为结点的最大层数层数由零开始计！性质4’：含n个结点的完全二叉树的深度为：log2(n+1)-1设完全二叉树的深度为h，则有：2h-1n2h+1-1变形：2hn+12h+1取对数：hlog2(n+1)h+1则有：log2(n+1)=h+12020/4/2811中国海洋大学数学科学学院深度定义为结点的最大层数层数由零开始计！性质5：对完全二叉树的结点自顶向下、同一层自左向右连续编号：0,1,2,…,n-1，则：若2*i+1n，则i的左子女为2*i+1若2*i+2n，则i的右子女为2*i+2若i=0，则i无双亲若i0，则i的双亲为(i-1)/201237456892020/4/2812中国海洋大学数学科学学院由性质5：完全二叉树适合顺序存储！00123456789137894562901234567890125436782020/4/2813中国海洋大学数学科学学院空树：None非空树：[data,left,right]方式1：list2020/4/28中国海洋大学数学科学学院14leftdataright递归的终结状态tree=[‘*’,[3,None,None],[‘+’,[5,None,None],[7,None,None]]]例：2020/4/28*3+57空树：None非空树：若结点的左右子树均为空，则为data否则：[data,left,right]方式1’：简化的list2020/4/28中国海洋大学数学科学学院16leftdataright也是递归的终结状态tree=[‘*’,3,[‘+’,5,7]]例：简化的list2020/4/28*3+57list表示是利用了Python的list可以含有不同类型的元素，将树表示成长度为3的表，其中最后两个元素仍是表，即表的表，形成层次结构；由于list是一个一般意义下的表，其实现本身有一定的复杂性，所以这种表示的效率不如自定义的二叉链表。说明2020/4/28classBinTNode:def__init__(self,data,left=None,right=None):self.data=dataself.left=leftself.right=right方式2：二叉链表leftdataright2020/4/28*^3^+^5^^7^*3+57root=BinTNode(‘*’,BinTNode(3,None,None),BinTNode(‘+’,BinTNode(5,None,None),BinTNode(7,None,None)))例：2020/4/28*3+57root=BinTNode(‘*’,BinTNode(3),BinTNode(‘+’,BinTNode(5),BinTNode(7)))例：利用默认参数值，可简化一点！2020/4/28*3+57三叉链表2020/4/2823中国海洋大学数学科学学院leftdataparentrightleftdataparentrightAAABBBCCCDDDFFFEEErootrootroot二叉链表和三叉链表2020/4/2824中国海洋大学数学科学学院三叉链表相当于线性表中的“双向”链表，方便由孩子找到双亲。说明2020/4/28二叉树的递归遍历2020/4/2826中国海洋大学数学科学学院按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。可能的三种遍历次序：先序：vLR中序：LvR后序：LRv二叉树的遍历vLR2020/4/2827中国海洋大学数学科学学院vLR递归的终结条件：盒子是“空”！二叉树的递归结构vLR2020/4/2828中国海洋大学数学科学学院Traverse(树T){if(T是空树)return！！！else访问根结点;//先序！Traverse(T的左子树);Traverse(T的右子树);return}二叉树的递归遍历模板vLR2020/4/2829中国海洋大学数学科学学院若二叉树为空，则空操作；否则：访问根结点(v)；先序遍历左子树(L)；先序遍历右子树(R)。先序遍历(PreorderTraversal)2020/4/2830中国海洋大学数学科学学院先序：-+a*b-cd/ef遍历序列--/+*abcdef2020/4/2831中国海洋大学数学科学学院defpreorder(tree):iftree!=None:print(tree[0],end='')#对根的访问preorder(tree[1])preorder(tree[2])递归的先序遍历算法——基于list表示2020/4/2832中国海洋大学数学科学学院defpreorder(root):ifroot!=None:print(root.data,end=‘’)#对根的访问preorder(root.left)preorder(root.right)递归的先序遍历算法——基于二叉链表表示2020/4/2833中国海洋大学数学科学学院若二叉树为空，则空操作；否则：中序遍历左子树(L)；访问根结点(v)；中序遍历右子树(R)。中序遍历(InorderTraversal)2020/4/2834中国海洋大学数学科学学院中序：a+b*c-d-e/f后序：abcd-*+ef/-遍历序列--/+*abcdef2020/4/2835中国海洋大学数学科学学院definorder(root):ifroot!=None:inorder(root.left)print(root.data,end=‘’)#对根的访问inorder(root.right)递归的中序遍历算法——基于二叉链表表示2020/4/2836中国海洋大学数学科学学院deforder(树T):iftree!=None:order(T的左子树);order(T的右子树);}}第一次到达T时visit由左子树返回T时visit由右子树返回T时visit三种遍历的递归模板相同，访问时机不同！2020/4/2837中国海洋大学数学科学学院-/+baef递归的执行过程是相同的！！！2020/4/2838中国海洋大学数学科学学院基于遍历的递归算法2020/4/2839中国海洋大学数学科学学院defcount(root):ifroot==None:return0else:n1=count(root.left)n2=count(root.right)n=1+n1+n2;returnn例1：基于后序遍历计算结点总数vLR2020/4/2840中国海洋大学数学科学学院defnum(root):ifroot==None:return0else:return1+num(root.left)+num(root.right)简写——明白这里是后序遍历模板2020/4/2841中国海洋大学数学科学学院defheight(root):ifroot==None:return-1else:return1+max(height(root.left),height(root.right))//注意：层次从0编号时，空树深度为-1!例2：基于后序遍历计算高度vLR2020/4/2842中国海洋大学数学科学学院二叉树的建立2020/4/2843中国海洋大学数学科学学院先序序列：ABHFDECKG中序序列：HBDFAEKCG由先序和中序序列可唯一确定一棵二叉树！HBDFEKCGAEKCGABHDFEKCGABHDF2020/4/2844中国海洋大学数学科学学院先序序列：ABHFDECKG中序序列：HBDFAEKCG由先序和中序序列可唯一确定一棵二叉树！EKCGABHFDKCGEABHFDEABHFDCKG2020/4/2845中国海洋大学数学科学学院根根左子树结点右子树结点左子树结点右子树结点k个结点p1p1+1p1+k+1p2i1i1+ki1+k+1i2中：先：2020/4/2846中国海洋大学数学科学学院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/4/28中国海洋大学数学科学学院47先序序列：ABDEC先序扩展序列：AB#DE###C##先序“扩展”序列CABED2020/4/2848中国海洋大学数学科学学院defTreeToExtendedPreorder(root,lst):ifroot==None:lst.append(‘#')else:lst.append(root.data)TreeToExtendedPreorder(root.left,lst)TreeToExtendedPreorder(root.right,lst)将二叉树输出为先序扩展序列2020/4/2849中国海洋大学数学科学学院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/4/2850中国海洋大学数学科学学院