数据结构－第06章－树和二叉树_01.pptVIP

计算机控制系统 第一讲 第六章 树和二叉树 实例：食物的分类 第六章 树和二叉树 第六章 树和二叉树 6.1 树的定义和基本概念 6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.6 Huffman树及其应用 6.6.1 Huffman树 6.6.2 Huffman编码 第六章 树和二叉树 主要内容及基本要求 1、主要内容 树的定义和基本术语（6.1节） 二叉树及其存储结构（6.2节） 遍历二叉树（6.3.1节） 哈夫曼树（6.6节） 2、基本要求 掌握二叉树的结构特征 掌握二叉树的基本操作，特别是遍历算法 学会运用遍历算法实现二叉树的其它操作 掌握Huffman编码方法 6.1 树的定义和基本术语 有序树 子树的次序不能互换 无序树 子树的次序可以互换 森林 互不相交的树的集合 第六章 树和二叉树 6.1 树的定义和基本概念 6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.6 Huffman树及其应用 6.6.1 Huffman树 6.6.2 Huffman编码 6.2 二叉树 二叉树的定义 二叉树(binary tree)是另一种树型结构，它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。 6.2 二叉树 二叉树的形态 插 入 类 InitBiTree(T); Assign(T, e, value); CreateBiTree(T, definition); InsertChild(T, p, LR, c); 查 找 类 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit()); 删 除 类 ClearBiTree(T); DestroyBiTree(T); DeleteChild(T, p, LR); 6.2 二叉树 2、另一方面，二叉树中一度结点有一个孩子，二度 结点有二个孩子，根结点不是任何结点的孩子，因 此， 结点总数为： n = n1 + 2n2 + 1 3、两式相减，得到： n0 = n2 + 1 6.2 二叉树 定义1 满二叉树(Full Binary Tree) 一棵深度为k 且有2k-1个结点的二叉树。 定义2 完全二叉树(Complete Binary Tree) 若设二叉树的高度为h，则共有h层。除第h层外，其它各层(1?h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。 6.2 二叉树 性质4 具有n个结点的完全二叉树的高度 为 ?log2n? + 1 证明：假设深度为k，则根据性质2和完全二叉树的定义有 2k-1-1n≤2k -1 或 2k-1≤n2k 于是k-1≤log2nk 因为k是整数，所以 k = ?log2n? + 1。 6.2 二叉树——二叉树的性质 性质5 如果对一棵有n个结点的完全二叉树(其深度为[log2n]+1)的结点按层序编号(从第1层到第[log2n]+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有 (1)如果i=1，则