数据结构树和二叉树ppt课件.ppt

第6章树和二叉树 本章主题 树 二叉树教学目的 掌握树和二叉树的类型定义 运算及存储结构教学重点 树的各种表示 各种存储方式和运算 二叉树的概念及其运算和应用教学难点 二叉树的非递归运算及应用主要内容 树二叉树树 森林与二叉树的转换树的应用 1 本章学习导读 本章主要介绍树的基本概念 树的存储结构 树和二叉树的遍历等一些常用算法 通过本章学习 读者应该 1 熟练掌握二叉树的各种遍历算法 并能灵活运用遍历算法实现二叉树的其它操作 2 理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法 3 熟练掌握二叉树和树的各种存储结构及建立的算法 4 学会编写实现树的各种操作的算法 5 了解最优二叉树的特性 掌握建立最优二叉树和哈夫曼编码的方法 2 数据结构 线性结构和非线性结构线性结构 线性表 栈 队列等 非线性结构 至少存在一个数据元素有不止一个直接前驱或后继 树 图等 树型结构是一类重要的非线性结构 树型结构是结点之间有分支 并且具有层次关系的结构 它非常类似于自然界中的树 树结构在客观世界国是大量存在的 例如家谱 行政组织机构都可用树形象地表示 树在计算机领域中也有着广泛的应用 例如在编译程序中 用树来表示源程序的语法结构 在数据库系统中 可用树来组织信息 在分析算法的行为时 可用树来描述其执行过程 等等 3 6 1 1树型结构实例1 家族树 6 1树的逻辑结构和存储结构 图6 1家族树 4 2 书的目录结构 图6 2书的目录 5 6 1 2树的定义1 树的定义树 Tree 是n n 0 个结点的有限集 记为T T为空时称为空树 否则它满足以下两个条件 1 有且仅有一个结点没有前驱 称该结点为根结点 Root 2 除根结点以外 其余结点可分为m m 0 个互不相交的有限集合T0 Tl Tm 1 其中每个集合又构成一棵树 树T0 Tl Tm 1被称为根结点的子树 Subree 每棵子树的根结点有且仅有一个直接前驱 但可以有0个或多个后继 树的逻辑结构表示数据之间的关系是一对多 或者多对一的关系 它的结构特点具有明显的层次关系 是一种十分重要的非线性的数据结构 6 1树的逻辑结构和存储结构 6 图6 3树的示例 图6 3 a 是一棵只有一个根结点的树 图6 3 b 是一棵有12个结点的树 即T A B C K L A是棵根 除根结点A之外 其余的11个结点分为三个互不相交的集合 T1 T2和T3是根A的三棵子树 且本身又都是一棵树 所以树的定义是递归的 返回 7 2 树的基本术语树的结点包含一个数据元素及若干指向其子树的分支 1 树的结点 包含一个DE和指向其子树的所有分支 2 结点的度 一个结点拥有的子树个数 度为零的结点称为叶结点 3 树的度 树中所有结点的度的最大值Max D I 含义 树中最大分支数为树的度 4 结点的层次及树的深度 根为第一层 根的孩子为第二层 若某结点为第k层 则其孩子为k 1层 树中结点的最大层次称为树的深度或高度5 森林 是m m 0 棵互不相的树的集合森林与树概念相近 相互很容易转换 6 有序树 无序树如果树中每棵子树从左向右的排列拥有一定的顺序 不得互换 则称为有序树 否则称为无序树 8 7 森林 是m m 0 棵互不相交的树的集合 在树结构中 结点之间的关系又可以用家族关系描述 定义如下 8 孩子 双亲 结点子树的根称为这个结点的孩子 而这个结点又被称为孩子的双亲 9 子孙 以某结点为根的子树中的所有结点都被称为是该结点的子孙 10 祖先 从根结点到该结点路径上的所有结点 11 兄弟 同一个双亲的孩子之间互为兄弟 12 堂兄弟 双亲在同一层的结点互为堂兄弟 9 3 树的基本运算树的基本运算主要有 初始化操作INITIATE T 创建一棵空树 求根函数ROOT T 求树T的根 ROOT X 求结点x所在树的根 求双亲函数PARENT T x 在树T中求x的双亲 求第i个孩子函数CHILD T x i 在树T中求结点x的第i个孩子 建树函数CRT TREE x F 建立以结点x为根 森林F为子树的树 6 遍历树操作TRAVERSE T 按顺序访问树T中各个结点 10 6 1 3树的表示树的逻辑表示方法有多种 常见的有 1 树形图表示法2 嵌套集合表示法 文氏图表示法 3 凹入表示法4 广义表表示法 11 6 1 3树的存储结构和线性表一样 树可以用顺序和链式两种存储结构 树的顺序存储结构适合树中结点比较 满 的情况 根据树的非线性结构特点 常用链式存储方式来表示树 树常用的存储方法有 双亲存储表示法 孩子链表表示法和孩子兄弟链表表示法 1 双亲存储表示法一般采用顺序存储结构实现 用一组地址连续的存储单元来存放树的结点 每个结点有两个域 data域 存放结点的信息 parent域 存放该结点双亲结点的位置 特点 求结点的双亲很容易 但求结点的孩子需要遍历整个向量 12 存储结构描述为 defineMaxTreeSize100 定义数组空间的大小typedefcharDataType 定义数据类型typedefstruct DataTypedata 结点数据intparent 双亲指针 指示结点的双亲在数组中的位置 PTreeNode typedefstruct PTreeNodenodes MaxTreeSize intn 结点总数 PTree PTreeT T是双亲链表 13 2 孩子链表表示法这是树的链式存储结构 每个结点的孩子用单链表存储 称为孩子链表 n个结点可以有n个孩子链表 叶结点的孩子链表为空表 n个孩子链表的头指针用一个向量表示 图6 6树的孩子链表结构 头指针向量孩子链表 特点 与双亲相反 求孩子易 求双亲难 14 存储结构描述为 typedefstructCTNode intchild 孩子链表结点structCTNode next ChildPtr typedefstruct 孩子链表头结点 ElemTypedata 结点的数据元素ChildPtrfirstchild 孩子链表头指针 CTBox typedefstruct CTBoxnodes MaxTreeSize intn r 数的结点数和根结点的位置 CTree 15 孩子链表表示法的类型说明typedefstructCnode DataType和MaxTreeSize由用户定义 孩子链表结点intchild 孩子结点在数组中对应的下标structCNode next Cnode typedefstruct 孩子链表头结点 DataTypedata 存放树中结点数据CNode firstchild 孩子链表的头指针 PTNode typedefstruct PTNodenodes MaxTreeSize Intn root 树的结点数和根结点的位置 Ctree CtreeT T的孩子链表表示 16 3 孩子兄弟链表表示法孩子兄弟链表表示法也是树的一种链式存储结构 用二叉链表作为树的存储结构 每个结点的左链域指向该结点的第一个孩子 右链域指向下一个兄弟结点 由于结点中的两个指针指示的分别为 孩子 和 兄弟 故称为 孩子 兄弟链表 这种结构也称为二叉链表 图6 7树的孩子 兄弟存储结构 特点 双亲只管长子长子连接兄弟 17 树的孩子兄弟链表的存储结构描述为 typedefstructCSNode ElemTypedata structCSNode firstchild nextsibling CSNode CSTree 孩子兄弟存储结构的最大优点是可以方便地实现树和二叉树的相互转换和树的各种操作 但是 孩子兄弟存储结构的缺点也是查找当前结点的双亲结点比较麻烦 需要从树根结点开始逐个结点比较查找 18 6 1 5树和森林的遍历1 树的遍历所谓树的遍历 就是按照某种顺序依次访问树中各个结点 并使得每个结点只被访问一次 也就是把非线性结构的树结点变成线性序列的一种方式 树的遍历可以按深度优先遍历 也可以按照广度优先 按层次 遍历 深度优先遍历通常有两种方式 前序遍历和后序遍历 1 前序遍历的递归定义 若树T非空 则 访问根结点R 按照从左到右的顺序依次前序遍历根结点R的各子树T1 T2 Tk 19 2 后序遍历的递归定义 若树T非空 则 按照从左到右的顺序依次后序遍历根T的各子树Tl T2 Tk 访问根结点R 3 广度优先 按层 遍历广度优先 按层次 遍历定义为 先访问第一层结点 即树根结点 再从左至右访问第二层结点 依次按层访问 直到树中结点全部被访问为止 对图6 6 a 中的树进行按层次遍历得到树的广度优先遍历序列为 ABCDEFG 说明 前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树 6 2节将介绍二叉树 后序遍历树恰好等价于中序遍历该树所对应的二叉树 20 树的先序遍历算法描述如下 voidPreorder Btree root 先根遍历k叉树 if root NULL printf c n root data 访问根结点for i 0 it i 递归前序遍历每一个子结点 21 2 森林的遍历森林的深度优先遍历通常也有两种方式 前序遍历和后序遍历 1 前序遍历森林若森林非空 则 访问森林中第一棵树的根结点 前序遍历第一棵树中根结点的各子树所构成的森林前序遍历去掉第一棵树外其它树构成的森林 2 后序遍历森林若森林非空 则 后序遍历森林中第一棵树中根结点的各子树所构成的森林 访问第一棵树的根结点 后序遍历去掉第一棵树外其它树构成的森林 当用二叉链表作为树和森林的存储结构时 树和森林的前序遍历和后序遍历可用二叉树的前序遍历和中序遍历算法来实现 22 2 森林的遍历森林的深度优先遍历通常也有两种方式 前序遍历和后序遍历 1 前序遍历森林若森林非空 则 访问森林中第一棵树的根结点 前序遍历第一棵树中根结点的各子树所构成的森林前序遍历去掉第一棵树外其它树构成的森林 2 后序遍历森林若森林非空 则 后序遍历森林中第一棵树中根结点的各子树所构成的森林 访问第一棵树的根结点 后序遍历去掉第一棵树外其它树构成的森林 23 图6 8森林和对应的二叉树 24 6 2 1二叉树的定义与性质二叉树 BinaryTree 是另一种重要的树型结构 是度为2的有序树 它的特点是每个结点至多有两棵子树 和树结构的定义类似 二叉树的定义也可以用递归形式给出 1 二叉树的递归定义二叉树 BinaryTree 是n n 0 个结点的有限集 它或者是空集 n 0 或者同时满足以下两个条件 1 有且仅有一个根结点 2 其余的结点分成两棵互不相交的左子树和右子树 6 2二叉树 25 二叉树与树有区别 树至少应有一个结点 而二叉树可以为空 树的子树没有顺序 但如果二叉树的根结点只有一棵子树 必须明确区分它是左子树还是右子树 因为两者将构成不同形态的二叉树 因此 二叉树不是树的特例 它们是两种不同的数据结构 二叉树有5种基本形态 图6 9二叉树的五种基本形态 a 空二叉树 b 只有根结点的二叉树 c 右子树为空的二叉树 d 左子树为空的二叉树 e 左右子树均不为空的二叉树 26 两种特殊形态的二叉树 满二叉树和完全二叉树 1 满二叉树 FullBinaryTree 深度为k 且有2k 1个结点的二叉树 特点 1 每一层上结点数都达到最大 2 度为1的结点n1 0 树叶都在最下一层上 结点层序编号方法 从根结点起从上到下逐层 层内从左到右 对二叉树的结点进行连续编号 27 2 完全二叉树 CompleteBinaryTree 深度为k 结点数为n的二叉树 当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时 称为完全二叉树 图6 11完全二叉树 完全二叉树的特点 1 每个结点i的左子树的深度Lhi 其结点i的右子树的深度Rhi等于0或1 即叶结点只可能出现在层次最大或次最大的两层上 2 完全二叉树结点数n满足2k 1 1 n 2k 1 3 满二叉树一定是完全二叉树 反之不成立 28 LH1 3RH1 1LH1 RH1 2 非完全二叉树非完全二叉树 LH2 0RH2 1LH2 RH2 0 1 1 29 2 二叉树的性质性质1在二叉树的第i层上至多有2i 1个结点 i 1 性质2深度为k的二叉树至多有2k 1个结点 k 1 深度一定 二叉树的最大结点数也确定 性质3二叉树中 终端结点数n0与度为2的结点数n2有如下关系 n0 n2 1性质4结点数为n的完全二叉树 其深度为 log2n l性质5在按层序编号的n个结点的完全二叉树中 任意一结点i 1 i n 有 i 1时 结点i是树的根 否则 结点i的双亲为结点 i 2 i 1 2i n时 结点i无左孩子 为叶结点 否则 结点i的左孩子为结点2i 2i 1 n时 结点i无右孩子 否则 结点i的右孩子为结点2i 1 30 6 2 2二叉树的存储结构同线性表一样 二叉树的存储结构也有顺序和链表两种结构 1 顺序存储结构用一组地址连续的存储单元 以层序顺序存放二叉树的数据元素 结点的相对位置蕴含着结点之间的关系 bt 3 的双亲为 3 2 1 即在bt 1 中 其左孩子在bt 2i bt 6 中 其右孩子在bt 2i 1 bt 7 中 31 这种存储结构适合于完全二叉树 既不浪费存储空间 又能很快确定结点的存放位置 结点的双亲和左右孩子的存放位置 但对一般二叉树 可能造成存储空间的大量浪费 123456789101112ABCDE0000FG0000 一般二叉树也按完全二叉树形式存储 无结点处用0表示 32 例如 深度为k 且只有k个结点的右单枝树 每个非叶结点只有右孩子 需2k 1个单元 即有2k 1 k个单元被浪费 链式存储结构 二叉链表 设计不同的结点结构 可以构成不同的链式存储结构 常用的有 二叉链表三叉链表线索链表用空链域存放指向前驱或后继的线索 33 由于二叉树每个结点至多只有2个孩子 分别为左孩子和右孩子 因此可以把每个结点分成三个域 一个域存放结点本身的信息 另外两个是指针域 分别存放左 右孩子的地址 每个结点的结构表示为 其中左链域lchild为指向左孩子的指针 右链域rchild为指向右孩子的指针 数据域data表示结点的值 若某结点没有左孩子或右孩子 其相应的链域为空指针 对应的结构类型定义如下 typedefstructnode ElemTypedata structnode lchild structnode rchild BTree tree 其中 tree是指向根结点的指针 34 二叉链表的结点结构 二叉链表 说明 一个二叉链表由根指针root唯一确定 若二叉树为空 则root NULL 若结点的某个孩子不存在 则相应的指针为空 具有n个结点的二叉链表中 共有2n个指针域 其中只有n 1个用来指示结点的左 右孩子 其余的n 1个指针域为空 35 lchilddataparentrchild A C B D E 三叉链表 3 带双亲指针的二叉链表由于经常要在二叉树中寻找某结点的双亲时 可在每个结点上再加一个指向其双亲的指针parent 形成一个带双亲指针的二叉链表 就是三叉链表 三叉链表的结点结构 性质6含有n个结点的二叉链表中 有n 1个空链域 二叉树存储方法的选择 主要依赖于所要实施的各种运算的频度 36 6 2 3二叉树的基本运算及实现1 二叉树的基本运算 1 Inittree T 功能 初始化操作 建立一棵空的二叉树 2 Root T 功能 求二叉树的根 3 Parent T x 功能 求二叉树T中值为x的结点的双亲 4 Lchild T x 功能 求结点的左孩子 5 Rchild T x 功能 求结点的右孩子 6 Traverse T 功能 遍历或访问二叉树T 7 creatree T 功能 创建二叉树T 37 2 二叉树部分运算的算法描述 1 创建二叉树creatree 38 p data ch p lchild p rchild NULL if b NULL 为根结点 b p else switch k case1 stack top lchild p break case2 stack top rchild p break j ch str j 39 2 查找给定的结点find root x 3 找左孩子结点lchild p 或右孩子结点rchild p 4 输出二叉树disptree root 40 6 3 1遍历二叉树在二叉树的一些应用中 常常要求在树中查找具有某种特征的结点 或者对树中全部结点逐一进行某种处理 这就引入了遍历二叉树的问题 即如何按某条搜索路径访问树中的每一个结点 使得每一个结点仅切仅被访问一次 遍历二叉树 指按一定的规律对二叉树的每个结点 访问且仅访问一次的处理过程 遍历对线性结构是容易解决的 而二叉树是非线性的 因而需要寻找一种规律 使二叉树上的结点能排列在一个线性队列上 从而便于遍历 6 3遍历二叉树和线索二叉树 41 访问是一种抽象操作 是对结点的某种处理 例如可以是求结点的度 或层次 打印结点的信息 或做其他任何工作 一次遍历后 使树中结点的非线性排列 按访问的先后顺序变为某种线性排列 遍历的次序 假如以L D R分别表示遍历左子树 遍历根结点和遍历右子树 遍历整个二叉树则有DLR LDR LRD DRL RDL RLD六种遍历方案 若规定先左后右 则只有前三种情况 分别规定为 DLR 先 根 序遍历 LDR 中 根 序遍历 LRD 后 根 序遍历 1 遍历方案LDR中序遍历 LRD后序遍历 DLR先序遍历 42 1 中序遍历二叉树算法思想 若二叉树非空 则 1 中序遍历左子树2 访问根结点3 中序遍历右子树 算法描述 voidInorder BiTreebt bt为根结点指针if bt 根非空Inorder bt lchild visit bt data Inorder bt rchild 2 后序遍历二叉树算法思想 若二叉树非空 则 1 后序遍历左子树2 后序遍历右子树3 访问根结点 算法描述 voidPostorder BiTreebt bt为根结点指针if bt Postorder bt lchild Postorder bt rchild visit bt data 43 3 先序遍历二叉树算法思想 若二叉树非空 则 1 访问根结点2 先序遍历左子树3 先序遍历右子树 算法描述 voidPreorder BiTreebt bt为根结点指针if bt 根非空visit bt data Preorder bt lchild Preorder bt rchild 例 表达式a b c d e f 遍历结果 中序 a b c d e f后序 abcd ef 先序 a b cd ef 44 1 先序遍历的递归算法如下 假定结点的元素值为字符型 include stdio h typedefcharElemType typedefstructnode 定义链表结构 ElemTypedata 定义结点值structnode lchild 定义左子结点指针structnode rchild 定义右子结点指针 BTree preorder BTree root 前序遍历 if root NULL 如果不是空结点 printf c n root data 输出当前结点值preorder root lchild 递归前序遍历左子结点preorder root rchild 递归前序遍历右子结点 return 结束 2 遍历算法 45 voidinorder BTree root 中序遍历 if root NULL 如果不是空结点 inorder root lchild 递归中序遍历左子结点printf c n root data 输出当前结点值inorder root rchild 递归中序遍历右子结点 3 后序遍历的算法实现voidpostorder BTree root 后序遍历 if root NULL 如果不是空结点 postorder root lchild 递归后序遍历左子结点postorder root rchild 递归后序遍历右子结点printf c n root data 输出当前结点值 2 中序遍历的递归算法如下 假定结点的元素值为字符型 46 voidinorder BiTreebt InitStack s Push s bt while StackEmpty s while GetTop s Push s GetTop s lchild p POP s if StackEmpty s visit GetTop s data p Pop s Push s p rchild 中序遍历非递归算法 s为存储二叉树结点指针栈 操作过程 根结点先进栈 左结点紧跟根后面进栈 右结点在根出栈后入栈 每个结点都要进一次和出一次栈 并且总是访问栈顶元素 因此 算法正确 时间复杂度为O n 47 通过上述三种不同的遍历方式得到三种不同的线性序列 它们的共同的特点是有且仅有一个开始结点和一个终端结点 其余各结点都有且仅有一个前驱结点和一个后继结点 从二叉树的遍历定义可知 三种遍历算法的不同之处仅在于访问根结点和遍历左右子树的先后关系 如果在算法中隐去和递归无关的语句printf 则三种遍历算法是完全相同的 遍历二叉树的算法中的基本操作是访问结点 显然 不论按那种方式进行遍历 对含n个结点的二叉树 其时间复杂度均为O n 所含辅助空间为遍历过程中占的最大容量 即树的深度 最坏的情况下为n 则空间复杂度也为O n 48 3 二叉链表的构造 1 基本思想利用遍历可以实现对结点的一些操作 如求结点的双亲 求结点的孩子等 还可以在遍历过程中生成结点 建立二叉树的存储结构 前面介绍过用栈建立二叉树 此处介绍一种基于先序遍历的二叉树构造方式 即以二叉树的先序序列为输入构造二叉链表 先序序列中必须加入虚结点以示空指针的位置 2 构造算法 举例说明 49 例6 4 建立图6 13 a 所示二叉树 其输入的先序序列是 ABD G CE F 解 假设虚结点输入时以空格字符表示 相应的构造算法为 voidCreateBinTree BTree T 构造二叉链表 T是指向根指针的指针 故修改 T就修改了实参 根指针 本身charch if ch getchar T NULL 读入空格 将相应指针置空else 读入非空格 T BTree malloc sizeof BTree 生成结点 T data ch CreateBinTree T lchild 构造左子树CreateBinTree T rchild 构造右子树 调用该算法时 应将待建立的二叉链表的根指针的地址作为实参 50 6 3 2线索二叉树 问题的提出 通过遍历二叉树可得到结点的一个线性序列 在线性序列中 很容易求得某个结点的直接前驱和后继 但是在二叉树上只能找到结点的左孩子 右孩子 结点的前驱和后继只有在遍历过程中才能得到 那么 如何保存遍历二叉树后动态得到的线性序列 以便快速找到某个结点的直接前驱和后继 2 分析 n个结点有n 1个前驱和n 1个后继 一共有2n个链域 其中 n 1个空链域 n 1个指针域 因此 可以用空链域来存放结点的前驱和后继 线索二叉树就是利用n 1个空链域来存放结点的前驱和后继结点的信息 51 3 线索二叉树 有效利用二叉链表中空的存储空间 指定原有的孩子指针为空的域来存放指向前驱和后继的信息 这样的指针被称为 线索 加线索的过程称为线索化 由此得到的二叉树称作线索二叉树 结点结构在二叉链表中增加ltag和rtag两个标志域 若结点有左子树 则左链域lchild指示其左孩子 ltag 0 否则 令左链域指示其前驱 ltag 1 若结点有右子树 则右链域rchild指示其右孩子 rtag 0 否则 令右链域指示其后继 rtag 1 52 中序 先序和后序线索二叉树中所有实线均相同 所有结点的标志位取值也完全相同 只是当标志位取1时 不同的线索二叉树将用不同的虚线表示 按中序遍历得到的线索二叉树称为中序线索二叉树 按先序遍历得到的线索二叉树称为先序线索二叉树 按后序遍历得到的线索二叉树称为后序线索二叉树 2 整体结构增设一个头结点 令其lchild指向二叉树的根结点 ltag 0 rtag 1 并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继 最后用头指针指示该头结点 53 图6 14线索二叉树 54 线索二叉树的存储结点可描述如下 structnode ElemenTypedata 数据域intltag 左标志域intrtag 右标志域structnode lchild 左指针域structnode rchild 右指针域 BTree 同样 线索二叉树根据遍历规则的不同 可分为前序线索二叉树 中序线索二叉树 后序线索二叉树 55 建立中序线索二叉树的算法 voidthread BTree current BTree pre if current NULL thread 右子树线索化 56 BTree creathread BTree b 中序线索化二叉树 BTree pre root current root BTree malloc sizeof BTree 创建根结点root data r 值 r 表示根结点root ltag 1 root rtag 0 if b NULL 空二叉树 root lchild root root rchild root else 57 else current root lchild b root ltag 0 pre root pre是前驱结点 供加线索用thread returnroot 58 树与二叉树的对应关系树与二叉树均可用二叉链表作为存储结构 因此给定一棵树 用二叉链表存储 可唯一对应一棵二叉树 反之亦然 2 树转换成二叉树将一棵树转化为等价的二叉树方法如下 1 在树中各兄弟 堂兄弟除外 之间加一根连线 2 对于任一结点 只保留它与最左孩子的连线外 删去它与其余孩子之间的连线 3 以树根为轴心 将整棵树按顺时钟方向旋转约45 特点 根无右子树 6 4树 森林与二叉树的转换 59 图6 15树转换成二叉树 图6 16森林和对应的二叉树 60 3 森林转换成二叉树树和森林都可转换成二叉树 但树转换成二叉树后根结点无右分支 而森林转换后的二叉树 其根结点有右分支 将森林转化为二叉树方法如下 1 将森林中的每一棵树转换成等价的二叉树 2 保留第一棵二叉树 自第二棵二叉树始 依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子 当所有的二叉树依此相连后 所得到的二叉树就是由森林转化成的二叉树 3 以树根为轴心 将整棵树按顺时钟方向旋转约45 转换过程如图图6 16 61 4 二叉树转换成森林将当前根结点和其左子树作为森林的一棵树 并将其右子树作为森林的其他子树 重复上面直到某结点的右子树为空 62 树型结构具有广泛的应用领域 常见的有 二叉排序树 哈夫曼树和判定树等 6 5 1二叉排序树二叉排序树T是一棵二叉树 或者为空 或者满足下面条件 1 若T的根结点的左子树非空 则左子树中所有结点的值均小于根结点值 2 若T的根结点的右子树非空 则右子树中所有结点的值均大于根结点值 3 T的左右子树也分别为二叉排序树 二叉排序树又称二叉查找树 是一种动态树表 它把查找和插入操作集为一体 或查找成功或插入 具体的查找和插入方法将在第9章介绍 6 5二叉树的应用 63 6 5 2路径长度和最优二叉树 哈夫曼树 哈夫曼 Huffman 树又称最优二叉树或最优搜索树 是一种带权路径长度最短的二叉树 在许多应用中 常常赋给树中结点一个有某种意义的实数 称此实数为该结点的权 从树根结点到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度 WPL 树中所有叶子结点的带权路径长度之和称为该树的带权路径长度 通常记为 两结点间的路径 从一结点到另一结点所经过的结点序列路径长度 路径上的分支树树的路径长度 从根到每一结点的路径长度之和 64 为结点1到5之间的路径 其路径长度为2 树的路径长度 l12 l13 l14 l15 l16 l17 1 1 2 2 2 2 10 完全二叉树是路径长度最短的二叉树 考虑带权时 设树中有m个叶结点 每个叶结点带一个权值w 且根到叶结点i的路径长度为Li 1 2 m 则树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和 即 65 例如 给定4个叶结点 设权值分别为1 3 5 7 据此可以构造出形状不同的4棵二叉树 如图6 19所示 它们的带权路径长度分别为 a WPL 1 2 3 2 5 2 7 2 32 b WPL 1 2 3 3 5 3 7 l 33 c WPL 7 3 5 3 3 2 1 1 43 d WPL 1 3 3 3 5 2 7 1 29WPL最小的二叉树是最优二叉树 Huffman树 图6 19 d 所示 图6 19由4个结点构成的不同的带权二叉树 第0层第1层第2层第3层 66 1 二叉树的路径长度从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径 路经上的分支数目称为路径长度 树的路径长度是指从树根到树中每一结点的路径长度之和 在结点数目相同的二叉树中 完全二叉树的路径长度最短 2 二叉树的带权路径长度 WeightedPathLengthofTree 简记为WPL 结点的带权路径长度定义为结点到树根之间的路径长度与该结点上所带权值的乘积 树的带权路径长度 WeightedPathLengthofTree 是树中所有叶结点的带权路径长度之和 通常记为 67 3 最优二叉树或哈夫曼树哈夫曼树 或最优二叉树 在权为wl w2 wn的n个叶子所构成的所有二叉树中 带权路径长度最小 即代价最小 的二叉树 结论 当叶子上的权值均相同时 完全二叉树一定是最优二叉树 否则完全二叉树不一定是最优二叉树 在最优二叉树中 权值越大的叶子离根越近 最优二叉树的形态不唯一 但WPL最小 68 3 最优二叉树或哈夫曼树哈夫曼树 或最优二叉树 在权为wl w2 wn的n个叶子所构成的所有二叉树中 带权路径长度最小 即代价最小 的二叉树 结论 当叶子上的权值均相同时 完全二叉树一定是最优二叉树 否则完全二叉树不一定是最优二叉树 在最优二叉树中 权值越大的叶子离根越近 最优二叉树的形态不唯一 但WPL最小 69 6 5 3构造最优二叉树 1 哈夫曼算法哈夫曼算法的基本思想是 1 以权值分别为W1 W2 的 各结点 构成n棵二叉树T1 T2 Tn并组成森林F T1 T2 Tn 其中每棵二叉树Ti仅有一个权值为Wi的根结点 2 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树 并且置新二叉树根结点权值为左右子树上根结点的权值之和 根结点的权值 左右孩子权值之和 叶结点的权值 Wi 3 从F中删除这两棵二叉树 同时将新二叉树加入到F中 4 重复 2 直到F中只含一棵二叉树为止 这棵二叉树就是Huffman树 70 例如 给定权值集合 5 15 40 30 10 构造哈夫曼树的过程如图6 21所示 其中最优的带权路径长度为 WTL 5 10 4 15 3 30 2 40 205 由图6 21可以看出 哈夫曼树的结点的度数为0或2 没有度为1的结点 图6 21哈夫曼树构造过程 71 2 哈夫曼树的存储结构及哈夫曼算法的实现 1 哈夫曼树的存储结构用大小为2n 1的一维数组来存储哈夫曼树中的结点 其存储结构为 definen100 叶结点数目 definem2 n 1 树中结点总数typedefstruct floatweight 权值 设权值均大于零intlchild rchild parent 左右孩子及双亲指针 HTNode typedefHTNodeHuffmanTree m 哈夫曼树是一维数组因为C语言数组的下界为0 用 1表示空指针 树中结点的lchild rchild和parent不等于 1时 分别表示该结点的左 右孩子和双亲结点在数组中的下标 设置parent域有两个作用 一是使查找某结点的双亲变得简单 二是可通过判定parent的值是否为 1来区分根与非根结点 72 2 哈夫曼算法的简要描述在上述存储结构上实现的哈夫曼算法可大致描述为 设T的类型为HuffmanTree 初始化将T 0 m 1 中2n 1个结点里的三个指针均置为空 即置为 1 权值置为0 输入读入n个叶子的权值存于数组的前n个分量 即T 0 n 1 中 它们是初始森林中n个孤立的根结点上的权值 合并对森林中的树共进行n 1次合并 所产生的新结点依次放入数组T的第i个分量中 n i m 1 每次合并分两步 73 1 在当前森林T 0 i 1 的所有结点中 选取权值最小和次小的两个根结点T p1 和T p2 作为合并对象 这里0 p1 p2 i 1 2 将根为T p1 和T p2 的两棵树作为左右子树合并为一棵新的树 新树的根是新结点T i 具体操作 将T p1 和T p2 的parent置为i 将T i 的lchild和rchild分别置为p1和p2 新结点T i 的权值置为T p1 和T p2 的权值之和 合并后T pl 和T p2 在当前森林中已不再是根 因为它们的双亲指针均已指向了T i 所以下一次合并时不会被选中为合并对象 74 3 哈夫曼树的构造 数组法 voidCreateHuffmanTree HuffmanTreeT inti p1 p2 构造哈夫曼树 T m 1 为其根结点InitHuffmanTree T T初始化InputWeight T 输入叶子权值至T 0 n 1 的weight域for i n i m i SelectMin T i 1 75 例6 7 用链表构造哈夫曼树 解 哈夫曼树的链表结构算法描述如下 include stdio h include stdlib h include alloc h definem100structptree 定义二叉树结点类型 intw 定义结点权值structptree lchild 定义左子结点指针structptree rchild 定义右子结点指针 structpforest 定义链表结点类型 structpforest link structptree root intWPL 0 初始化WTL为0structptree hafm voidtravel structpforest inforest 76 main structptree head intn i w m printf pleaseinputthesumofnode n 提示输入结点数scanf d 输出最佳路径权值之和 77 voidtravel structptree head intn 为验证harfm算法的正确性进行的遍历 structptree p p head if p NULL if p lchild NULL 78 structptree hafm intn intw m structpforest p1 p2 f structptree ti t t1 t2 inti f structpfores malloc sizeof structpforest f link NULL for i 1 iw w i 给结点赋权值ti lchild NULL ti rchild NULL f inforest f ti while f link link NULL 至少有二棵二叉树 p1 f link p2 p1 link f link p2 link 取出前两棵树 79 f link p2 link 取出前两棵树t1 p1 root t2 p2 root free p1 释放p1free p2 释放p2t structptree malloc sizeof structptree 开辟新的结点空间t w t1 w t2 w 权相加t lchild t1 t rchild t2 产生新二叉树f inforest f t p1 f link t p1 root free f return t 返回t 80 structpforest inforest structpforest f sturctptree t structpforest p q r structptree ti r structpforest malloc sizeof structpforest 开辟新的结点空间r root t q f p f link while p NULL 寻找插入位置 ti p root if t w ti w 如果t的权值大于ti的权值 q p p p link p向后寻找 elsep NULL 强迫退出循环 r link q link q link r r接在q的后面return f 返回f 81 3 哈夫曼编码哈夫曼树的应用很广 哈夫曼编码就是哈夫曼树在电讯通信中的应用之一 通讯中常需要将文字转换成二进制字符串电文进行传送 文字电文 称为编码 收到电文后要将电文转换成原来的文字 电文文字 称为译码 在电报通信中 电文是以二进制的0 1序列传送的 在发送端需要将电文中的字符转