树的递归遍历

1、2020/7/6,中国海洋大学数学科学学院,1,第五章 二叉树,2016 Fall 数据结构,结点、结点的度、树的度、叶结点、孩子、双亲、兄弟、祖先、子孙、结点层次、树的深度,概念,2020/7/6,2,中国海洋大学数学科学学院,2020/7/6,叶结点：度是零的结点 结点的度：结点的孩子总数 树的度：结点的度的最大值,概念,一棵二叉树是结点的有限集合： 或者为空， 或者由：根结点 +左子树+右子树 组成。,二叉树 (Binary Tree),2020/7/6,4,中国海洋大学数学科学学院,二叉树的性质,2020/7/6,5,中国海洋大学数学科学学院,性质1：第 i 层最多有 2i 个结点。(

2、i 0) 数学归纳法！,2020/7/6,6,中国海洋大学数学科学学院,性质2： 深度为 h 的二叉树最多有 2h-1个结点。 (h 0) 20 + 21 + 22 + + 2h = 2h+1 - 1,2020/7/6,7,中国海洋大学数学科学学院,性质3 ：设叶结点有 n0 个，度为2的结点有 n2 个, 则有 n0n21 顶点总数：n = n0 + n1 + n2 总边数：e = 2n2 + n1 = n - 1 因此：2n2 + n1 = n0 + n1 + n2 - 1 推出：n0 = n2 + 1,2020/7/6,8,中国海洋大学数学科学学院,定义1： 满二叉树 (Full Bin

3、ary Tree) 定义2 ： 完全二叉树 (Complete Binary Tree),2020/7/6,9,中国海洋大学数学科学学院,性质4： 含n个结点的完全二叉树的深度为 ： log2n 设完全二叉树的深度为 h，则有： 2h n 2h+1 取对数： h log2n h+1 则有： h= log2n ,2020/7/6,10,中国海洋大学数学科学学院,深度定义为结点的最大层数 层数由零开始计！,性质4 ：含 n 个结点的完全二叉树的深度为： log2(n+1) - 1 设完全二叉树的深度为 h，则有： 2h - 1 n 2h+1 - 1 变形 ： 2h n+1 2h+1 取对数： h

4、log2(n+1) h+1 则有： log2(n+1) = h+1,2020/7/6,11,中国海洋大学数学科学学院,深度定义为结点的最大层数 层数由零开始计！,性质5： 对完全二叉树的结点自顶向下、同一层自左向右连续编号：0, 1, 2, , n-1，则： 若2*i+1 0，则 i 的双亲为 (i -1)/2,2020/7/6,12,中国海洋大学数学科学学院,由性质5：完全二叉树适合顺序存储！,2020/7/6,13,中国海洋大学数学科学学院,空树：None 非空树：data, left, right,方式1：list,2020/7/6,中国海洋大学数学科学学院,14,递归的 终结状态,20

5、20/7/6,tree = *, 3, None, None, +, 5, None, None, 7, None, None,例：,空树：None 非空树： 若结点的左右子树均为空，则为 data 否则：data, left, right,方式1：简化的list,2020/7/6,中国海洋大学数学科学学院,16,也是递归的 终结状态,2020/7/6,tree = *, 3, +, 5, 7,例：简化的list,2020/7/6,list表示是利用了Python的list可以含有不同类型的元素，将树表示成长度为3的表，其中最后两个元素仍是表，即表的表，形成层次结构； 由于list是一个一般意

