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

1、二叉树的递归遍历,2016 Fall 数据结构,2020/8/7,1,中国海洋大学数学科学学院,二叉树的存储表示,2020/8/7,空树：None 非空树：data, left, right,方式1：list,2020/8/7,中国海洋大学数学科学学院,3,递归的 终结状态,tree = *, 3, None, None, +, 5, None, None, 7, None, None,例：,2020/8/7,空树：None 非空树： 若结点的左右子树均为空，则为 data 否则：data, left, right,方式1：简化的list,2020/8/7,中国海洋大学数学科学学院,5,也是递

2、归的 终结状态,tree = *, 3, +, 5, 7,例：简化的list,2020/8/7,list表示是利用了Python的list可以含有不同类型的元素，将树表示成长度为3的表，其中最后两个元素仍是表，即表的表，形成层次结构； 由于list是一个一般意义下的表，其实现本身有一定的复杂性，所以这种表示的效率不如自定义的二叉链表。,说明,2020/8/7,class BinTNode: def _init_(self, data, left = None, right = None): self.data = data self.left = left self.right = right

3、,方式2：二叉链表,2020/8/7,root = BinTNode(*, BinTNode(3, None, None), BinTNode(+, BinTNode(5, None, None), BinTNode(7, None, None),例：,2020/8/7,root = BinTNode(*, BinTNode(3), BinTNode(+, BinTNode(5), BinTNode(7),例：利用默认参数值，可简化一点！,2020/8/7,三叉链表,2020/8/7,12,中国海洋大学数学科学学院,二叉链表和三叉链表,2020/8/7,13,中国海洋大学数学科学学院,三叉链表

4、相当于线性表中的“双向”链表，方便由孩子找到双亲。,说明,2020/8/7,二叉树的递归遍历,2020/8/7,15,中国海洋大学数学科学学院,按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 可能的三种遍历次序： 先序： vLR 中序： LvR 后序： LRv,二叉树的遍历,2020/8/7,16,中国海洋大学数学科学学院,递归的终结条件： 盒子是“空”！,二叉树的递归结构,2020/8/7,17,中国海洋大学数学科学学院,Traverse( 树T ) if ( T是空树 ) return ！ else 访问根结点; /先序！ Traverse( T的左子树 ); Travers

5、e( T的右子树 ); return ,二叉树的递归遍历模板,2020/8/7,18,中国海洋大学数学科学学院,若二叉树为空，则空操作； 否则： 访问根结点 (v)； 先序遍历左子树 (L)； 先序遍历右子树 (R)。,先序遍历 (Preorder Traversal),2020/8/7,19,中国海洋大学数学科学学院,先序：- + a * b - c d / e f,遍历序列,2020/8/7,20,中国海洋大学数学科学学院,def preorder(tree): if tree != None: print(tree0, end=) # 对根的访问 preorder(tree1) preo

6、rder(tree2),递归的先序遍历算法基于list表示,2020/8/7,21,中国海洋大学数学科学学院,def preorder(root): if root != None: print(root.data, end=) # 对根的访问 preorder(root.left) preorder(root.right),递归的先序遍历算法基于二叉链表表示,2020/8/7,22,中国海洋大学数学科学学院,若二叉树为空，则空操作； 否则： 中序遍历左子树 (L)； 访问根结点 (v)； 中序遍历右子树 (R)。,中序遍历 (Inorder Traversal),2020/8/7,23,中国

7、海洋大学数学科学学院,中序：a + b * c - d - e / f 后序：a b c d - * + e f / -,遍历序列,2020/8/7,24,中国海洋大学数学科学学院,def inorder(root): if root != None: inorder(root.left) print(root.data, end=) # 对根的访问 inorder(root.right),递归的中序遍历算法基于二叉链表表示,2020/8/7,25,中国海洋大学数学科学学院,def order(树T): if tree != None: order(T的左子树); order(T的右子树);

8、,第一次到达T时visit,由左子树返回T时visit,由右子树返回T时visit,三种遍历的递归模板相同，访问时机不同！,2020/8/7,26,中国海洋大学数学科学学院,递归的执行过程是相同的！,2020/8/7,27,中国海洋大学数学科学学院,基于遍历的递归算法,2020/8/7,28,中国海洋大学数学科学学院,def count(root): if root = None: return 0 else: n1 = count(root.left) n2 = count(root.right) n = 1 + n1 + n2; return n,例1：基于后序遍历计算结点总数,2020/

9、8/7,29,中国海洋大学数学科学学院,def num(root): if root = None: return 0 else: return 1 + num(root.left) + num(root.right),简写明白这里是后序遍历模板,2020/8/7,30,中国海洋大学数学科学学院,def height(root): if root = None: return -1 else: return 1 + max(height(root.left), height(root.right) /注意： 层次从0编号时，空树深度为-1!,例2：基于后序遍历计算高度,2020/8/7,31,

10、中国海洋大学数学科学学院,二叉树的建立,2020/8/7,32,中国海洋大学数学科学学院,先序序列 ：ABHFDECKG 中序序列 ：HBDFAEKCG,由先序和中序序列可唯一确定一棵二叉树！,2020/8/7,33,中国海洋大学数学科学学院,先序序列 ：ABHFDECKG 中序序列 ：HBDFAEKCG,由先序和中序序列可唯一确定一棵二叉树！,2020/8/7,34,中国海洋大学数学科学学院,2020/8/7,35,中国海洋大学数学科学学院,def createTreeBy2Orders(preorderList, p1, p2, inorderList, i1, i2): if p1 =

11、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, p1+k+1, p2, inorderList, i1+k+1, i2) return root,由先序和中序序列建立二叉树,2020/8

12、/7,中国海洋大学数学科学学院,36,先序序列： A B D E C 先序扩展序列： A B # D E # # # C # #,先序“扩展”序列,2020/8/7,37,中国海洋大学数学科学学院,def TreeToExtendedPreorder(root, lst): if root = None: lst.append(#) else: lst.append(root.data) TreeToExtendedPreorder(root.left, lst) TreeToExtendedPreorder(root.right, lst),将二叉树输出为先序扩展序列,2020/8/7,38,中国海洋大学数学科学学院,def createTreeByExtendedPreorder(lst, i): 由lst的i位置开始读入先序遍历序列， 返回建立的二叉树，以及lst的下一个读入位置 if lsti = #: return No