第六章树和二叉树总结.ppt

An Introduction to Data Structure 黑龙江科技学院计算机系 第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树（重点内容） 6.3 遍历二叉树和线索二叉树 （重点内容、难点内容） 6.4 树和森林 6.5 不讲 6.6 赫夫曼树及其应用（重点内容） 树的定义：树(tree)是n(n ? 0)个结点的有限集。 在任意一棵非空树中： 有且仅有一个特定的结点，称为树的根(root) 当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，并且称为根的子树(subtree)。 特点（见下页举例）： 树中至少有一个结点——根。 树中各子树是互不相交的集合。 结点(node)——表示树中的元素，包括一个数据元素及若干指向其子树的分支。 结点的度(degree)——结点拥有的子树数。 叶子(leaf)或（终端结点）——度为0的结点。 非终端结点（分支结点） ——度不为0的结点。 内部结点——除根结点之外，分支结点也叫~。 孩子(child)——结点的子树的根称为该结点的孩子 双亲(parent)——孩子结点的上层结点叫该结点的~ 定义 定义：二叉树是另一种树型结构，是由n(n?0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。 特点： 每个结点至多有二棵子树(即不存在度大于2的结点，因而度数只能为0或者1或者2) 二叉树的子树有左、右之分，且其次序不能任意颠倒（有序树） 性质1： 满二叉树 定义： 性质5：如果对一棵有n个结点的完全二叉树（其深度为 +1）的结点按层序编号（从第一层到第 +1层，每层从左到右），则对任一结点i(1?i?n)，有： (1) 如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是?i/2? (2) 如果2in，则结点i无左孩子（其一定无右孩子，故为叶子结点）；如果2i?n，则其左孩子是2i。 (3) 如果2i+1n，则结点i无右孩子；如果2i+1?n，则其右孩子是2i+1。 顺序存储结构 思想：将一棵一般的二叉树想象成一棵完全二叉树。将其不存在的结点补上，并假设结点的值为0。 实现：按完全二叉树的结点层次编号，依次存放二叉树中的数据元素。即用一组地址连续的存储单元（一维数组）依次自上而下、自左至右存储完全二叉树上的结点元素。 链式存储结构（常用） 二叉链表 遍历二叉树（Traversing Binary Tree） 应用：在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。 遍历——按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义很广，可以是对结点做各种处理，如输出结点信息等。 遍历的本质即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列。 算法（此页一般略过不讲） 递归算法 树的存储结构（三种表示方法） 双亲表示法（顺序存储结构） 实现：定义结构数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难（需要遍历整个结构） 孩子表示法 采用多重链表：由于树中每个结点可能有多棵子树，采用多重链表，即每个结点有多个指针域，分别指向其子树的根结点，链表中结点有以下两种结点格式： 结点同构：结点的指针个数相等， D为树的度 孩子兄弟表示法（又称二叉树表示法或二叉链表表示法） 注：和二叉树的二叉链表表示法十分相象，属于链式存储结构 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。 特点： 操作容易 破坏了树的层次 将森林中各棵树分别转换成二叉树 将后续每棵树转换成的二叉树依次作为前面转换成的二叉树的右子树，最终连接成为一棵整体二叉树，从而实现转换。 树的遍历 常用方法 先根（次序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树 后根（次序）遍历：先依次后根遍历每棵子树，然后访问根结点 按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点 赫夫曼树(Huffman)——带权路径长度最短的树，又称最优二叉树，有着广泛的实际应用，我们应重点掌握。 引入定义： 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的~。 路径长度：路径上的分支数目。 树的路径长度：从树根到每一个结点的路径长度之和。 构造Huffman树的方法——Huffman算法 构造Huffman树步骤 根据给