数据结构课件 树和二叉树 1、第六章树和二叉树 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 森林与二叉树的转换 16.4.3 树和森林的遍历 6.6 赫夫曼树及其应用 6.6.1 最优二叉树〔赫夫曼树〕6.6.2 赫夫曼编码 2v 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它特别类似于自然界中的树。树结构在客观世界里是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的 2、应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。36.1 树的定义和基本术语 v 定义：树(Tree)是 n(n=0)个结点的有限集T，T 为空时称为空树，否则它满足如下两个条件：〔1〕有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为 m(m=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为根的子树(Subtree)。4v 树的基本概念：结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥 3、有的子树数叶子(leaf)——度为 0 的结点称为叶子或终端结点。非终端结点——度不为 0 的结点称为非终端结点或分支结点。5vv 孩子(child)——结点子树的根称为该结点的孩子。相应地，该结点称为孩子的双亲。双亲(parents)——若结点 X 有子女 Y，则 X 为 Y 的双亲结点。兄弟(sibling)——同一个双亲的孩子之间互称兄弟。6v 子孙结点——以某结点为根的子树中的任一结点都称为该结点的子孙。v 结点的祖先是从根到该结点所经分支上的全部结点。v 树的度——一棵树中最大的结点度数 v 结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……7v 深度(de 4、pth)——树中结点的最大层次数 v 森林(forest)——m(m?0)棵互不相交的树的集合 v 有序树——若一棵树中全部子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。v 无序树——若一棵树中全部子树的次序无关紧要，则称为无序树。8ABCDEFGHIJKLM 结点 A 的度：3 结点 B 的度：2 结点 M 的度：0 叶子：K，L，F，G，M，I，J 结点 A 的孩子：B，C，D 结点...
