数据结构

Size: px

Start display at page:

Download "数据结构"

霓锋孟
5 years ago
Views:

1 第六讲二叉树孙猛年 10 月 22 日

2 被猜价格第一次第二次第三次第四次第五次第六次第七次

3 课程内容二叉树及其抽象数据类型二叉树的周游二叉树的实现 3

4 二叉树及其抽象数据类型基本概念二叉树可以定义为结点的有限集合, 这个集合或者为空集, 或者由一个根及两棵不相交的分别称作这个根的左子树和右子树的二叉树组成二叉树的定义是个递归定义二叉树可以是个空集合, 这时的二叉树称为空二叉树二叉树也可以是只有一个结点的集合, 这个结点只能是根 ; 它的左子树和右子树均是空二叉树 4

5 二叉树的五种基本形态 5

6 二叉树的基本术语 A 的祖先根结点的层数 Level 0 A 的兄弟 A 的子孙 A B 父结点 Level 1 边 Level 2 子结点 Level 3 ( 二结叉点树的的最深大度层或数高 ) 度叶结点 Level 4 6

7 满二叉树和完全二叉树满二叉树 : 如果一棵二叉树的任何结点或者是树叶, 或有两棵非空子树, 则此二叉树称作满二叉树完全二叉树 : 如果一棵二叉树至多只有最下面的两层结点度数可以小于 2, 其余各层结点度数都必须为 2, 并且最下面一层的结点都集中在该层最左边的若干位置上, 则此二叉树称为完全二叉树完全二叉树不一定是满二叉树 7

8 满二叉树和完全二叉树举例满二叉树完全二叉树 8

9 扩充二叉树和外部结点扩充二叉树 : 把原二叉树的结点都变为度数为 2 的分支结点, 也就是说, 如果原结点的度数为 2, 则不变, 度数为 1, 则增加一个分支, 度数为 0( 树叶 ), 则增加两个分支 b a d c e 新增加的结点都用小方框表示, 称为外部结点, 树中原有的结点称为内部结点 f 特别对空二叉树扩充得到只有一个外部结点的扩充二叉树 9

10 外部路径长度和内部路径长度外部路径长度 E 定义为在扩充的二叉树中从根到每个外部结点的路径长度之和内部路径长度 I 定义为在扩充的二叉树中从根到每个内部结点的路径长度之和 10

11 主要性质性质 1 在二叉树的 i 层上至多有 2 i 个结点 (i 0) 性质 2 高度为 k 的二叉树中最多有 2 k+1 1 个结点 (k 0) 性质 3 对于任何一棵二叉树, 如果叶结点个数为 n 0, 度为 2 的结点个数为 n 2, 则有 n 0 = n ( 因为 :n0 + n1 + n2 = n1 + 2 n2 + 1) 11

