数据结构第6章树和二叉树.ppt

数据结构第 6 章树和二叉树.ppt 1、第六章树和二叉树 6.1 树的类型定义 6.2 二叉树的类型定义和实现 6.3遍历二叉树和线索二叉树 6.4 树和森林 6.5Huffman 树与 Huffman 编码 1 对比树型结构和线性结构的结构特点第一个数据元素(无前驱)最终一个数据元素(无后继)其它数据元素(一个前驱、一个后继)根结点(无前驱)多个叶子结点(无后继)其它数据元素(一个前驱、多个后继)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~26.1 树的类型定义树是 n(n≥0)个结点的有限集 D，当 n≥1 时：1〕有一个特定的结点root 被称为根(结点);2〕除根以外的结点被分成 m(m≥0)个不相交的有限集T1,T2,……,Tm，其中每个集合又是一棵树，称为根的子树。ABCDEFGHIJMKL3 任何一棵非空树是一个二元组 Tree=〔roo 2、t，F〕其中：root 被称为根结点 F 被称为子树森林森林和树之间的联系：一棵树去掉根后，其子树构成一个森林；一个森林增加一个根结点成为树。森林：是 m〔m≥0〕棵互不相交的树的集合。4 定义或为空树，或是由一个根结点和两棵互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。特性二叉树中每个结点最多有两棵子树；二叉树每个结点的度小于等于 2 子树有左右之分，不能颠倒——有序树二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念 6.2 二叉树的类型定义和实现 5 性质 1 在二叉树的第 i 层上至多有 2i-1 个结点。(i≥1)二叉树的重要特性性质 2 深度为 k 的二叉树上至多含2k-1 个结点(k≥1)性质 3 对任何一棵二叉树，若它含有 n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。性质 4 具有 3、n 个结点的完全二叉树的深度为log2n +16满二叉树：深度为 k，且有2k-1 个结点的二叉树；特点：每一层上的结点数都是最大数目。结点层序编号方法：从根结点起自上而下逐层〔层内自左至右〕对二叉树的结点进行连续编号。123114589121367101415 两类特别的二叉树：7 完全二叉树：一棵深度为 k有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从1 至 n 的结点一一对应时，称之为完全二叉树。特点：叶子结点只可能在层次数最大的两层上出现。只有最下一层的结点数可能未到达最大值。对任一结点，假如其右子树的最大层次为 L，则其左子树的最大层次为 L 或 L＋1。完全二叉树结点数 2k-1-1n，则该结点无左孩子，否则，编号为 2i 的结点为其...