幻灯片 1

Size: px

Start display at page:

Download "幻灯片 1"

格龄乐
7 years ago
Views:

1 二叉树汪小林改写基于张铭王腾蛟原稿北京大学信息学院

2 主要内容 1. 二叉树的概念 2. 二叉树的抽象数据类型 3. 二叉树的存储结构 4. 二叉搜索树 5. 堆与优先队列 6. Huffman 树及其应用 7. 二叉树知识点总结

3 1 二叉树的概念二叉树的定义及基本术语满二叉树完全二叉树扩充二叉树二叉树的主要性质

4 二叉树的定义二叉树 (binary tree) 由结点的有限集合构成, 这个有限集合或者为空集 (empty), 或者为由一个根结点 (root) 及两棵互不相交分别称作这个根的左子树 (left subtree) 和右子树 (right subtree) 的二叉树组成的集合

5 二叉树的五种基本形态

6 满二叉树如果一棵二叉树的任何结点, 或者是树叶, 或者恰有两颗非空子树, 则此二叉树称作满二叉树

7 完全二叉树最多只有最下面的两层结点度数可以小于 2 最下一层的结点都集中最左边

8 扩充二叉树所有空子树, 都增加空树叶

9 扩充二叉树从扩充的二叉树的根到每个外部结点的路径长度之和称为外部路径长度 (E) 扩充的二叉树里从根到每个内部结点的路径长度之和称为内部路径长度 (I) 外部路径长度 E 和内部路径长度 I 满足 : E = I + 2n, 其中 n 是内部结点个数

10 二叉树的主要性质性质 1. 在二叉树中, 第 i 层上最多有 2 i 个结点 (i 0) 证明 : 利用数学归纳法当 i = 0 时,2 0 = 1, 只有一个根结点, 正确现在假设对所有的 j,1 j <i, 命题成立, 即第 j 层上最多有 2 j 个结点下面证明当就 j = i 时结论也成立由归纳假设, 第 i - 1 层上最多有 2 i- 1 个结点由于二叉树每个结点的度数最大为 2, 所以第 i 层上的最大结点数为第 i - 1 层上的最大结点数的 2 倍, 即 2 i 个

11 二叉树的主要性质性质 2. 深度为 k 的二叉树至多有 2 k+1-1 个结点 (k 0) 其中深度 (depth) 定义为二叉树中层数最大的叶结点的层数证明 : 由性质 1 可知, 第 i 层的最大结点数为 2 i, 所以 k i 0 2 i 2 k 1 1

12 二叉树的主要性质性质 3. 任何一棵二叉树, 若其叶结点数为 n 0, 内结点数为 n 2, 则 n 0 =n 2 +1 证明 : 设 n 1 为二叉树中度为 1 的结点数该二叉树的结点总数 n 为度分别为 0,1,2 的结点数之和, 即 n=n 0 +n 1 +n 2 ( 公式 1) 除根结点外, 其余结点都有一条边进入, 设边数为 e, 有 n=e+1 由于这些边是由度为 1 或 2 的的结点射出的, 所以又有 e=n 1 +2n 2, 于是得 n=e+1=n 1 +2n 2 +1 ( 公式 2) 由公式 1 和 2 得 n 0 +n 1 +n 2 =n 1 +2n 2 +1, 即 n 0 =n 2 +1

13 二叉树的主要性质性质 4. 满二叉树定理 : 非空满二叉树树叶数目等于其分支结点数加 1 证明 : 满二叉树定理由性质 3 可直接推出性质 5. 满二叉树定理推论 : 一个非空二叉树的空子树数目等于其结点数加 1 证明 : 设二叉树为 T, 将其所有空子树换为树叶, 记新的扩充满二叉树为 T' 所有原来 T 的结点现在是 T' 的分支结点根据满二叉树定理, 新添加的树叶数目等于 T 结点个数加 1 而每个新添加的树叶对于 T 的一个空子树因此 T 中空子树的数目等于 T 中的结点个数加 1

14 二叉树的主要性质性质 6. 有 n 个结点 (n>0) 的完全二叉树的高度为 log 2 (n+1) ( 深度为 log 2 (n+1) -1) 其中二叉树的高度 (height) 定义为二叉树中层数最大的叶结点的层数加 1 证明 : 假设高度为 h, 则根据性质 2 和完全二叉树的定义, 有 2 h-1 1<n 2 h 1 或 2 h-1 <n+1 2 h 不等式中各项取对数, 于是得到 h 1< log 2 (n+1) h 因为 h 为整数, 所以 h= log 2 (n+1)

