第5章树和二叉树剖析.ppt

教学要求 建议学时：8学时 总体要求 了解树的定义和基本术语； 了解树及二叉树的存储结构； 重点掌握二叉树的结构特性及相应的证明方法； 掌握二叉树的各种遍历算法； 掌握树和二叉树之间的转换； 了解最优树的特性； 了解Huffman树、编码的实现及应用。 教学要求 相关知识点 树的常用术语：树、二叉树、完全二叉树、满二叉树、结点、结点的度、树的高度、有序树、无序树、Huffman树等 树及二叉树的存储结构 二叉树的遍历 树和二叉树之间的转换 Huffman树 学习重点 二叉树的存储结构 二叉树的遍历 Huffman树 树的定义和基本术语 树的定义 树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0时，称这棵树为空树。在一棵非树T中： 有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。 若n1，除根结点之外的其余数据元素被分成m（m0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。 树的特点 树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。 树中所有结点可以有零个或多个后继结点。 树的定义和基本术语 树的表示方法 直观表示法 嵌套集合表示法 凹入表示法 广义表表示法 树的定义和基本术语 树的术语 （1）结点：表示树中的元素，包括数据项及若干指向其子树的分支 （2）结点的度。结点所拥有的子树的个数称为该结点的度。 （3）叶结点。度为0的结点称为叶结点，或者称为终端结点。 （4）分枝结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。 （5）孩子、双亲、兄弟。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。 （6）路径、路径长度。如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点（1≤ik）,就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。 树的定义和基本术语 树的术语（续） （7）祖先、子孙。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。 （8）结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。 （9）树的深度。树中所有结点的最大层数称为树的深度。 （10）树的度。树中各结点度的最大值称为该树的度。 （11）有序树和无序树。如果一棵树中结点的各子树丛左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。 （12）森林。零棵或有限棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根结点就变成了森林。 二叉树 二叉树基本概念 二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 二叉树具有五种基本形态 二叉树 满二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上 二叉树 完全二叉树 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。 完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。。 二叉树 二叉树的性质 性质1 一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。 性质2 一棵深度为k的二叉树中，最多具有2k－1个结点。 性质3 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有: n0＝n2＋1。 性质4 具有n个结点的完全二叉树的深度k为 。 二叉树 二叉树的性质 性质5 对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有： （1）如果i1，则序号为i的结点的双亲结点的序号为；如果i＝1，则序号为i的结点是根结点，无双亲结点。 （2）如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2in，则序号为i的结点无左孩子。 （3）如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1n，则序号为i的结点无右孩子。 二叉树的存储结构 顺序存储结构 所谓二叉树的顺序存储，就是用一组连续的存储