12 完全二叉树的主要性质性质 4 具有 n 个结点的完全二叉树的深度 k 为 log 2 n 性质 5 对于具有 n 个结点的完全二叉树, 如果按照从上 ( 根结点 ) 到下 ( 叶结点 ) 和从左到右的顺序对二叉树中的所有结点从 0 开始到 n-1 进行编号, 则对于任意的下标为 i 的结点, 有 : (1) 如果 i=0, 则它是根结点, 它没有父结点 : 1) 如果 i>0, 则它的父结点的下标为 ; (2) 如果 2i+1 n-1, 则下标为 i 的结点的左子结点的下标为 2i+1; 否则, 下标为 i 的结点没有左子结点 ; (i (3) 如果 2i+2 n-1, 则下标为 i 的结点的右子结点的下标为 2i+2; 否则, 下标为 i 的结点没有右子结点 7 12

13 满 / 扩充二叉树的主要性质性质 6 在满二叉树中, 叶结点的个数比分支结点个数多 1 ( 因为 :n0= n2 + 1 ) 性质 7 在扩充二叉树中, 外部结点的个数比内部结点的个数多 1 性质 8 对任意扩充二叉树, 外部路径长度 E 和内部路径长度 I 之间满足关系 :E = I + 2n, 其中 n 是内部结点个数 13

14 E = I + 2n 如下图的扩充二叉树中 : E = = 21 I = = 9 n = 6 a b d c e f 14

15 二叉树的抽象数据类型 ADT BinTree: BinTree: Data * BinTree * BinTree -> BinTree; is_empty: BinTree -> Bool; root: BinTree -> Data; left: BinTree -> BinTree; right: BinTree -> BinTree; set_left: BinTree * BinTree -> BinTree; set_right: BinTree * BinTree -> BinTree; end ADT BinTree 15

16 什么是周游? 二叉树的周游二叉树的周游是指按某种方式访问二叉树中的所有结点, 使每个结点被访问一次且只被访问一次深度优先周游广度优先周游 16

17 深度优先周游若以符号 D L R 分别表示根结点左子树右子树, 则二叉树的周游共有六种方式 :DLR,LDR, LRD,DRL,RDL 和 RLD 如果限定先左后右, 则只能采用前三种周游方式 : DLR----- 先根次序 ( 简称先序或前序 ) 周游 LDR----- 中根次序 ( 简称中序或对称序 ) 周游 LRD----- 后根次序 ( 简称后序 ) 周游 17

18 先根序列若二叉树不空, 则先访问根 ; 然后按先根次序周游左子树 ; 最后按先根次序周游右子树下图所示二叉树, 先根次序周游得到的结点序列 ( 也称为先根序列 ) 为 :A,B,D,C,E,G,F,H,I D B E A C F G H I 18

19 后根序列若二叉树不空, 则先按后根次序周游左子树 ; 然后按后根次序周游右子树 ; 最后访问根前图所示的二叉树, 后根次序周游得到的结点序列 ( 也称为后根序列 ) 为 :D,B,G,E,H,I,F,C,A D B E A C F G H I 19

20 对称 ( 中根 ) 序列若二叉树不空, 则先按对称序周游左子树 ; 然后访问根 ; 最后按对称序周游右子树对于前图所示的二叉树, 按对称序周游一棵二叉树得到的结点序列 ( 也称为对称或中根序列 ) 为 :D,B,A, E,G,C,H,F,I A D B E C F G H I 20

21 提示对于给定的二叉树, 可以唯一确定它的先根序列后根序列和对称序列但是反过来, 给定一个二叉树的任意一种周游的序列, 无法唯一确定这个二叉树一般而言, 如果已知一个二叉树的对称序列, 又知道另外一种周游序列 ( 无论是先根序列还是后根序列 ), 就可以唯一确定这个二叉树先根 ABECFDGHIJKL 中根 EBFCDAIJKHGL 21

22 广度优先周游若二叉树的高度为 h, 则从 0 到 h 逐层如下处理 : 从左到右逐个访问存在的结点广度优先周游一棵二叉树所得到的结点序列, 叫作这棵二叉树的层次序列前图的二叉树, 广度优先周游所得到的结点层次序列为 : A,B,C,D,E,F,G,H,I A D B E C F G H I 22

23 例子对这个二叉树进行先根后根和中根周游所得到的线性序列分别为 : 先根序列 -ab +cd 后根序列 ab -cd + 中根序列 a -b c +d 它们也分别被称为表达式的前缀表示后缀表示和中缀表示 23

24 周游的抽象算法这里给出的算法, 都是建立在上节关于抽象数据类型基本运算的基础上它们不依赖于二叉树的具体存储结构, 所以称为抽象算法 24

25 二叉树先根次序周游的递归算法 25

26 二叉树对称序周游的递归算法 26

27 二叉树后根次序周游的递归算法 27

28 先根次序周游考虑先根序的非递归遍历算法需要用一个栈保存树尚未访问过部分的信息考虑先根序遍历的一种方法基本想法很简单先根序, 访问遇到的结点并沿左枝下行尚未访问的右分支需要记录, 将其入栈遇空树时回溯, 取出栈中保存的右分支, 像一棵树一样遍历它算法还有一些细节, 主要是循环的控制循环条件 : 当前树非空 ( 这棵树需要遍历 ) 或者栈不空 ( 还存在整个树的未遍历部分 ), 这时就应该继续循环在向下检查左分支时把经过结点的右分支入栈 ( 也要用一个循环 ) 弹出栈中元素 ( 一个右子树 ) 回溯, 要做的也是遍历一棵二叉树 28

29 先根次序周游的非递归算法 29

30 算法的时间代价假设栈的主要操作只要常量时间, 算法中每个二叉树恰好进栈出栈各一次, 所以它的时间代价为 O(n), 其中 n 为二叉树中子二叉树 ( 也是结点 ) 的个数 30

31 先根次序周游的非递归算法 31

32 对称序周游 1. 若当前二叉树不为空时, 则沿其左子树尽量前进, 在前进过程中, 把所经过的二叉树逐个压入栈中, 直到左子树为空 2. 弹出栈顶元素为当前二叉树, 并访问该二叉树的根 ; 3. 如果当前二叉树有右子树, 再进入它的右子树 ( 作为当前二叉树 ), 从 1 开始执行上述过程 ; 4. 如果当前二叉树没有右子树, 但是栈不空, 转 2 重复上面的处理, 直到当前二叉树没有右子树并且栈也为空时, 周游结束 32

33 对称序周游的非递归算法 33

34 算法的时间代价假设栈的主要操作只要常量时间, 算法中每个二叉树恰好进栈出栈各一次, 所以它的时间代价还是 O(n), 其中 n 为二叉树中子二叉树 ( 也是结点 ) 的个数外表看它是一个双重循环, 但时间代价还是线性的 34

35 后根次序周游 1. 首先由该二叉树找到其左子树, 周游其左子树, 周游完返回到这个二叉树的根 ; 2. 然后由该二叉树找到其右子树, 周游其右子树, 周游完再次返回到这个二叉树的根, 3. 最后才能访问该二叉树的根结点为此必须在算法中增加对二叉树出栈的判断 : 如果是从栈顶二叉树的左子树回来, 就直接进入右子树周游 ; 如果是从栈顶二叉树的右子树回来, 就执行出栈, 访问该二叉树的根结点 35

36 后根次序周游算法 36

37 算法的代价分析假设栈的主要操作只要常量时间, 算法中每个二叉树恰好进栈出栈各一次, 所以它的时间代价还是 O(n), 其中 n 为二叉树中子二叉树 ( 也是结点 ) 的个数外表看它是一个双重循环, 但时间代价还是线性的各种深度周游算法的空间代价主要是栈最坏情况是 O(n) 37

38 广度优先周游根据广度优先周游的思想不难想到, 可以利用一个队列实现其算法 : 首先把二叉树送入队列 ; 其后, 每当从队首取出一个二叉树访问根之后, 马上把它的子二叉树按从左到右的次序送入队列尾端 ; 重复此过程直到队列为空 38

39 广度优先周游二叉树 39

40 算法的代价分析每个二叉树进队列一次出队列一次, 所以时间代价为 O(n) 主要空间代价是需要队列的附加空间若二叉树结点个数为 n, 最坏的情况出现在完全二叉树时, 需要大约 n/2 个队列元素的空间 40

41 二叉树现在考虑二叉树作为一种, 构造和基本操作等问题二叉树的基本操作应该包括创建二叉树一棵二叉树或为空 ( 用 None 表示 ), 或是两棵已有二叉树和要存在树根结点的一项数据, 构造起的根结点代表构造出的二叉树 :BiTree(dat, left, right) 判断树空 :is_empty(bitree) 访问操作, 访问二叉树的组成成分 : 访问二叉树的根结点数据元素 :data() 取得一棵二叉树的左右子树 :right(),left() 其他操作 41

42 二叉树的 list 实现首先考虑二叉树的一种 list 实现这种技术不仅可用于实现二叉树, 也可用于实现一般的树采用下面的设计 : 空树用空表 [ ] 表示非空二叉树用包含三个元素的表 [d, l, r] 表示, 其中 d 表示存在根结点的元素,l 和 r 是两棵子树, 按同样方式用两个 list 表示显然, 这样设计做出的是一种递归结构, 每棵二叉树都有一个与之对应的 ( 递归结构的 )list 42

43 二叉树的 list 实现下面是一棵二叉树及其 list 表示 A B D C E F G H I ['A', ['B', [], []], ['C', ['D', ['F', [], []], ['G', [], []]], ['E', ['H', [], []], ['I', [], []] ] ] ] 43

44 二叉树的 list 实现相关的二叉树操作很容易实现, 下面是一组基本操作 def BiTree(data, left, right): return [data, left, right] def is_empty_bitree(bitree): return bitree == [] def root(bitree): return bitree[0] def leftch(bitree): return bitree[1] def rightch(bitree): return bitree[2] def set_root(bitree, data): betree[0] = data def set_leftch(bitree, left): betree[1] = left def set_rightch(bitree, right): betree[2] = right 简单使用 : t1 = BiTree(2, BiTree(4, [], []), BiTree(8, [], [])) 这相当于 :t1 = [2, [4, [], []], [8, [], []]] 44

45 链接表示二叉树中每个结点对应链接表示中的一个结点每个结点中, 除了存储结点本身的数据外, 再设置两个链接字段 :llink 和 rlink, 分别存放结点的左子结点和右子结点的位置当结点的某个子树为空时, 则相应的链接为空 llink info rlink 45

46 链接表示直接用结点构造的二叉树具有递归的结构, 可以很方便地递归处理但这样的二叉树结构也有不统一的地方用 None 表示空树, 但 None 不具有 BiTNode 类型解决问题的方法是定义一个二叉树类型, 以结点树作为其内部表示与链接表的情况类似, 那里也是以一个结点表作为内部表示 46

47 二叉树类 47

48 二叉树类可以考虑定义一个或几个遍历迭代器, 例如 48

49 二叉树类其他操作可以根据需要定义, 也可以考虑以这个二叉树为基类定义派生的二叉树类除遍历操作外, 其他操作都是 O(1) 在这种表示上求父结点的操作较难实现, 只能通过从根开始的遍历来完成, 最坏时间代价是 O(n) 为了提高求父结点操作的速度, 可以采用的另一种链接表示方式是三叉链表表示, 即给二叉树中的每个结点增加一个指向父结点的引用域采用三叉链表表示, 既便于查找子结点, 又便于查找父结点, 但是相对于左 - 右链接表示而言, 它增加了空间开销 49

50 三叉链表表示 50

51 线索二叉树线索二叉树是对于左右链接表示法的一种修改它利用结点的空的左链接 (llink) 存储该结点在某种周游序列中的前驱结点的位置 ; 利用结点的空的右链接 (rlink) 存储该结点在同种周游序列中的后继结点的位置这种附加的指向前驱结点和后继结点的链接称作线索, 加进了线索的二叉树左右链接表示称作线索二叉树 51

52 线索二叉树的结点为区分左右链接和线索, 需要在每个结点里增加两个标志位 ltag 和 rtag ltag=0,llink 指向结点的左子结点 ; ltag=1,llink 是线索, 指向结点的对称序的前驱结点 ; rtag=0,rlink 指向结点的右子结点 ; rtag=1,rlink 是线索, 指向结点的对称序的后继结点增加了标志域的结点结构为 : 52

53 线索二叉树示例 53

54 按对称序线索化二叉树在未线索化之前, 所有结点的 llink 和 rlink 都是指向子结点, 因此所有 ltag 和 rtag 的初始状态都为 0 给出一棵二叉树, 要将它按对称序线索化, 其做法就是按对称序周游此二叉树, 在周游的过程中用线索代替空链接 54

55 按对称序周游对称序线索二叉树要按对称序周游对称序线索二叉树, 首先找到对称序列中的第一个结点, 然后依次找到结点的后继结点, 直至其后继结点为空即可第一个结点也很容易找, 只要从根结点出发沿着左指针不断往下走, 直至左指针为空, 到达最左下的结点, 这就是对称序第一个结点找任意结点的对称序后继时, 也非常容易做 : 一个结点的右指针字段如果是线索, 则它就指向该结点在对称序下的后继 ; 如果不是线索, 则它指向该结点右子树的根, 而该结点在对称序下的后继应是此右子树的最左下结点 55

56 本讲重点二叉树的概念和主要性质二叉树的周游算法 ( 递归与非递归 ) 二叉树的实现方法 56

6

孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 10 月 16 日 1 被猜价格第一次第二次第三次第四次第五次第六次第七次 39 50 25 37 43 40 38 39 82 50 75 88 82 99 50 75 88 94 97 99 2 二叉树及其抽象数据类型二叉树的周游二叉树的实现 3 基本概念二叉树可以定义为结点的有限集合,