6

Size: px

Start display at page:

Download "6"

翼包
5 years ago
Views:

1 孙猛年 10 月 16 日 1

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 扩充二叉树 : 把原二叉树的结 a 点都变为度数为 2 的分支结点, 也就是说, 如果原结点的度数为 2, 则不不变, 度数为 1, 则增 b d c e 加一个分支, 度数为 0 ( 树叶 ), 则增加两个分支 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 n blog 2 nc 性质 4: 具有个结点的完全二叉树的深度 k 为 11

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

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

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

15 ADT BinTree is operations BinTree bintree (DataType r, BinTree lt, BinTree rt); Bool is_empty (BinTree t); DataType root (BinTree t); BinTree left (BinTree t); Bintree right (BinTree t); BinTree set_left (BinTree t, BinTree new); BinTree set_right (BinTree t, BinTree new); 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 A B C D E F G H I 18

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

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

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

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

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

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

25 void preorder( BinTree t) { if (t==null) return; } visit(root(t)); preorder(leftchild(t)); preorder(rightchild(t)); 25

26 void inorder(bintree t){ if (t==null) return; } inorder(leftchild(t)); visit(root(t)); inorder(rightchild(t)); 26

27 void postorder( BinTree t) { if (t==null) return; } postorder(leftchild(t)); postorder(rightchild(t)); visit(root(t)); 27

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

29 void npreorder(bintree t) { Stack s; /* 栈元素的类型是 BinTree */ BinTreeNode* c; if (t = = NULL) return; s = createemptystack(); push(s, t); while (!isemptystack(s)) { /* 每当栈不不空 */ c = top(s); pop(s); /* 取栈顶, 出栈 */ if (c!= NULL) { visit(root(c)); /* 访问 */ push(s, rightchild(c)); /* 右子树进栈 */ push(s, leftchild(c)); /* 左子树进栈 */ } } } 29

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

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

32 void ninorder(bintree t) { Stack s= createemptystack(); /* 栈元素类型是 BinTree */ BinTree c= t; if (c = = NULL) return; do { while (c!= NULL) { push(s, c); c = leftchild(c); } c = top(s); pop(s); visit(root(c) ); c = rightchild(c); } while (c!= NULL!isEmptyStack(s)); } 32

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

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

35 void npostorder2( BinTree t ) { Stack s = createemptystack ( ); /* 栈中元素的类型是 BinTree*/ BinTree p = t; while ( p!= NULL!isEmptyStack (s) ) { while (p!= NULL) { push ( s, p ); p = leftchild (p)? leftchild (p): rightchild(p); } /* 循环到当前需要处理理的结点 */ p = top (s); pop (s); visit(root(p)); /* 栈顶二叉树的根是应访问结点 */ if (!isemptystack (s) && leftchild (top (s)) == p ) p = rightchild(top (s)) ; /* 栈不不空, 且为从左子树退回 */ else p = NULL; /* 从右子树回来, 退到上一层处理理 */ } } 35

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

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

38 void levelorder(bintree t) { BinTree c, cc; Queue q= createemptyqueue(); /* 队列列元素为 BinTree 类型 */ if (t==null) return; /* 空二叉树返回 */ c = t; enqueue(q,c); /* 将二叉树送入队列列 */ while (!isemptyqueue(q)) { c = frontqueue(q); dequeue(q); visit(root( c )); /* 从队列列首部取出二叉树并访问 */ cc = leftchild( c ); if(cc!=null) enqueue(q,cc); /* 将左子树送入队列列 */ cc= rightchild( c ); if(cc!=null) enqueue(q,cc); /* 将右子树送入队列列 */ } } 38

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

40 顺序表示链接表示线索二叉树 40

41 采用一组连续的存储单元来存放二叉树中的结点对于完全二叉树, 按照从上 ( 根结点 ) 到下 ( 叶结点 ) 和从左到右的顺序, 对二叉树中的所有结点从 0 到 n-1 编号, 这样存放到一维数组中只要通过数组元素的下标关系, 就可以确定二叉树中结点之间的逻辑关系 41

42 A B D C E F G H I A B C D E F G H I 42

43 对于一般的二叉树, 如果仍采用顺序表示, 首先要对它进行行扩充, 增加一些并不不存在的空结点, 使之成为一棵完全二叉树, 然后再用一维数组顺序存储 A A B C B C D E D E F G F G A B C ^ D E ^ ^ ^ F ^ ^ G 43

44 struct SeqBinTree{ /* 顺序二叉树类型定义 */ int MAXNUM /* 完全二叉树中允许结点的最大个数 */ int n; /* 改造成完全二叉树后, 结点的实际个数 */ DataType *nodelist; /* 存放结点的数组 */ }; typedef struct SeqBinTree *PSeqBinTree; /* 顺序二叉树类型的指针类型 */ 44

