第四章二叉树 任课教员:张铭 http://dbpku.edu.cn/mzhang/ds/ zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究
第四章 二叉树 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究
主要内容 41二叉树的概念 42二叉树的主要性质 43二叉树的抽象数据类型 44周游二叉树 45二叉树的实现 4.6二叉搜索树 47堆与优先队列 48 Huffman编码树 北京大学信息学院 版权所有,转载或翻印必究 Page 2
北京大学信息学院 ©版权所有，转载或翻印必究 Page 2 主要内容 ◼ 4.1 二叉树的概念 ◼ 4.2 二叉树的主要性质 ◼ 4.3 二叉树的抽象数据类型 ◼ 4.4 周游二叉树 ◼ 4.5 二叉树的实现 ◼ 4.6 二叉搜索树 ◼ 4.7 堆与优先队列 ◼ 4.8 Huffman编码树
41二叉树的概念 411二叉树的定义及相关概念 412满二叉树 完全二叉树 扩充二叉树 北京大学信息学院 版权所有,转载或翻印必究 Page 3
北京大学信息学院 ©版权所有，转载或翻印必究 Page 3 4.1 二叉树的概念 ◼ 4.1.1 二叉树的定义及相关概念 ◼ 4.1.2 满二叉树 完全二叉树 扩充二叉树
二叉树的定义 二叉树由结点的有限集合构成: 或者为空集 或者由一个根结点及两棵不相交的分别称作这个根的左 子树和右子树的二叉树(它们也是结点的集合)组成 这是个递归的定义。二叉树可以是空集合,因此根 可以有空的左子树或右子树,或者左右子树皆为空 北京大学信息学院 版权所有,转载或翻印必究 Page 4
北京大学信息学院 ©版权所有，转载或翻印必究 Page 4 二叉树的定义 ◼ 二叉树由结点的有限集合构成: ◼ 或者为空集 ◼ 或者由一个根结点及两棵不相交的分别称作这个根的左 子树和右子树的二叉树(它们也是结点的集合)组成 ◼ 这是个递归的定义。二叉树可以是空集合，因此根 可以有空的左子树或右子树，或者左右子树皆为空
二叉树的五种基本形态 (a)空(b)独根(c)空右(d)空左(e)左右都不空 北京大学信息学院 版权所有,转载或翻印必究 Page 5
北京大学信息学院 ©版权所有，转载或翻印必究 Page 5 二叉树的五种基本形态 (a)空 (b)独根 (c)空右 (d)空左 (e)左右都不空