北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第四章 二叉树

数据结构与算法 第四章二叉树 张铭 http://db.pkuedu.cn/mzhang/ds/ 北京大学信息科学与技术学院 数据结构与算法”教学小组 版权所有,转载或翻印必究

数据结构与算法 第四章 二叉树 张铭 http://db.pku.edu.cn/mzhang/DS/ 北京大学信息科学与技术学院 “数据结构与算法 ”教学小组 ©版权所有，转载或翻印必究

主要内容 41二叉树的概念 42二叉树的主要性质 43二叉树的抽象数据类型 4.4周游二叉树 45二叉树的实现 46二叉搜索树 47堆与优先队列 48 Huffman编码树 北京大学信息学院张铭编写 @版权所有,转载或翻印必究

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 2 主要内容 „ 4.1 二叉树的概念 „ 4.2 二叉树的主要性质 „ 4.3 二叉树的抽象数据类型 „ 4.4 周游二叉树 „ 4.5 二叉树的实现 „ 4.6 二叉搜索树 „ 4.7 堆与优先队列 „ 4.8 Huffman编码树

41二叉树的概念 411二叉树的定义及相关概念 4.12满二叉树 完全二叉树 扩充二叉树 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 Page 3

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 3 4.1 二叉树的概念 „ 4.1.1 二叉树的定义及相关概念 „ 4.1.2 满二叉树 完全二叉树 扩充二叉树

二叉树的定义 树的特例 递归的定义:二叉树由结点的有限集合构成 或者为空集 或者由一个根结点及两棵不相交的分别称作这个根的左 子树和右子树的二叉树(它们也是结点的集合)组成 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 Page 4

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 4 二叉树的定义 „ 树的特例 „ 递归的定义：二叉树由结点的有限集合构成: „ 或者为空集 „ 或者由一个根结点及两棵不相交的分别称作这个根的左 子树和右子树的二叉树(它们也是结点的集合)组成

二叉树的五种基本形态 二叉树可以是空集合,因此根可以有空的左子 树或右子树,或者左右子树皆为空 (b)独根(空右()空左(e)左右都不 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 Page 5

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 二叉树的五种基本形态 (a)空 (b)独根 (c)空右 (d)空左 (e)左右都不空 „ 二叉树可以是空集合，因此根可以有空的左子 树或右子树，或者左右子树皆为空

二叉树的相关术语 结点 根结点、子结点、父结点、左 子结点、右子结点 分支结点、叶结点 边 路径、路径长度 B 祖先、后代 深度、高度、层数、宽度 E F 二叉树的高度定义为二叉树中 层数最大的叶结点的层数加1 二叉树的深度定义为二叉树中 GO 层数最大的叶结点的层数 H 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 Page 6

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 二叉树的相关术语 „ 结点 „ 根结点、子结点、父结点、左 子结点、右子结点 „ 分支结点、叶结点 „ 边 „ 路径、路径长度 „ 祖先、后代 „ 深度、高度、层数、宽度 „ 二叉树的高度定义为二叉树中 层数最大的叶结点的层数加1 „ 二叉树的深度定义为二叉树中 层数最大的叶结点的层数 H G E A B C D F I

满二叉树 如果一棵二叉树的任何结点,或者是树叶 或者恰有两橾非空子树,则此二叉树称作 满二叉树 Q B E F GH I 北京大学信息学院张铭编写 @版权所有,转载或翻印必究

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 满二叉树 „ 如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作 满二叉树 A B C D E F G H I 树叶 两棵非空子树

完全二叉树 最多只有最下面的两层结点度数可以小于2 最下一层的结点都集中最左边 B C B E F E FgHIJK 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 Page 8

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 完全二叉树 A B G C A B C F G D E I J L D E F H K „ 最多只有最下面的两层结点度数可以小于2 „ 最下一层的结点都集中最左边

扩充二叉树 所有空子树,都增加空树叶 xa wan ZO wi yo zom wIm wen xul yum wu xem yon ZI 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 Page 9

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 扩充二叉树 „ 所有空子树，都增加空树叶 wen wim xul yum wul xal wan zol wil yo zom xem yon zi

扩充二叉树 ■扩充二叉树是满二叉树 新增加的空树叶(外部结点)的个数等于原来二叉树 的结点(内部结点)个数加1 ■路径长度 ■外部路径长度E从扩充的二叉树的根到每个外部 结点的路径长度之和 内部路径长度I扩充的二叉树里从根到每个内部 结点的路径长度之和 ·E和两个量之间的关系为E=I+2n 北京大学信息学院 张铭编写 版权所有,转载或翻印必究

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 扩充二叉树 „ 扩充二叉树是满二叉树 „ 新增加的空树叶(外部结点)的个数等于原来二叉树 的结点(内部结点)个数加1 „ 路径长度 „ 外部路径长度E 从扩充的二叉树的根到每个外部 结点的路径长度之和 „ 内部路径长度I 扩充的二叉树里从根到每个内部 结点的路径长度之和 „ E和I两个量之间的关系为 E=I+2n