45 int parent_seq(pseqbintree t, int p){ /* 返回下标为 p 的结点的父结点的下标 */ } if (p < 0 p >= t->n) return -1; return (p - 1) / 2; int leftchild_seq(pseqbintree t, int p){ /* 返回下标为 p 的结点的左子结点的下标 */ if (p < 0 p >= t->n) return -1; return 2*p + 1; /* 可能不不存在 */ } int rightchild_seq (PSeqBinTree t, int p){ /* 返回下标为 p 的结点的右子结点的下标 */ if (p < 0 p >= t->n) return -1; return 2 * (p + 1) ; /* 可能不不存在 */ } 45

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

47 struct BinTreeNode; /* 二叉树中结点 */ typedef struct BinTreeNode * PBinTreeNode; /* 结点的指针类型 */ struct BinTreeNode{ DataType info; /* 数据域 */ PBinTreeNode llink; /* 指向左子结点 */ PBinTreeNode rlink; /* 指向右子结点 */ }; 47

48 由于递归是二叉树的固有特性, 二叉树的许多处理理都可以用递归算法来描述, 因此, 为了了运算和参数传递的方便便, 不不再对二叉树进行行封装, 直接将二叉树定义为指向结点的指针类型 : typedef struct BinTreeNode *BinTree; 在实际应用中, 将二叉树作为参数传递时, 可能需要传递二叉树根结点指针的地址, 因此, 为了了说明方便便, 可以引入二叉树类型的指针类型 : typedef BinTree *PBinTree; 48

49 /* 返回结点 p 的左子结点的地址 */ PBinTreeNode leftchild_link(pbintreenode p){ if (p == NULL) return NULL; return p->llink; } /* 返回结点 p 的右子结点的地址 */ PBinTreeNode rightchild_link(pbintreenode p){ if (p == NULL) return NULL; return p->rlink; } 49

50 只能从 t 出发, 使用前面介绍的周游算法, 通过算法中的访问函数 (visit), 检查当前结点是否所求结点的父结点最坏的时间代价与周游整个二叉树的代价相同为了了提高求父结点操作的速度, 可以采用的另一种链接表示方式是三叉链表表示, 即给二叉树中的每个结点增加一个指向父结点的指针域采用三叉链表表示, 既便便于查找子结点, 又便便于查找父结点, 但是相对于左 - 右指针表示而言, 它增加了了空间开销 50

51 51

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

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

54 54

55 struct ThrTreeNode; /* 线索二叉树中的结点 */ typedef struct ThrTreeNode * PThrTreeNode; /* 指向线索二叉树结点的指针类型 */ struct ThrTreeNode { /* 线索二叉树中结点的定义 */ DataType info; PThrTreeNode llink, rlink; int ltag, rtag; }; typedef struct ThrTreeNode * ThrTree; /* 线索二叉树类型的定义 */ typedef ThrTree * PThrTree; /* 线索二叉树类型的指针类型 */ 55

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

57 void thread(thrtree t) { PSeqStack st = createemptystack (M); /* 栈元素类型是 ThrTree, M 一般取 t 的高度 */ ThrTree p, pr; if (t==null) return ; p = t; pr = NULL; do { while (p!=null) {push_seq(st,p);p= p->llink;} p = top_seq(st); pop_seq(st); if (pr!=null) { if (pr->rlink==null) { pr->rlink = p;pr->rtag = 1; } /* 修改前驱结点的右指针 */ if (p->llink==null) { p->llink = pr; p->ltag = 1;} /* 修改该结点的左指针 */ } pr = p; p = p->rlink; } while (!isemptystack_seq(st) p!=null ); } 57

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

59 void ninorder(thrtree t ) { ThrTree p= t; if (t==null) return ; while ( p->llink!=null && p->ltag==0 ) p = p->llink; while (p!=null) { visit(*p); if ( p->rlink!=null && p->rtag==0 ) { /* 右子树不不是线索时 */ p = p->rlink; while (p->llink!=null&&p->ltag==0) p = p->llink; /* 顺右子树的左子树一直向下 */ } else p = p->rlink; } } 59

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

数据结构

数据结构第六讲二叉树孙猛 http://www.math.pku.edu.cn/teachers/sunm sunmeng@math.pku.edu.cn 2015 年 10 月 22 日被猜价格第一次第二次第三次第四次第五次第六次第七次 39 50 25 37 43 40 38 39 82 50 75 88 82 99 50 75 88 94 97 99 2 课程内容二叉树及其抽象数据类型