6、义下的表，其实现本身有一定的复杂性，所以这种表示的效率不如自定义的二叉链表。,说明,class BinTNode: def _init_(self, data, left = None, right = None): self.data = data self.left = left self.right = right,方式2：二叉链表,2020/7/6,2020/7/6,root = BinTNode(*, BinTNode(3, None, None), BinTNode(+, BinTNode(5, None, None), BinTNode(7, None, None),例：,202

7、0/7/6,root = BinTNode(*, BinTNode(3), BinTNode(+, BinTNode(5), BinTNode(7),例：利用默认参数值，可简化一点！,2020/7/6,中国海洋大学数学科学学院,23,三叉链表,2020/7/6,中国海洋大学数学科学学院,24,二叉链表和三叉链表,2020/7/6,三叉链表相当于线性表中的“双向”链表，方便由孩子找到双亲。,说明,二叉树的递归遍历,2020/7/6,26,中国海洋大学数学科学学院,按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 可能的三种遍历次序： 先序： vLR 中序： LvR 后序： LRv,二

8、叉树的遍历,2020/7/6,27,中国海洋大学数学科学学院,2020/7/6,中国海洋大学数学科学学院,28,递归的终结条件： 盒子是“空”！,二叉树的递归结构,Traverse( 树T ) if ( T是空树 ) return ！ else 访问根结点; /先序！ Traverse( T的左子树 ); Traverse( T的右子树 ); return ,二叉树的递归遍历模板,2020/7/6,29,中国海洋大学数学科学学院,若二叉树为空，则空操作； 否则： 访问根结点 (v)； 先序遍历左子树 (L)； 先序遍历右子树 (R)。,先序遍历 (Preorder Traversal),202

9、0/7/6,30,中国海洋大学数学科学学院,先序：- + a * b - c d / e f,遍历序列,2020/7/6,31,中国海洋大学数学科学学院,def preorder(tree): if tree != None: print(tree0, end=) # 对根的访问 preorder(tree1) preorder(tree2),递归的先序遍历算法基于list表示,2020/7/6,32,中国海洋大学数学科学学院,def preorder(root): if root != None: print(root.data, end=) # 对根的访问 preorder(root.le

10、ft) preorder(root.right),递归的先序遍历算法基于二叉链表表示,2020/7/6,33,中国海洋大学数学科学学院,若二叉树为空，则空操作； 否则： 中序遍历左子树 (L)； 访问根结点 (v)； 中序遍历右子树 (R)。,中序遍历 (Inorder Traversal),2020/7/6,34,中国海洋大学数学科学学院,中序：a + b * c - d - e / f 后序：a b c d - * + e f / -,遍历序列,2020/7/6,35,中国海洋大学数学科学学院,def inorder(root): if root != None: inorder(root

11、.left) print(root.data, end=) # 对根的访问 inorder(root.right),递归的中序遍历算法基于二叉链表表示,2020/7/6,36,中国海洋大学数学科学学院,def order(树T): if tree != None: order(T的左子树); order(T的右子树); ,第一次到达T时visit,由左子树返回T时visit,由右子树返回T时visit,三种遍历的递归模板相同，访问时机不同！,2020/7/6,37,中国海洋大学数学科学学院,2020/7/6,中国海洋大学数学科学学院,38,递归的执行过程是相同的！,基于遍历的递归算法,2020

12、/7/6,39,中国海洋大学数学科学学院,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/7/6,40,中国海洋大学数学科学学院,def num(root): if root = None: return 0 else: return 1 + num(root.left) + num(root.right),简写明白这里是后序遍历模板,2020/7/6,41,中国海

13、洋大学数学科学学院,def height(root): if root = None: return -1 else: return 1 + max(height(root.left), height(root.right) /注意： 层次从0编号时，空树深度为-1!,例2：基于后序遍历计算高度,2020/7/6,42,中国海洋大学数学科学学院,二叉树的建立,2020/7/6,43,中国海洋大学数学科学学院,先序序列 ：ABHFDECKG 中序序列 ：HBDFAEKCG,由先序和中序序列可唯一确定一棵二叉树！,2020/7/6,44,中国海洋大学数学科学学院,先序序列 ：ABHFDECKG 中

14、序序列 ：HBDFAEKCG,由先序和中序序列可唯一确定一棵二叉树！,2020/7/6,45,中国海洋大学数学科学学院,2020/7/6,46,中国海洋大学数学科学学院,def createTreeBy2Orders(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(preord

15、erList, 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/7/6,中国海洋大学数学科学学院,47,先序序列： A B D E C 先序扩展序列： A B # D E # # # C # #,先序“扩展”序列,2020/7/6,48,中国海洋大学数学科学学院,def TreeToExtendedPreorder(root, lst): if root = None: lst.append(#) else: lst.append(root.data) TreeToExtendedPreorder(root.left, lst) TreeToExtendedPreorder(root.right, lst),将二叉树输出为先序扩展序列,2020/7/6,49,中国海洋大学数学科学学院,def createTreeByExtendedPreorder(lst, i): 由lst的i位置开始读入