国家级精品课程—《数据结构与算法》 第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 二叉树的五种基本形态