合取学院 第7章二叉树及其应用 HEFEI UNIVERSITY 第7章二叉树及其应用 r7.1二叉树的概念 7.2二叉树的存储 7.3二叉树的遍历 7.4线索二叉树 7.5二叉树的应用1一基本算法 7.6二叉树的应用2一—哈夫曼树 7.7二叉树的应用3一二叉排序树 7.8二叉树的应用3一堆和堆排序 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第7章 二叉树及其应用 1 ☞7.1 二叉树的概念 7.2 二叉树的存储 7.3 二叉树的遍历 7.4 线索二叉树 7.5 二叉树的应用1—基本算法 7.6 二叉树的应用2—哈夫曼树 7.7 二叉树的应用3—二叉排序树 7.8 二叉树的应用3—堆和堆排序 第7章 二叉树及其应用
⑧合取学院 第7章二叉树及其应用 HEFEI UNIVERSITY 7.1二叉树的概念 m7.1.1什么是二叉树 7.1.2特殊的二叉树 7.1.3二叉树的性质 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第7章 二叉树及其应用 2 ☞7.1.1 什么是二叉树 7.1.2 特殊的二叉树 7.1.3 二叉树的性质 7.1 二叉树的概念
合取警院 第7章二叉树及其应用 HEFEI UNIVERSITY 叉树的定义 二叉树是由n(n≥0)个结点组成的有限集合，其中： ①当n=0时为空树： ②当>0时，有且仅有一个特定的结点，称为二叉 树的恨，其余结点可分为2个互不相交的子集，其中每 一个子集本身又是一裸二叉树，分别称为左子树和右子 树 B G 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071120)
第7章 二叉树及其应用 3 二叉树的定义 二叉树是由n(n≥0)个结点组成的有限集合，其中： ① 当n＝0时为空树； ② 当n＞0时，有且仅有一个特定的结点，称为二叉 树的根，其余结点可分为2个互不相交的子集，其中每 一个子集本身又是一棵二叉树，分别称为左子树和右子 树。 A B C D E F G H I J
⑧合雕学院 第7章二叉树及其应用 HEFEI UNIVERSITY 二叉树的形态 空树 单结点二叉树 右子树不空的 左子树不空的 二叉树 二叉树 左右子树均不空的二叉树 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第7章 二叉树及其应用 4 二叉树的形态 空树 单结点二叉树 A Ø 右子树不空的 二叉树 Ø 左子树不空的 二叉树 左右子树均不空的二叉树
⑧合飞学院 第7章二叉树及其应用 HEFEI UNIVERSITY 二叉树的基本术语： 父结点：若一个结点有子树，则该结点为父结点（也称 双亲结点)。 孩子结点：若某结点有左子树，则其左子树的根为该结 点的左孩子：若其有右子树，则其右子树的根为该结点 的右孩子。 ④ 结点A为结点B、C的父结点 B B为A的左孩子 C是A的右孩子： 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007~11一20)
第7章 二叉树及其应用 5 二叉树的基本术语： 父结点：若一个结点有子树，则该结点为父结点（也称 双亲结点）。 孩子结点：若某结点有左子树，则其左子树的根为该结 点的左孩子；若其有右子树，则其右子树的根为该结点 的右孩子。 A B C D E F G H I J 结点A为结点B、C的父结点 B为A的左孩子， C是A的右孩子；
合取警院 第7章二叉树及其应用 HEFEI UNIVERSITY 兄弟结点：同一个结点的孩子 延伸父子关系可得到祖先结点和后代结点关系。 层次：根结点的层次为1，其余结点的层次是其父结点 的层次加1 高度（深度）：二叉树中结点的最大层次数。 B 该二叉树的深度为4： E 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(200711一20)
第7章 二叉树及其应用 6 兄弟结点：同一个结点的孩子。 延伸父子关系可得到祖先结点和后代结点关系。 层次：根结点的层次为1，其余结点的层次是其父结点 的层次加1。 高度（深度）：二叉树中结点的最大层次数。 A B C D E F G H I J 该二叉树的深度为4；
⊙合雕学院 第7章二叉树及其应用 HEFEI UNIVERSITY 度：一个结点的孩子数目是这个结点的度。 叶子结点：度为0的结点。 二叉树的度：二叉树中结点的最大的度。 A、B、C的度均为2； B E、F、G的度均为1； D D、H、I、J的度为0. 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20)
第7章 二叉树及其应用 7 度：一个结点的孩子数目是这个结点的度。 叶子结点：度为0的结点。 二叉树的度：二叉树中结点的最大的度。 A B C D E F G H I J A、B、C的度均为2； E、F、G的度均为1； D、H、I、J的度为0
⑧合飞学院 第7章二叉树及其应用 HEFEI UNIVERSITY 注意：对于结点数>1的二叉树，有且仅有一个结点 为二叉树的根，其余结点均为孩子结点，且有左右之 分一左孩子、右孩子。 例：具有三个结点的二叉树 A A B 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007-11一20)
第7章 二叉树及其应用 8 注意：对于结点数>1的二叉树，有且仅有一个结点 为二叉树的根，其余结点均为孩子结点，且有左右之 分——左孩子、右孩子。 例：具有三个结点的二叉树 A B C B A C A B C A B C C A B
合取警院 第7章二叉树及其应用 HEFEI UNIVERSITY 总结：二叉树的逻辑结构 (1)二叉树中任一结点（除根结点外）只有一个 父结点 (2)二叉树中任一结点（除叶子结点外）最多有2 个孩子结点： (3)结点间为非线性关系。 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(2007-1120)
第7章 二叉树及其应用 9 总结：二叉树的逻辑结构 （1）二叉树中任一结点（除根结点外）只有一个 父结点； （2）二叉树中任一结点（除叶子结点外）最多有2 个孩子结点； （3）结点间为非线性关系
⑧ 合取学院 第7章二叉树及其应用 HEFEI UNIVERSITY 7.1二叉树的概念 7.1.1什么是二叉树 r7.1.2两种特殊的二叉树 7.1.3二叉树的性质 合肥学院计算机科学与技术系“数据结构与算法”课程建设组(20071山20) 10
第7章 二叉树及其应用 10 7.1.1 什么是二叉树 ☞7.1.2 两种特殊的二叉树 7.1.3 二叉树的性质 7.1 二叉树的概念