15 二叉树的主要性质性质 7. 对于具有 n 个结点的完全二叉树, 结点按层次由左到右编号, 则对任一结点 i(0 i n-1) 有 1. 如果 i=0, 则结点 i 是二叉树的根结点 ; 若 i>0, 则其父结点编号是 (i - 1)/2 2. 当 2i +1 n-1 时, 结点 i 的左子结点是 2i+1; 否则, 结点 i 没有左子结点当 2i+2 n-1 时, 结点 i 的右子结点是 2i+2; 否则, 结点 i 没有右子结点 3. 当 i 为偶数且 0<i<n 时, 结点 i 的左兄弟是结点 i-1, 否则结点 i 没有左兄弟当 i 为奇数且 i+1<n 时, 结点 i 的右兄弟是结点 i+1, 否则结点 i 没有右兄弟

16 二叉树的主要性质证明 : 这里证明 (2),(1) 和 (3) 即可由结论 (2) 推得对于 i=0, 由完全二叉树的定义, 其左孩子的编号是 1, 如果 1>n-1, 即不存在编号为 1 的结点, 此时结点 i 没有左孩子其右孩子的编号只能是 2, 如果 2>n-1, 此时结点 i 没有右孩子对于 i>0 分两种情况讨论 : (1) 设第 j 层的第一个结点编号为 i( 此时有 i = 2 j -1), 则其左孩子必为第 j+1 层的第一个结点, 其编号为 2 j+1-1= 2i+1, 如果 2i+1>n-1, 那么 i 没有左孩子 ; 其右孩子必为第 j+1 层第二个结点, 其编号为 2i + 2 (2) 假设第 j 层的某个结点编号为 i, 若它有左孩子, 那么它的左孩子必然是第 j+1 层中的第 2(i-(2 j -1)) 个, 那么其左孩子的编号就是 (2 j+1-1)+2(i-(2 j -1))=2i+1; 如果结点 i 有右孩子, 那么其右孩子的编号必是 2i + 2

17 2 周游二叉树周游 ( 或称遍历,traversal) 系统地访问数据结构中的结点每个结点都正好被访问到一次二叉树的结点的线性化深度优先周游二叉树广度优先周游二叉树

18 深度优先周游二叉树基于二叉树的递归定义, 三种深度优先周游的递归定义是 : (1) 前序法 (tlr 次序,preorder traversal) 其递归定义是访问根结点 ; 按前序周游左子树 ; 按前序周游右子树 (2) 中序法 (LtR 次序,inorder traversal) 其递归定义是按中序周游左子树 ; 访问根结点 ; 按中序周游右子树 (3) 后序法 (LRt 次序,postorder traversal) 其递归定义是按后序周游左子树 ; 按后序周游右子树 ; 访问根结点

19 深度优先周游二叉树深度周游如下二叉树前序序列是 :A B D E G C F H I 中序序列是 :D B G E A C H F I 后序序列是 :D G E B H I F C A

20 深度优先的非递归算法递归算法非常简洁推荐使用当前的编译系统优化效率很不错了特殊情况用栈模拟递归理解编译栈的工作原理理解深度优先周游的回溯特点有些应用环境不允许递归

21 非递归前序周游二叉树遇到一个结点访问它把右子结点推入栈中下降到左子树周游完左子树从栈顶弹出结点并按照前序访问其子树

22 非递归前序周游二叉树 void preorder(node *root) { Stack<Node*> s; Node *current = root; while (current!= NULL) { visit(current); if (current->right!= NULL) s.push(current->right); if (current->left!= NULL) current = current->left; else if (!s.isempty()) current = s.pop(); else break; } }

23 非递归中序周游二叉树遇到一个结点把它推入栈中周游其左子树周游完左子树从栈顶托出该结点并访问之按照其右链地址周游该结点的右子树

24 非递归中序周游二叉树 void inorder(node *root) { Stack<Node*> s; Node *current = root; while (!s.isempty() current!= NULL) { if (current!= NULL) { s.push(current); current = current->left; } else { current = s.pop(); visit(current); current = current->right; } } }

25 非递归后序周游二叉树遇到一个结点把它推入栈中周游它的左子树左子树周游结束后按照其右链地址周游该结点的右子树周游遍右子树后从栈顶弹出该结点并访问之

