第五章树和二叉树ss.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层。 树的深度：树中所有结点的最大层数，也称高度。; ;有序树、无序树：如果??棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。; ;同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。;树结构和线性结构的比较;树的遍历操作 ;前序遍历 ;后序遍历 ;层序遍历 ;5.2 树的存储结构;双亲表示法;template class T struct PNode{ T data; //数据域 int parent; //指针域，双亲在数组中的下标 } ;;下标 data parent;5.2 树的存储结构;下标 data parent;链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。 ;5.2 树的存储结构;链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。 ;5.2 树的存储结构;基本思想： 把每个结点的孩子排列起来，看成是一个线性表，且以单链表存储，则n个结点共有 n 个孩子链表。 这 n 个单链表共有 n 个头指针，这 n 个头指针又组成了一个线性表。 为了便于进行查找采用顺序存储。 最后，将存放 n 个头指针的数组和存放n个结点的数组结合起来，构成孩子链表的表头数组。 ; ;child next; ; ; ;孩子兄弟表示法;template class T struct TNode { T data; TNode T *firstchild, *rightsib; };;5.2 树的存储结构;5.2 树的存储结构;树的存储结构小结;二叉树的定义 ;二叉树的特点：;二叉树的基本形态;5.3 二叉树的逻辑结构;特殊的二叉树;满二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。;满二叉树; ;在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。;1. 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部； 2. 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。 3. 深度为k的完全二叉树在k-1层上一定是满二叉树。;二叉树的基本性质 ;性质5-2 一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。 ;性质5-3 在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0＝n2＋1。 ;5.3 二叉树的逻辑结构;性质5-4 具有n个结点的完全二叉树的深度为 log2n +1。 ; ;性质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的右孩子的序号为2i＋1；如果2i＋1＞n，则结点 i无右孩子。 ;1;二叉树的遍历操作 ;二叉树的遍历方式： DLR、LDR、LRD、 DRL、RDL、RLD ;前序（根）遍历 若二叉树为空，则空操作返回；否则： ①访问根结点； ②前序遍历根结点的左子树； ③前序遍历根结点的右子树。;中序（根）遍历 若二叉树为空，则空操作返回；否则： ①中序遍历根结点的左子树； ②访问根结点； ③中序遍历根结点的右子树。 ;后序（根）遍历 若二叉树为空，则空操作返回；否则： ①后序遍历根结点的左子树； ②后序遍历根结点的右子树。 ③访问根结点；;层序遍历 二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到