数据结构_王红梅_第5章树和二叉树.ppt

树的逻辑结构 树的存储结构 二叉树的逻辑结构 二叉树的存储结构及实现 二叉树遍历的非递归算法 树、森林与二叉树的转换 哈夫曼树和哈夫曼编码;树的定义; ;树的应用举例——文件结构;树的基本术语;5.1 树的逻辑结构; 孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点； 兄弟：具有同一个双亲的孩子结点互称为兄弟。 ; 路径：如果树的结点序列n1, n2, …, nk有如下关系：结点ni是ni+1的双亲（1=ik），则把n1, n2, …, nk称为一条由n1至nk的路径； 路径上经过的边的个数称为路径长度。 ;祖先、子孙：在树中，如果有一条路径从结点x到结点y，则x称为y的祖先，而y称为x的子孙。; 结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。 树的深度：树中所有结点的最大层数，也称高度。; ;有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。; ;树结构和线性结构的比较;树的抽象数据类型定义;InitTree 前置条件：树不存在 输入：无 功能：初始化一棵树 输出：无 后置条件：构造一个空树 DestroyTree 前置条件：树已存在 输入：无 功能：销毁一棵树 输出：无 后置条件：释放该树占用的存储空间 ; PreOrder 前置条件：树已存在 输入：无 功能：前序遍历树 输出：树的前序遍历序列 后置条件：树保持不变 PostOrder 前置条件：树已存在 输入：无 功能：后序遍历树 输出：树的后序遍历序列 后置条件：树保持不变 endADT;树的遍历操作 ;前序遍历 ;后序遍历 ;层序遍历 ;5.2 树的存储结构;双亲表示法;template class DataType struct PNode { DataType data; //数据域 int parent; //指针域，双亲在数组中的下标 } ;;下标 data parent;5.2 树的存储结构;下标 data parent;链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。 ;5.2 树的存储结构;链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。 ;5.2 树的存储结构;孩子链表表示法;child next; ; ;双亲孩子表示法;孩子兄弟表示法;template class DataType struct TNode { DataType data; TNode DataType *firstchild, *rightsib; };;5.2 树的存储结构;5.2 树的存储结构;二叉树的定义 ;二叉树的特点;二叉树的基本形态;5.3 二叉树的逻辑结构;特殊的二叉树;满二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。;满二叉树; ;在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。;1. 叶子结点只能出现在最下两层且最下层的叶子结点都集中在二叉树的左面； 2. 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。 3. 深度为k的完全二叉树在k-1层上一定是满二叉树。 4. 在同样结点个数的二叉树中，完全二叉树的深度最小。 ;二叉树的基本性质 ;性质5-2 一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。 ;性质5-3 在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0＝n2＋1。 ;5.3 二叉树的逻辑结构;性质5-4 具有n个结点的完全二叉树的深度为 log2n +1。 ;5.3 二叉树的逻辑结构;性质5-5 对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1≤i≤n）的结点（简称为结点i），有： （1）如果i＞1，则结点i的双亲结点的序号为 i/2；如果i＝1，则结点i是根结点，无双亲结点。 （2）如果2i≤n，则结点i的左孩子的序号为2i； 如果2i＞n，则结点i无左孩子。 （3）如果2i+1≤n，则结点i的右孩子的序号为2