26 非递归后序周游二叉树 void postorder(node *root) { Stack<Node*> s; Node *current = root; while (!s.isempty() current!= NULL) { if (current!= NULL) { s.push(current); s.push(current); current = current->left; } else { current = s.pop(); if (!s.isempty() && current == t.top()) current = current->right; else visit(current); } } }

27 思考题 1 设 p q rt, 为二叉树中的三个结点, 其中 rt 为根结点, 求距离结点 p 和结点 q 最近的这两个结点的共同祖先结点递归实现非递归实现

28 思考题 2 表达式二叉树把计算机内部的一棵表达式二叉树, 输出为相应的中缀表达式 ( 可以带括号, 但不允许冗余括号 ) 递归实现非递归实现

29 广度优先周游二叉树从二叉树的第 0 层 ( 根结点 ) 开始, 自上至下逐层遍历 ; 在同一层中, 按照从左到右的顺序对结点逐一访问例如 :A B C D E F G H I

30 广度优先周游二叉树 void levelorder(node *root) { Queue<Node*> q; q.enqueue(root); while (!q.isempty()) { Node *current = q.dequeue(); visit(current); if (current->left!= NULL) q.enqueue(current->left); if (current->right!= NULL) q.enqueue(current->right); } }

31 二叉树周游算法的代价分析时间在各种周游中, 每个结点都被访问且只被访问一次, 时间代价为 O(n) 如果计算非递归保存入出栈 ( 或队列 ) 时间广度优先, 正好每个结点入 / 出队一次,O(n) 前序中序, 某些结点入 / 出栈一次, 不超过 O(n) 后序周游, 每个结点分别从左右边各入 / 出一次, O(n)

32 二叉树周游算法的代价分析空间最好 O(log n), 最坏 O(n) 深度优先栈的深度与树的高度有关广度优先与树的最大宽度有关

33 3 二叉树的存储结构二叉树的链式存储结构完全二叉树的顺序存储结构

34 二叉树的链式存储结构二叉树的各结点随机地存储在内存空间中, 结点之间的逻辑关系用指针来链接二叉链表指针 left 和 right, 分别指向结点的左子女和右子女 ( 可能为空指针 ) 三叉链表 left info right 指针 left 和 right, 分别指向结点的左子女和右子女, 增加一个父指针 parent left info parent right

35 二叉链表

36 三叉链表

37 寻找父结点 Node* findparent(node *root, Node *current) { Stack<Node*> s; if (root == current) return NULL; Node *p = root; while (p!= NULL) { if (p->left == current p->right == current) return p; if (p->right!= NULL) s.push(p->right); if (p->left!= NULL) p = p->left; else if (!s.isempty()) p = s.pop(); else break; } return NULL; }

38 完全二叉树的顺序存储结构顺序方法存储二叉树把所有结点按照一定的次序顺序存储到一片连续的存储单元使结点在序列中的相互位置反映出二叉树结构的部分信息在存储结构上是线性的, 但在逻辑结构上它仍然是二叉树型结构

39 用数组实现完全二叉树按层次顺序将一棵有 n 个结点的完全二叉树的所有结点从 0 到 n-1 编号, 就得到结点的一个线性序列

40 完全二叉树的下标公式从结点的编号就可以推知其父母子女兄弟的编号当 2i+1<n 时, 结点 i 的左子女是结点 2i+1, 否则结点 i 没有左子女当 2i+2<n 时, 结点 i 的右子女是结点 2i+2, 否则结点 i 没有右子女当 0<i<n 时, 结点 i 的父母是结点 (i-1)/2 当 i 为偶数且 0<i<n 时, 结点 i 的左兄弟是结点 i-1, 否则结点 i 没有左兄弟当 i 为奇数且 i+1<n 时, 结点 i 的右兄弟是结点 i+1, 否则结点 i 没有右兄弟

41 4 二叉搜索树二叉搜索树 (BST) 或者是一颗空树 ; 或者是具有下列性质的二叉树 : 对于任何一个结点, 设其值为 K 则该结点的左子树 ( 若不空 ) 的任意一个结点的值都小于 K; 该结点的右子树 ( 若不空 ) 的任意一个结点的值都大于 K; 而且它的左右子树也分别为 BST BST 的性质 : 按照中序周游将各结点打印出来, 将得到按照由小到大的排列

42 二分搜索树的例子

