《数据结构》 第六章上)
《 数据结构》 第六章(上)
第六章树和二叉树 数据结构 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