国家级精品课程—《数据结构与算法》 第5章二叉树 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpkpku.edu.cn/pkujpk/course/siig 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:王腾蛟 版权所有,转载或翻印必究
国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：王腾蛟 ©版权所有，转载或翻印必究 第5章 二叉树
主要内容 5.1二叉树的概念 5.2二叉树的抽象数据类型 5.3二叉树的存储结构 5.4二叉搜索树 5.5堆与优先队列 5.6 Huffman树及其应用 5.7二叉树知识点总结 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 ◼ 5.1 二叉树的概念 ◼ 5.2 二叉树的抽象数据类型 ◼ 5.3 二叉树的存储结构 ◼ 5.4 二叉搜索树 ◼ 5.5 堆与优先队列 ◼ 5.6 Huffman树及其应用 ◼ 5.7 二叉树知识点总结 主要内容
51二叉树的概念 511二叉树的定义及基本术语 5.12满二叉树、完全二叉树、扩充二叉树 513二叉树的主要性质 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 ◼ 5.1.1 二叉树的定义及基本术语 ◼ 5.1.2 满二叉树、 完全二叉树、 扩充二叉树 ◼ 5.1.3 二叉树的主要性质 5.1 二叉树的概念
二叉树的定义 二叉树( binary tree)由结点的有限集合构成,这 个有限集合或者为空集( empty),或者为由一个根 结点(roo)及两棵互不相交、分别称作这个根的 左子树( eft subtree和右子树( right subtree)的二 叉树组成的集合。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树的定义 ◼ 二叉树(binary tree)由结点的有限集合构成，这 个有限集合或者为空集(empty)，或者为由一个根 结点(root)及两棵互不相交、分别称作这个根的 左子树(left subtree)和右子树(right subtree)的二 叉树组成的集合
二叉树的五种基本形态 a)空一又树(b)仅有根的(c)右子树为(d左子树为(e)左右子树均 二叉树空的二叉树空的二叉树非空的二叉树 图51二叉树的五种基本形态 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树的五种基本形态 (a)空二叉树 (b)仅有根的 二叉树 (c)右子树为 空的二叉树 (d)左子树为 空的二叉树 (e)左右子树均 非空的二叉树 图5.1 二叉树的五种基本形态
二叉树相关术语(1) 口二叉树是由唯一的起始结点引出的结点集合。这个起始结点称为根(root) 口二叉树中的任何非根结点都有且仅有一个前驱结点,称之为该结点的父 结点(或称为双亲, parent)。根结点即为二叉树中唯一没有父结点的结点 口二叉树中的任何结点最多可能有两个后继结点,分别称为左子结点(或左 孩子、左子女, left child)和右子结点(或右孩子,右子女, right child), 具有相同父结点的结点之间互称兄弟结点 sibling) 二叉树中结点的子树数目称为结点的度(d egree)。 口没有子结点的结点称为叶结点(leaf,也称“树叶”或“终端结点”), 叶结点的度为0。 口除叶结点以外的那些非终端结点称为内部结点(或分支结点, internal node) 口父结点k与子结点k之间存在一条有向连线,称作边(edge) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树相关术语（1） 二叉树是由唯一的起始结点引出的结点集合。这个起始结点称为根(root) 二叉树中的任何非根结点都有且仅有一个前驱结点，称之为该结点的父 结点(或称为双亲，parent)。根结点即为二叉树中唯一没有父结点的结点 二叉树中的任何结点最多可能有两个后继结点，分别称为左子结点(或左 孩子、左子女，left child)和右子结点(或右孩子，右子女，right child)， 具有相同父结点的结点之间互称兄弟结点(sibling) 二叉树中结点的子树数目称为结点的度(degree)。 没有子结点的结点称为叶结点(leaf，也称“树叶”或“终端结点”)， 叶结点的度为0。 除叶结点以外的那些非终端结点称为内部结点(或分支结点，internal node) 父结点k与子结点k’之间存在一条有向连线，称作边(edge)
二叉树相关术语(2) 口若二又树中存在结点序列{k0,k1,…,ks},使得kO,k1>,,,都是二叉树中的边,则称从结点k0到结点ks存在 一条路径(path),该路径所经历的边的个数称为这条路径的路径长度 ( path length)。若有一条由k到达ks的路径,则称k是ks的祖先( ancestor), ks是k的子孙( descendant) 口断掉一个结点与其父结点的连接,则该结点与其子孙构成的树就称为 以该结点为根的子树( subtree6 口从根结点到某个结点的路径长度称为结点的层数(evel),根结点为第0 层,非根结点的层数是其父结点的层数加1 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树相关术语（2） 若二叉树中存在结点序列{k0，k1，…，ks}，使得，，…，都是二叉树中的边，则称从结点k0到结点ks存在 一条路径(path)，该路径所经历的边的个数称为这条路径的路径长度 (path length)。若有一条由 k到达ks的路径，则称k是ks的祖先(ancestor)， ks是k的子孙(descendant) 断掉一个结点与其父结点的连接，则该结点与其子孙构成的树就称为 以该结点为根的子树(subtree) 从根结点到某个结点的路径长度称为结点的层数(level)，根结点为第0 层，非根结点的层数是其父结点的层数加1
满二叉树与完全二叉树 口如果一棵二叉树的任何结点,或者是树叶,或者恰有两棵非空子树, 则这棵二又树称作满二叉树 full binary tree)) 口如果一棵二叉树最多只有最下面的两层结点度数可以小于2,并且最下 面一层的结点都集中在该层最左边的连续位置上,则此二叉树称作完 全二叉树( (complete binary tree) (A)满二叉树 (b)完全二叉树 图52满二叉树和完全二叉树示例 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 满二叉树与完全二叉树 如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树， 则这棵二叉树称作满二叉树(full binary tree)。 如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下 面一层的结点都集中在该层最左边的连续位置上，则此二叉树称作完 全二叉树(complete binary tree)。 图5.2 满二叉树和完全二叉树示例 A B C D E F G A B D E H I J K C F G L (A)满二叉树 (b)完全二叉树
完全二叉树 口完全二叉树的特点是: 其叶结点只可能在层次最大的两层出现 完全二叉树中由根结点到各个结点的路径长度总和在具 有同样结点个数的二叉树中达到了最小,即任意一棵 二叉树中根结点到各结点的最长路径一定不短于结点 数目相同的完全二叉树中的路径长度 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 完全二叉树 完全二叉树的特点是： ◼其叶结点只可能在层次最大的两层出现 ◼完全二叉树中由根结点到各个结点的路径长度总和在具 有同样结点个数的二叉树中达到了最小，即任意一棵 二叉树中根结点到各结点的最长路径一定不短于结点 数目相同的完全二叉树中的路径长度
扩充二叉树 ■在二叉树里出现空子树的位置增加空树叶,所形成的 二叉树称为扩充二叉树 extended binary tree) ■构造一棵扩充二叉树只需要在原二叉树里度数为1的 分支结点下增加一个空树叶,在原二叉树的树叶下面 增加两个新的空树叶。 扩充二叉树是满二叉树,新增空树叶(以下称为外部 结点)的个数等于原二叉树的结点(以下称为内部结点) 个数加1 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 扩充二叉树 ◼ 在二叉树里出现空子树的位置增加空树叶，所形成的 二叉树称为扩充二叉树(extended binary tree) ◼ 构造一棵扩充二叉树只需要在原二叉树里度数为1的 分支结点下增加一个空树叶，在原二叉树的树叶下面 增加两个新的空树叶。 ◼ 扩充二叉树是满二叉树，新增空树叶(以下称为外部 结点)的个数等于原二叉树的结点(以下称为内部结点) 个数加1