43 二分搜索树检索性能分析最大检索长度为 log 2 (n+1) =O(lgn) 失败的检索长度是 log 2 (n+1) 或 log 2 (n+1) 也是 =O(lgn)

44 BST 图示

45 二叉搜索树的检索只需检索二个子树之一从根结点开始, 在二叉搜索树中检索值 K 如果根结点储存的值为 K, 则检索结束如果 K 小于根结点的值, 则只需检索左子树如果 K 大于根结点的值, 就只检索右子树一直持续到 K 被找到或者遇上了树叶如果遇上树叶仍没有发现 K, 那么 K 就不在该二叉搜索树中

46 二叉搜索树的插入插入新结点要符合二叉搜索树的定义将新结点的关键码值与树根的关键码值比较, 若新关键码值小于树根的关键码值, 则进入左子树, 否则进入右子树在子树里又与子树根比较, 如此进行下去, 直到把新结点插入到二叉树里作为一个新的树叶

47 二叉搜索树的生成过程对于关键码集合 K={50,19,35,55,20,5,100,52,88,53,92}

48 二叉搜索树的结点插入算法 void insertnode(bintree *tree, Node *newnode) { Node *pointer; if (tree->root == null) { tree->root = newnode; return; } else pointer = tree->root; while (pointer!= NULL) {... // 见下一页 } }

49 二叉搜索树的结点插入算法 if (newnode->value == pointer->value) // 相等则不插入 return; else if (newnode->value < pointer->value) { // 小于则左 if (pointer->left == NULL) { // 左空 pointer->left = newnode; // 插入新结点 return; } else pointer = pointer->left; // 向左下降 } else { // 若待插入结点大于 pointer 的关键码值 if (pointer->right == NULL) { // 右空 pointer->right = newnode; // 新结点插入空位 return; } else pointer = pointer->right; // 向右下降 }

50 二叉搜索树的删除设 pointer,temppointer 是指针变量, 其中 pointer 表示要删除的结点首先找到待删除的结点 pointer, 删除该结点的过程如下 : 若结点 pointer 没有左子树, 则用 pointer 右子树的根代替被删除的结点 pointer; 若结点 pointer 有左子树, 则在左子树里找到按中序周游的最后一个结点 temppointer, 把 temppointer 的右指针置成指向 pointer 的右子树的根, 然后用结点 pointer 左子树的根代替被删除的结点 pointer

51 二叉搜索树的删除删除 52 删除 55

52 二叉搜索树的删除算法 void deletenode(bintree *tree, Node *pointer) { Node *newp, *parent; if (pointer == NULL) return; newp = removenode(pointer); parent = findparent(tree->root, pointer); if (parent!= NULL) { if (parent->left == pointer) parent->left = newp; else parent->right = newp; } else if (pointer == tree->root) { tree->root = newp; } delete pointer; }

53 删除算法 ( 未优化版 ) void removenode(node *pointer) { Node *p; if (pointer->left == NULL) // 左子树为空返回右子树 return pointer->right; if (pointer->right == NULL) // 右子树为空返回左子树 return pointer->left; // 两个子树都非空, 把右子树插入左子树, 返回左子树 p = pointer->left; while (p->right!= NULL) p = p->right; p->right = pointer->right; return pointer->left; } 存在的问题 : 树的高度可能增加!

54 二叉搜索树的删除算法优化改进的二叉搜索树结点删除算法的思想为 : 若结点 pointer 没有左子树, 则用 pointer 右子树的代替被删除的结点 pointer 若结点 pointer 有左子树, 则在左子树里找到按中序周游的最后一个结点 temppointer( 即左子树中的最大结点 ) 并将其从二叉搜索树里删除由于 temppointer 没有右子树, 删除该结点只需用 temppointer 的左子树代替 temppointer, 然后用 temppointer 结点代替待删除的结点 pointer

55 删除算法 ( 不增加树高度 ) void removenode(node *pointer) { Node *p, *pp; if (pointer->left == NULL) // 左子树为空返回右子树 return pointer->right; if (pointer->right == NULL) // 右子树为空返回左子树 return pointer->left; // 两个子树都非空, 用左子树中序周游最后一个节点代替删除节点 pp = p = pointer->left; while (p->right!= NULL) pp = p, p = p->right; if (pp == p) { // 中序周游最后一个节点是左子树的根 p->right = pointer->right; } else { // 最后一个节点只有左子树 pp->right = p->left; p->left = pointer->left; p->right = pointer->right; } return p; }

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用