数据结构5树(精品·公开课件).ppt

树和森林 树和森林的概念 二叉树 二叉树的表示 二叉树遍历 堆 树和森林 赫夫曼树及其应用 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。 树结构应用：家谱、行政组织机构、源程序的语法结构、文件系统、在数据库系统中用树来组织信息。 定义及主要特性 关于树的术语 结点：包含数据的和指向其他节点分支 根结点：只有后继，没有前驱。(A) 节点的度：节点的子树的棵数 叶结点：度数为零的节点。K,L,F, G,M,I,J 分支结点：除叶节点以外的节点。A,B,C, D,E,H 子树：树的一颗分支。 子节点：树的子树的根节点。 父节点：若x有子节点，则x是子节点的父节点。 子孙节点：某节点为根的子树上的所有结点都是它的子孙。 祖先节点：从根节点到某节点的路径上的任意节点都是该节点的祖先。 兄弟节点：有共同的父节点的节点。 层数：节点的层次。（根节点在第1层）结点E,F,G,H,I,J的层数是3，结点A的层数为1 高度：树中节点的最大层次。（空树0，只有根节点1） 树的度：树中所有节点的度的最大值。 路径：从A到B到E到K的这条边形成了一条长度为3的通路。 森林:m颗树的集合 二叉树具有下列重要性质 性质1： 在二叉树的第i层上至多有2i-1 个结点(i=1)。 采用归纳法证明此性质。 性质2：高度为k的二叉树至多有2k－1个结点（k=0). 性质3： 对任何一棵二叉树，如果其叶结点数为n0，度为2的结点数为n2，则n0＝n2＋1。（从两个不同方向数边） 性质4：具有n个节点的完全二叉树的高度为「log2(n+1)︱。（最多最少） 性质5：如果一棵有n个节点的完全二叉树按自然顺序编号，则有如下的关系 1、i0,则i的父节点为︱(i-1)/2」。 2、若2*i+1n,则节点i的左子节点为i*2+1。(基础，证） 3、若2*i+2n,则节点i的右子节点为i*2+2。 4、若i（0)节点为偶数，则它的左兄弟节点为节点i-1。 5、若i(n-1)节点为奇数，则它的右兄弟节点为节点i+1。 6、节点i所在层次为︱log2(i+1) 」+1 二叉树的表示 1、使用数组实现完全二叉树 一般二叉树 优点：存储简单，占用空间少，速度快。 缺点：不能推广应用到一般的二叉树。 二叉链表示：（找父节点困难） 二叉树的二叉链表实现：p194 找父节点的递归有哪些信誉好的足球投注网站算法 递归算法的低效性 二叉树遍历 Traversals 遍历：按照一定顺序访问二叉树的所有结点，每个节点仅访问一次。称为一次遍历 (traversals) 二叉树结点的枚举：对每个结点都进行一次访问并将其列出，称为二叉树结点的枚举(enumeration) 令L、R 、V分别代表左子树、右子树和访问当前节点的操作。 1.前序遍历二叉树（VLR）的操作定义为： 若二叉树为空，则空操作；否则 (1)访问根结点；(2)前序遍历左子树；(3)前序遍历右子树。 2.中序遍历二叉树（LVR）的操作定义为： 若二叉树为空，则空操作；否则 (1)中序遍历左子树；(2)访问根结点；(3）中序遍历右子树。 3.后序遍历二叉树（LRV）的操作定义为： 若二叉树为空，则空操作；否则 (1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。 二叉树遍历的游标类（如何把递归改成非递归，三种+层次游标）（不讲） 线索化二叉树（把二叉树按照某种次序线性化（双向指针串在一起）（考虑插入、删除的情况） 何谓线索二叉树？ 遍历二叉树的结果是，求得结点的一个线性序列。 指向该线性序列中的“前驱”和“后继”的指针，称作“线索” 包含“线索”的存储结构，称作“线索链表”； 与其相应的二叉树，称作“线索二叉树” 最小堆用“filterDown”算法，自下而上的调整而成。 最大堆的算法与最小堆相同，但其中的不等号反向。 “filterDown”算法：两种情况：父节点小于等于两个子节点，不需要调整。父节点大于其中的至少一个子节点。向最小的子节点方向调整。 堆的插入删除算法 堆的插入：先把新节点加到最后面，然后用“filterup”算法向上调整。 删除算法：先把堆顶的元素删除，然后把堆中最后一个元素填补上来，然后用“filterDown”算法调整。 两种算法的时间复杂度（最坏情况）：0（log2n) 树与森林 树的存储表示 1.广义表表示 2.双亲表示 3.孩子链表示 4.双亲-孩子链表示 5.左孩子-右兄弟表示法 树在二叉树表示下的遍历 先根序遍历：对应于二叉树的前序遍历。 后根序遍历：对应于二叉树的中序遍历。 3. 后根遍历 （1）后根遍历第一棵树的根结点的子树； （2）后根遍历访问其他树构成的森林； （3） 访问第一颗树的根节点。 4.广度优先遍历 (层次