《数据结构》 第六章上)
《 数据结构》 第六章(上)
第六章树和二叉树 数据结构 61树的定义和基本术语 62二叉树 62.1二叉树的定义 62.2二叉树的性质 623二叉树的存储结构 63遍历二叉树与线索二叉树 63.1遍历二叉树 63.2线索二叉树 6.4树和森林 64.1树的存储结构 64.2森林与二叉树的转换 643树和森林的遍历 66赫夫曼树及其应用 66.1最优二叉树(赫夫曼树) 662赫夫曼编码
数据结构 tjm 第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树与线索二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历 6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 赫夫曼编码
数据结构 61树的定义和基本术语 树的定义 树是一类重要的非线性数据结构,是以分支关系 定义的层次结构。 树ree是n(m>=0个结点的有限集T,对于非空树, 其中有且仅有一个特定的结点,称为树的根(roo 当m>1时,其余结点可分为m(m>0)个互不相交的 有限集T1,T2,m,其中每一个集合本身又是 棵树,称为根的子树 (subtree)。每棵子树的根 结点有且仅有一个直接前驱,但可以有0个或多个 直接后继。 树的类型定义参见P118
数据结构 tjm 6.1 树的定义和基本术语 树的定义 树是一类重要的非线性数据结构，是以分支关系 定义的层次结构。 树(tree)是n(n>=0)个结点的有限集T，对于非空树， 其中有且仅有一个特定的结点，称为树的根(root)。 当n>1时，其余结点可分为m(m>0)个互不相交的 有限集T1,T2,……Tm，其中每一个集合本身又是 一棵树，称为根的子树(subtree)。每棵子树的根 结点有且仅有一个直接前驱，但可以有0个或多个 直接后继。 树的类型定义参见P118
数据结构 只有根结点的树 A 有子树的树 A 根 B D E)(PGB①① K 子树
数据结构 tjm A 只有根结点的树 A B C D E F G H I J K L M 有子树的树 根 子树
数据结构 A 树的基本术语 B E F)(G)(H)(I K 结点:包含一个数据元素及若干指向子树的分支。 结点的度:结点子树的个数。 树的度:树中最大的结点度。 叶子结点:也叫终端结点,是度为0的结点。 分枝结点:度不为0的结点。 从根到结点的路径:由从根到该结点所经分支和结 点构成
数据结构 tjm 结点：包含一个数据元素及若干指向子树的分支。 结点的度：结点子树的个数。 树的度： 树中最大的结点度。 叶子结点：也叫终端结点，是度为 0 的结点。 分枝结点：度不为0的结点。 从根到结点的路径：由从根到该结点所经分支和结 点构成。 树的基本术语： A B C D E F G H I J K L M
数据结构 E HI K 孩子结点:结点的子树的根称为该结点的孩子。 双亲结点:B结点是A结点的孩子,则A结点是B结点 的双亲。 兄弟结点:同一双亲的孩子结点。 堂兄结点:同一层上结点 祖先结点:从根到该结点的所经分支上的所有结点。 子孙结点:以某结点为根的子树中任一结点都称为该 结点的子孙
数据结构 tjm 孩子结点：结点的子树的根称为该结点的孩子。 双亲结点：B结点是A结点的孩子，则A结点是B结点 的双亲。 兄弟结点：同一双亲的孩子结点。 堂兄结点：同一层上结点。 祖先结点: 从根到该结点的所经分支上的所有结点。 子孙结点：以某结点为根的子树中任一结点都称为该 结点的子孙。 A B C D E F G H I J K L M
数据结构 B D E F)(G)(H) K 结点的层次:根结点的层定义为1;根的孩子为 第二层结点,依此类推。 树的深度:树中最大的结点层。 有序树:子树有序的树。 无序树:不考虑子树的顺序。 森林:m(m>=0)棵互不相交的树的集合。 树的基本操作分为三大类:查找,插入,删除 (参见P119
数据结构 tjm 结点的层次：根结点的层定义为1；根的孩子为 第二层结点，依此类推。 树的深度：树中最大的结点层。 有序树：子树有序的树。 无序树：不考虑子树的顺序。 森林： m(m>=0)棵互不相交的树的集合。 A B C D E F G H I J K L M 树的基本操作分为三大类：查找，插入，删除 （参见P119）
数据结构 线性结构与树结构的比较: 线性结构: 树 第一个数据元素(无前驱)根结点(无前驱 最后一个数据元素(无后继)多个叶结点(无后继 其它数据元素(一个前驱,树中其它结点(一个 一个后继) 前驱,多个后继)
数据结构 tjm 线性结构与树结构的比较： 线性结构： 第一个数据元素（无前驱） 最后一个数据元素（无后继） 其它数据元素（一个前驱， 一个后继） 树： 根结点（无前驱） 多个叶结点（无后继） 树中其它结点（一个 前驱，多个后继）
数据结构 62二叉树 621二叉树的定义 定义:二叉树是n(n≥0个结点的有限集,它或为 空树(n=0),或由一个根结点和两棵分别称为左子 树和右子树的互不相交的二叉树构成。 特点: 每个结点至多有二棵子树即不存在度大于2的 结点); 叉树的子树有左、右之分,且其次序不能任 意颠倒。 二叉树的类型定义参见P121
数据结构 tjm 6.2 二叉树 6.2.1 二叉树的定义 定义：二叉树是n(n0)个结点的有限集，它或为 空树(n=0)，或由一个根结点和两棵分别称为左子 树和右子树的互不相交的二叉树构成。 特点： 每个结点至多有二棵子树(即不存在度大于2的 结点)； 二叉树的子树有左、右之分，且其次序不能任 意颠倒。 二叉树的类型定义参见P121
数据结构 二叉树的五种基本形态 A A A A B B B C 只有根结点 左、右子树 空二叉树的二叉树右子树为空左子树为空均非空 二叉树的基本操作也分为三大类:查找,插入, 删除(参见P121)
数据结构 tjm 二叉树的五种基本形态 A 只有根结点 的二叉树 空二叉树 A B 右子树为空 A B 左子树为空 A B C 左、右子树 均非空 二叉树的基本操作也分为三大类：查找，插入， 删除（参见P121）