第六章树和二叉树 数据结构 线性结构(线性表栈队列等) 非线性结构:至少存在一个数据元素有不 止一个直接前驱或后继(树图等)
第六章 树和二叉树 数据结构: • 线性结构(线性表, 栈,队列等) • 非线性结构: 至少存在一个数据元素有不 止一个直接前驱或后继(树,图等)
第六章树和二叉树 6.1树的定义和基本概念 62二叉树 621树的定义和基本术语 622二叉树的性质 623二叉树的存储结构 63遍历二叉树 631遍历二叉树 632线索二叉树 64树和森林 64.1树的存储结构 642森林与二叉树的转换
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 森林与二叉树的转换 第六章 树和二叉树
第六章树和二叉树 643树和森林的遍历 6.6赫夫曼树及其应用 6.6.1最优二叉树(赫夫曼树) 6.62赫夫曼编码 树型结构是一类重要的非线性结构。树型结构是结点之间 有分支,并且具有层次关系的结构,它非常类似于自然界中的 树。树结构在客观世界国是大量存在的,例如家谱、行政组织 机构都可用树形象地表示。树在计算机领域中也有着广泛的应 用,例如在编译程序中,用树来表示源程序的语法结构;在数 据库系统中,可用树来组织信息;在分析算法的行为时,可用 树来描述其执行过程。等等
6.4.3树和森林的遍历 6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 赫夫曼编码 第六章 树和二叉树 树型结构是一类重要的非线性结构。树型结构是结点之间 有分支，并且具有层次关系的结构，它非常类似于自然界中的 树。树结构在客观世界国是大量存在的，例如家谱、行政组织 机构都可用树形象地表示。树在计算机领域中也有着广泛的应 用，例如在编译程序中，用树来表示源程序的语法结构；在数 据库系统中，可用树来组织信息；在分析算法的行为时，可用 树来描述其执行过程。等等
第六章树和二叉树 §6.1树的定义 树(tree)是n个数据元素的有限集(记为 T),对任意一棵树T有: 1.存在唯一一个称为根(r0Ot)的数据元素; 2当n>1时,其它数据元素可分为m(m>0) 个互不相交的有限集T,T2,…,Tm,其中每个 集合T;(i=1,2,…m)本身又是一棵树,并称 树T是根的子树( subtree)
第六章 树和二叉树 §6.1 树的定义 树(tree)是n个数据元素的有限集(记为 T)，对任意一棵树T有： ⒈ 存在唯一一个称为根(root) 的数据元素； ⒉ 当n＞1时，其它数据元素可分为m(m＞0) 个互不相交的有限集T1,T2,•…,Tm，其中每个 集合Ti(i=1,2,…,m)本身又是一棵树，并称 树 Ti是根的子树(subtree)
第六章树和二叉树 树的表示法 1.分支图表示法 2.嵌套集合表示法 3.广义表表示法 (A(B) C)
第六章 树和二叉树 树的表示法 1. 分支图表示法 2. 嵌套集合表示法 A B C D A B C D 3. 广义表表示法 (A(B(D),C))