北京大学：《数据结构与算法》课程教学资源（PPT课件讲稿）二叉树

点击下载完整版文档（PPT）

文档信息

资源类别：文库
文档格式：PPT
文档页数：162
文件大小：589.5KB
团购合买：点击进入团购

内容简介

◼ 4.1 二叉树的概念 ◼ 4.2 二叉树的主要性质 ◼ 4.3 二叉树的抽象数据类型 ◼ 4.4 周游二叉树 ◼ 4.5 二叉树的实现 ◼ 4.6 二叉搜索树 ◼ 4.7 堆与优先队列 ◼ 4.8 Huffman编码树

刷新页面文档预览

第四章二叉树任课教员:张铭 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)左右都不空

满二叉树如果一棵二叉树的任何结点,或者是树叶, 或者恰有两棵非空子树,则此二叉树称作满二叉树 C B FGⅡI 北京大学信息学院版权所有,转载或翻印必究 Page 6

北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 满二叉树 ◼ 如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树

完全二叉树若一颗二叉树最多只有最下面的两层结点度数可以小于2 最下面一层的结点都集中在该层最左边的若干位置上则称此二叉树为完全二叉树在许多算法和算法分析中都明显地或隐含地用到全二叉树的概念北京大学信息学院版权所有,转载或翻印必究 Page 7

北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 完全二叉树 ◼ 若一颗二叉树 ◼ 最多只有最下面的两层结点度数可以小于2 ◼ 最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树 ◼ 在许多算法和算法分析中都明显地或隐含地用到完全二叉树的概念

完全二叉树 C B oC G DE FGH IJ K 北京大学信息学院版权所有,转载或翻印必究 Page 8

北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 完全二叉树

打充二叉树 ■当二叉树里出现空的子树时,就增加新的、特殊的结点—空树叶对于原来二叉树里度数为1的分支结点,在它下面增加一个空树叶对于原来二叉树的树叶,在它下面增加两个空树叶 ■扩充的二叉树是满二叉树,新增加的空树叶 (外部结点)的个数等于原来二叉树的结点(内部结点)个数加1 北京大学信息学院版权所有,转载或翻印必究 Page 9

北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 扩充二叉树 ◼ 当二叉树里出现空的子树时，就增加新的、特殊的结点——空树叶 ◼ 对于原来二叉树里度数为1的分支结点，在它下面增加一个空树叶 ◼ 对于原来二叉树的树叶，在它下面增加两个空树叶 ◼ 扩充的二叉树是满二叉树，新增加的空树叶 (外部结点)的个数等于原来二叉树的结点(内部结点)个数加1

打充二叉树 wan zol wil yO wen yim xul yu m wu xem yonR 北京大学信息学院版权所有,转载或翻印必究 Page 10

北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 扩充二叉树

共162页，可试读30页，点击继续阅读 ↓↓

刷新页面下载完整文档

VIP每日下载上限内不扣除下载券和下载次数；
按次数下载不扣除下载券；
注册用户24小时内重复下载只扣除一次；
顺序：VIP每日次数-->可用次数-->下载券；

点击下载完整版文档（PPT）

相关文档