数据结构
数据结构
第六章树和二叉树 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.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赫夫曼编码
6.4.3树和森林的遍历 6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 赫夫曼编码
树型结构是一类重要的非线性结构。树型结 构是结点之间有分支，并且具有层次关系的结构 它非常类似于自然界中的树。树结构在客观世界 国是大量存在的，例如家谱、行政组织机构都可 用树形象地表示。树在计算机领域中也有着广泛 的应用，例如在编译程序中，用树来表示源程序 的语法结构；在数据库系统中，可用树来组织信 息；在分析算法的行为时，可用树来描述其执行 过程。等等。 6.1树的定义和基本术语 定义：树Tree)是n(n>=0)个结点的有限集T,T 为空时称为空树，否则它满足如下两个条件： (1)有且仅有一个特定的称为根(Root)的结点
树型结构是一类重要的非线性结构。树型结 构是结点之间有分支，并且具有层次关系的结构， 它非常类似于自然界中的树。树结构在客观世界 国是大量存在的，例如家谱、行政组织机构都可 用树形象地表示。树在计算机领域中也有着广泛 的应用，例如在编译程序中，用树来表示源程序 的语法结构；在数据库系统中，可用树来组织信 息；在分析算法的行为时，可用树来描述其执行 过程。等等。 6.1 树的定义和基本术语 定义：树(Tree)是n(n>=0)个结点的有限集T，T 为空时称为空树，否则它满足如下两个条件： （1）有且仅有一个特定的称为根(Root)的结点；
(2)其余的结点可分为m(m>=0)个互不相交的子集 T1T2T3TmT1T2,T3.Tm,其中每个子集又是 棵树，并称其为子树(Subtree)。如图6.1 树还有其他的表示形式，如图6.2的三种表示法： (1)嵌套集合(2)广义表的形式(3)凹入表示 法 下面是树结构的一些基本术语： 度：结点拥有的子树称为结点的度。 叶子（终端结点）：度为0的结点。其余结点称为非 终端结点或分支结点。 树的度：树内各结点的度的最大值。 孩子：结点的子树的根称为该结点的孩子。相应地 该结点称为双亲。同一个双亲的孩子称为兄弟。 依此可以递归定义祖先和子孙的概念
(2)其余的结点可分为m(m>=0)个互不相交的子集 T1,T2,T3.Tm T1,T2,T3.Tm，其中每个子集又是一 棵树，并称其为子树(Subtree)。如图6.1 树还有其他的表示形式，如图6.2的三种表示法： （1）嵌套集合（2）广义表的形式（3）凹入表示 法 下面是树结构的一些基本术语： 度：结点拥有的子树称为结点的度。 叶子（终端结点）：度为0的结点。其余结点称为非 终端结点或分支结点。 树的度：树内各结点的度的最大值。 孩子：结点的子树的根称为该结点的孩子。相应地， 该结点称为双亲。同一个双亲的孩子称为兄弟。 依此可以递归定义祖先和子孙的概念