数据结构-树与二叉树.ppt

Chapter6Tree BinaryTree 教 学 内 容 1 树和森林的概念2 二叉树的定义 性质及运算 3 二叉树的存储结构4 遍历二叉树 树 森林5 森林与二叉树的转换6 哈夫曼树 哈夫曼编码 树型结构 非线性结构 结点之间有分支 具有层次关系 例 自然界 树 人类社会 家谱 院系组织机构 树的概念 树的定义树是n n 0 个结点的有限集 若n 0 称为空树 若n 0 则它满足如下两个条件 有且仅有一个称之为根 Root 的结点 当n 1 除根以外的其它结点分为m m 0 个互不相交的有限集T1 T2 Tm 其中每个集合又是一棵符合本定义的树 并且称为根的子树 例如 A 只有根结点的树 有13个结点的树 A是根 其余数据元素分成三个互不相交的子集 T1 B E F K L T2 C G T3 D H I J M T1 T2 T3都是根A的子树 且本身也是一棵树 根结点 T1 R 树结构和线性结构作如下对照 树的基本术语 结点结点的度叶子结点分支结点 儿子结点父亲结点兄弟结点祖先结点 树的度结点的层次树的深度森林 有序树 子树之间存在确定的次序关系 无序树 子树之间不存在确定的次序关系 家族树就属于有序树 森林 是m m 0 棵互不相交的树的集合 root 给森林中的各子树加上一个父亲结点 森林就变成了树 T3 T2 T1 二叉树或为空树 或是由一个根结点加上两棵分别称为左子树和右子树的 互不交叉的二叉树组成 二叉树 为何要重点研究每结点最多只有两个 叉 的树 二叉树的结构最简单 规律性最强 可以证明 所有树都能转为唯一对应的二叉树 不失一般性 根结点 右子树 左子树 a 空二叉树 b 根和空的左右子树 c 根和左子树 d 根和右子树 e 根和左右子树 注 虽然二叉树与树概念不同 但有关树的基本术语对二叉树都适用 二叉树的五种基本形态 性质1在二叉树的第i层上至多有2i 1个结点 i 1 证明 当i 1时 只有根结点 2i 1 20 1 假设对所有j i j 1 命题成立 即第j层上至多有2j 1个结点 由归纳假设第i 1层上至多有2i 2个结点 二叉树的每个结点的度至多为2 故在第i层上的最大结点数为第i 1层上的最大结点数的2倍 即2 2i 2 2i 1 二叉树的重要特性 性质2深度为k的二叉树至多有2k 1个结点 其中k 1 证明 由性质1可见 深度为k的二叉树的最大结点数为 20 21 2k 1 2k 1 性质3对任何一棵二叉树T 如果其叶子结点数为n0 度为2的结点数为n2 则n0 n2 1 证明 n n0 n1 n2 e n 1 2n2 n1 因此 2n2 n1 n0 n1 n2 1n0 n2 1 满二叉树 FullBinaryTree 定义1 一棵深度为k且有2k 1个结点的二叉树称为满二叉树 两种特殊形态的二叉树 特点 每一层上的结点数都达到最大 叶子全部在最底层 非完全二叉树 完全二叉树 CompleteBinaryTree 若设二叉树的深度为h 除第h层外 其它各层 0 h 1 的结点数都达到最大值 第h层从右向左连续缺若干结点 完全二叉树 性质4具有n n 0 个结点的完全二叉树的深度为 log2 n 1 证明 设完全二叉树的深度为h 则根据性质2和完全二叉树的定义有2h 1 1 n 2h 1 取对数h 1 log2n h 又h是整数因此有h log2 n 1 性质5 若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号 则对完全二叉树中任意一个编号为i的结点 哪个是完全二叉树 1 若i 1 则该结点是二叉树的根 否则 编号为 i 2 的结点为其父亲结点 2 若2i n 则该结点无左孩子 否则 编号为2i的结点为其左孩子结点 3 若2i 1 n 则该结点无右孩子结点 否则 编号为2i 1的结点为其右孩子结点 3 深度为9的二叉树中至少有个结点 9 8 9 1 2 深度为 的二叉树的结点总数 最多为个 k 1 log2k k k 1 树 中各结点的度的最大值称为树 高度 层次 深度 度 D C C 课堂练习 二 二叉树的链式存储表示 一 二叉树的顺序存储表示 6 3二叉树的存储结构 顺序存储表示 用一组地址连续的存储单元存储二叉树中的数据元素 将完全二叉树上编号为i的结点元素存储在一维数组中下标为i 1的分量中 1 2 3 4 5 6 7 10 8 9 1 练习 2 4 1 6 3 5 对于一般的非完全二叉树不能直接使用二叉树的顺序存储结构 可以首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态 然后再用顺序存储结构存储 a 一般二叉树 b 完全二叉树形态 单支树 由于一般二叉树必须仿照完全二叉树那样存储 可能会浪费很多存储空间 单支树就是一个极端情况 链表存储表示 A D E B C F root lchilddatarchild 结点结构 二叉链表 A D E B C F root 三叉链表 parentlchilddatarchild 结点结构 BinaryTreeTraversal 6 3二叉树的遍历 遍历概念 顺着某一条搜索路径巡访二叉树中的结点 使得每个结点均被访问一次 而且仅被访问一次 访问 的含义很广 可以是对结点作各种处理 如 输出结点的信息 修改结点的数据值等 但要求这种访问不破坏原来的数据结构 遍历方法 依次遍历二叉树中的三个组成部分 便是遍历了整个二叉树 假设 L 遍历左子树v 访问根结点R 遍历右子树 则遍历整个二叉树方案共有 遍历目的 得到树中所有结点的一个线性排列 vLR LvR LRv vRL RvL RLv六种 若规定先左后右 则只有前三种情况 vLR 前 根 序遍历 LvR 中 根 序遍历 LRv 后 根 序遍历 前序遍历二叉树的操作定义 若二叉树为空 则空操作 否则 1 访问根结点 2 前序遍历左子树 3 前序遍历右子树 前序遍历 ABC ABELDHMIJ 中序遍历二叉树的操作定义 若二叉树为空 则空操作 否则 1 中序遍历左子树 2 访问根结点 3 中序遍历右子树 中序遍历 BAC ELBAMHIDJ 后序遍历二叉树的操作定义 若二叉树为空 则空操作 否则 1 后序遍历左子树 2 后序遍历右子树 3 访问根结点 后序遍历 BCA LEBMIHJDA a b a b c d e a b c 分析表达式和二叉树的关系 a b a b c a b c a b c a b c d e a b c d e f 例 写出下图二叉树的先序 中序和后序遍历顺序 遍历结果 前序 a b cd ef 中序 a b c d e f 后序 abcd ef 表达式的前缀表示 表达式的中缀表示 表达式的后缀表示 二叉树的类定义 templateclassBinTreeNode 二叉树结点类 private BinTreeNode LChild RChild Typedata public BinTreeNode LChild RChild NULL BinTreeNode constType templateclassBinaryTree 二叉树类 protected BinTreeNode root voidPreOrderHelp BinTreeNode r void Visit constType 先 中 后序遍历 辅助函数 public BinaryTree 建立以r为根的二叉树BinaryTree BinTreeNode r virtual BinaryTree 析构函数BinTreeNode GetRoot const boolEmpty const voidInOrder void Visit constType 二叉树的前序遍历 voidPostOrder void Visit constType 二叉树前序遍历递归算法 templatevoidBinaryTree PreOrderHelp BinTreeNode r void Visit constType templatevoidBinaryTree PreOrder void Visit Type templatevoidwrite constType 二叉树前序遍历非递归算法 templatevoidBinaryTree PreOrder Stack s BinTreeNode p root do while p NULL cout p data Push s p p p LChild if Empty s p pop s p p RChild while Empty s p NULL 二叉树中序遍历非递归算法 templatevoidBinaryTree InOrder BinTreeNode p root Stack s do while p NULL Push s p p p LChild if Empty s p pop s cout p data p p RChild while Empty s p NULL 层次遍历 LevelorderTraversal 从上到下 从左到右遍历结果 a efb cd 二叉树的重建 由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树由二叉树的前序序列和后序序列不可唯一地确定一棵二叉树 仅知二叉树的前序序列 abcdefg 不能唯一确定一棵二叉树 如果同时已知二叉树的中序序列 cbdaegf 则会如何 由二叉树的前序和中序序列建树 二叉树的前序序列 二叉树的中序序列 左子树 左子树 右子树 右子树 根 根 abcdefg cbdaegf a a b b c c d d e e f f g g a b c d e f g 前序序列中序序列 前序序列 ABHFDECKG 中序序列 HBDFAEKCG 二叉树应用事例 templatevoidBinaryTree InsertRightChild BinTreeNode cur constType e成为cur的右孩子 templatevoidBinaryTree InsertLeftChild BinTreeNode cur constType e成为cur的左孩子 intmain void BinTreeNode cur intc cur newBinTreeNode 2 BinaryTreebt cur 建立二叉树c 3 bt InsertLeftChild cur c 插入左孩子cur bt LeftChild cur c 4 bt InsertRightChild cur c 插入右孩子cur bt GetRoot 取出根结点c 6 bt InsertRightChild cur c 插入右孩子return0 6 6树和森林 一 树的存储表示 父亲表示法 孩子表示法 改进 父亲 孩子表示法结合 孩子兄弟表示法 ABCEDFG root 练习 树的遍历 深度优先遍历树的先根次序遍历树的后根次序遍历广度优先遍历树的层次次序遍历 ABCDEFGHIJK 先根遍历 ABEFCDGHIJK 后根遍历 EFBCIJKHGDA 层次遍历 ABCDEFGHIJK BCDEFGHIJK 1 森林中第一棵树的根结点 2 森林中第一棵树的子树森林 3 森林中其它树构成的森林 森林由三部分构成 森林的先根遍历 若森林F为空 返回否则 访问F的第一棵树的根结点 先根次序遍历第一棵树的子树森林 先根次序遍历其它树组成的森林 结果 BEFCDGHIJK 森林的后根遍历 若森林F为空 返回否则 后根次序遍历第一棵树的子树森林 访问F的第一棵树的根结点 后根次序遍历其它树组成的森林 结果 EFBCIJKHGD 森林的层次遍历 若森林F为空 返回否则 依次遍历各棵树的根结点 依次遍历各棵树根结点的所有子女 依次遍历这些子女结点的子女结点 结果 BCDEFGHIJK 森林与二叉树的相互转换 6 7哈夫曼树 HuffmanTree 与哈夫曼编码 结点的路径长度从根结点到该结点的路径上分支的数目 树的路径长度树中每个结点的路径长度之和 树的带权路径长度 WeightedPathLength WPL 树的各叶子结点所带的权值与该结点到根的路径长度的乘积的和 结点的带权路径长度从该结点到到根结点之间的路径长度与结点上权的乘积 在所有含n个叶子结点 并带有各自权值的m叉树中 必存在一棵其带权路径长度取最小值的树 称为 最优树 或 哈夫曼树 HuffmanTree 哈夫曼树中 权值大的结点离根最近 具有不同带权路径长度的二叉树 WPL a 7 2 5 2 2 3 4 3 9 2 60 WPL b 7 4 9 4 5 3 4 2 2 1 89 根据给定的n个权值 w1 w2 wn 造n棵二叉树的集合F T1 T2 Tn 其中每棵二叉树中均只含一个带权值为wi的根结点 其左 右子树为空树 1 构造哈夫曼树 在F中选取其根结点的权值为最小的两棵二叉树 分别作为左 右子树构造一棵新的二叉树 并置这棵新的二叉树根结点的权值为其左 右子树根结点的权值之和 2 从F中删去这两棵树 同时加入刚生成的新树 重复 2 和 3 两步 直至F中只含一棵树为止 3 4 哈夫曼树的构造过程 9 练习 已知权值W 5 6 2 9 7 5 6 2 7 9 2 5 7 16 6 7 13 29 哈夫曼编码 哈夫曼树的应用很广 哈夫曼编码就是其在电讯通信中的应用之一 在电讯通信业务中 通常用二进制编码来表示字母或其他字符 并用这样的编码来表示字符序列 例 如果需传送的电文为 ABACCDA 它只用到四种字符 用两位二进制编码便可分辨 假设A B C D的编码分别为00 01 10 11 则上述电文便为 00010010101100 共14位 译码员按两位进行分组译码 便可恢复原来的电文 能否使编码总长度更短呢 实际应用中各字符的出现频度不相同 数据的最小冗余编码问题 用短 长 编码表示频率大 小 的字符 使得编码序列的总长度最小 使所需总空间量最少 若假设A B C D的编码分别为0 00 1 01 则电文 ABACCDA 便为 000011010 共9位 可译为 BBCCDA ABACCDA AAAACCACA 存在多义性 要求任一字符的编码都不能是另一字符编码的前缀 这种编码称为前缀编码 其实是非前缀码 译码的惟一性问题 利用最优二叉树可以很好地解决上述两个问题 在编码过程要考虑两个问题 数据的最小冗余编码问题 译码的惟一性问题 以电文中的字符作为叶子结点构造二叉树 然后将二叉树中结点引向其左孩子的分支标 0 引向其右孩子的分支标 1 每个字符的编码即为从根到每个叶子的路径上得到的0 1序列 如此得到的即为二进制前缀编码 如此得到的即为二进制前缀编码 用二叉树设计二进制前缀编码 例 编码 A