《数据结构与算法(python语言描述)课件ds_051_树的递归遍历》由会员分享，可在线阅读，更多相关《数据结构与算法(python语言描述)课件ds_051_树的递归遍历（39页珍藏版）》请在金锄头文库上搜索。
1、二叉树的递归遍历,2016 Fall 数据结构,2019/10/22,1,中国海洋大学数学科学学院,二叉树的存储表示,2019/10/22,空树：None 非空树：data, left, right,方式1：list,2019/10/22,中国海洋大学数学科学学院,3,递归的 终结状态,tree = *, 3, None, None, +, 5, None, None, 7, None, None,例：,2019/10/22,空树：None 非空树： 若结点的左右子树均为空，则为 data 否则：data, left, right,方式1：简化的list,2019/10/22,中国海洋大学数学
2、科学学院,5,也是递归的 终结状态,tree = *, 3, +, 5, 7,例：简化的list,2019/10/22,list表示是利用了Python的list可以含有不同类型的元素，将树表示成长度为3的表，其中最后两个元素仍是表，即表的表，形成层次结构； 由于list是一个一般意义下的表，其实现本身有一定的复杂性，所以这种表示的效率不如自定义的二叉链表。,说明,2019/10/22,class BinTNode: def _init_(self, data, left = None, right = None): self.data = data self.left = left self
3、.right = right,方式2：二叉链表,2019/10/22,root = BinTNode(*, BinTNode(3, None, None), BinTNode(+, BinTNode(5, None, None), BinTNode(7, None, None),例：,2019/10/22,root = BinTNode(*, BinTNode(3), BinTNode(+, BinTNode(5), BinTNode(7),例：利用默认参数值，可简化一点！,2019/10/22,三叉链表,2019/10/22,12,中国海洋大学数学科学学院,二叉链表和三叉链表,2019/10
4、/22,13,中国海洋大学数学科学学院,三叉链表相当于线性表中的“双向”链表，方便由孩子找到双亲。,说明,2019/10/22,二叉树的递归遍历,2019/10/22,15,中国海洋大学数学科学学院,按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 可能的三种遍历次序： 先序： vLR 中序： LvR 后序： LRv,二叉树的遍历,2019/10/22,16,中国海洋大学数学科学学院,递归的终结条件： 盒子是“空”！,二叉树的递归结构,2019/10/22,17,中国海洋大学数学科学学院,Traverse( 树T ) if ( T是空树 ) return ！ else 访问根结点;
5、 /先序！ Traverse( T的左子树 ); Traverse( T的右子树 ); return ,二叉树的递归遍历模板,2019/10/22,18,中国海洋大学数学科学学院,若二叉树为空，则空操作； 否则： 访问根结点 (v)； 先序遍历左子树 (L)； 先序遍历右子树 (R)。,先序遍历 (Preorder Traversal),2019/10/22,19,中国海洋大学数学科学学院,先序：- + a * b - c d / e f,遍历序列,2019/10/22,20,中国海洋大学数学科学学院,def preorder(tree): if tree != None: print(tre
6、e0, end=) # 对根的访问 preorder(tree1) preorder(tree2),递归的先序遍历算法基于list表示,2019/10/22,21,中国海洋大学数学科学学院,def preorder(root): if root != None: print(root.data, end=) # 对根的访问 preorder(root.left) preorder(root.right),递归的先序遍历算法基于二叉链表表示,2019/10/22,22,中国海洋大学数学科学学院,若二叉树为空，则空操作； 否则： 中序遍历左子树 (L)； 访问根结点 (v)； 中序遍历右子树 (R
7、)。,中序遍历 (Inorder Traversal),2019/10/22,23,中国海洋大学数学科学学院,中序：a + b * c - d - e / f 后序：a b c d - * + e f / -,遍历序列,2019/10/22,24,中国海洋大学数学科学学院,def inorder(root): if root != None: inorder(root.left) print(root.data, end=) # 对根的访问 inorder(root.right),递归的中序遍历算法基于二叉链表表示,2019/10/22,25,中国海洋大学数学科学学院,def order(树T
8、): if tree != None: order(T的左子树); order(T的右子树); ,第一次到达T时visit,由左子树返回T时visit,由右子树返回T时visit,三种遍历的递归模板相同，访问时机不同！,2019/10/22,26,中国海洋大学数学科学学院,递归的执行过程是相同的！,2019/10/22,27,中国海洋大学数学科学学院,基于遍历的递归算法,2019/10/22,28,中国海洋大学数学科学学院,def count(root): if root = None: return 0 else: n1 = count(root.left) n2 = count(root.
9、right) n = 1 + n1 + n2; return n,例1：基于后序遍历计算结点总数,2019/10/22,29,中国海洋大学数学科学学院,def num(root): if root = None: return 0 else: return 1 + num(root.left) + num(root.right),简写明白这里是后序遍历模板,2019/10/22,30,中国海洋大学数学科学学院,def height(root): if root = None: return -1 else: return 1 + max(height(root.left), height(ro
10、ot.right) /注意： 层次从0编号时，空树深度为-1!,例2：基于后序遍历计算高度,2019/10/22,31,中国海洋大学数学科学学院,二叉树的建立,2019/10/22,32,中国海洋大学数学科学学院,先序序列 ：ABHFDECKG 中序序列 ：HBDFAEKCG,由先序和中序序列可唯一确定一棵二叉树！,2019/10/22,33,中国海洋大学数学科学学院,先序序列 ：ABHFDECKG 中序序列 ：HBDFAEKCG,由先序和中序序列可唯一确定一棵二叉树！,2019/10/22,34,中国海洋大学数学科学学院,2019/10/22,35,中国海洋大学数学科学学院,def crea
11、teTreeBy2Orders(preorderList, p1, p2, inorderList, i1, i2): if p1 = p2: return None data = preorderListp1 k = inorderList.index(data, i1, i2) - i1 root = BinTNode(data) root.left = createTreeBy2Orders(preorderList, p1+1, p1+k+1, inorderList, i1, i1+k) root.right = createTreeBy2Orders(preorderList, p
12、1+k+1, p2, inorderList, i1+k+1, i2) return root,由先序和中序序列建立二叉树,2019/10/22,中国海洋大学数学科学学院,36,先序序列： A B D E C 先序扩展序列： A B # D E # # # C # #,先序“扩展”序列,2019/10/22,37,中国海洋大学数学科学学院,def TreeToExtendedPreorder(root, lst): if root = None: lst.append(#) else: lst.append(root.data) TreeToExtendedPreorder(root.left
13、, lst) TreeToExtendedPreorder(root.right, lst),将二叉树输出为先序扩展序列,2019/10/22,38,中国海洋大学数学科学学院,def createTreeByExtendedPreorder(lst, i): 由lst的i位置开始读入先序遍历序列， 返回建立的二叉树，以及lst的下一个读入位置 if lsti = #: return None, i+1 root = BinTNode(lsti) root.left, j1 = createTreeByExtendedPreorder(lst, i+1) root.right, j2 = createTreeByExtendedPreorder(lst, j1) return root, j2,由先序的扩展序列建立二叉树,2019/10/22,39,中国海洋大学数学科学学院,
