DSB第05章[Delivrey].pptVIP

层次结构的数据在现实自然界中大量存在。 国家、省、市、县和区。 书的章节、回目。 上级和下级。 整体和部分。 祖先和后裔。 操作系统的目录结构 2. 树的递归定义 定义5.2 树是包括n个结点的有限非空集合T，其中一个特定的结点r称为根，其余结点(T-{r})划分成m(m≥0)个互不相交的子集T1,T2,...Tm,其中，每个子集都是树，被称为树根r的子树。 定义5.2是递归的，用子树来定义树，也就是说，在树的定义中引用了树概念本身，所以，树被称为递归数据结构。 二叉树是非常重要的树形数据结构。 很多从实际问题中抽象出来的数据是二叉树形的；以后我们将看到任意树或森林可方便地转换成二叉树，从而为一般树和森林的存储和处理提供了有效方法。 先看一个二叉树应用例子。 设有序表为（21，25，28，33，36，45），现在要在表中查找元素33。 定义5.6 扩充二叉树也称2-树，其中除叶子结点外，其余结点都必须有两个孩子。 二叉树的二叉链表结构有利于从双亲到孩子方向的访问。如果已知二叉树的一个结点，要查找其双亲结点，在该结构下只能采取从根开始，遍历整个二叉树来实现，这显然是费时的。 如果应用程序需要经常执行从孩子到双亲访问，可在二叉链表结点中增加一个parent域，令它指向该结点的双亲结点。这就实现了从孩子到双亲，以及从双亲到孩子的双向链接结构，形成多重链表。 本小节中，我们主要实现CreateBT、MakeTree和BreakTree运算，而将二叉树遍历算法留待下一小节专门讨论。 中序遍历： 对于遍历运算，设计了一个面向用户的公有成员函数和一个具体实现遍历操作的递归私有成员函数，两者共同完成遍历运算的功能。 公有成员函数：非递归函数，作为与用户的接 口。它调用私有的递归函数。 私有成员函数：递归函数，具体实现遍历操作。 被公有成员函数调用。 例 已知结点的前序序列和中序序列分别为： 前序序列 A B C D E F G 中序序列 C B E D A F G 则可按上述分解求得整棵二叉树。其构造过程如下图所示。首先由前序序列得知二叉树的根为A，则其左子树的中序序列为（CBED），又右子树的中序序列为（FG）。反过来得知其左子树的前序序列必为（BCDE），右子树的前序序列为（FG）。类似地，可由左子树的前序序列和中序序列构造A的左子树，由右子树的前序序列和中序序列构造得A的右子树。 编译原理中的表达式树 专家系统中的决策树 猜谜游戏的决策树 5.5.2 树和森林的存储表示 5.5.3 树和森林的遍历 5.7.1 树的路径长度 作业 P141 第二题、第三题 P142 第六、七、八、十三、十八题 实验 实验2：比较顺序存储和链接存储两种存储结构的优缺点。（参考教材4.1） (1) 分别用顺序存储和链接存储实现线性表的基本操作； (2) 比较两者的优缺点，并说明两者的适用场合。 先序遍历?前缀表达式 中序遍历?中缀表达式 后序遍历?后缀表达式 (d) a*(b+c*d)/e / * + e b * a c d (c) a*(b+c) * a c + b (b) a*b+c + * b c a (a) a/b / a b Is the picture clear? Is the screen blank? Is there sound? Is there sound? Check mute button Check power card No Yes Yes Yes No No No Yes Is it in North America? Brazil U.S.A. No Yes Is it in North America? U.S.A. No Yes Brazil No Is it in Europe? England Yes 前两几节中，我们已介绍了树和森林的定义和概念，并对二叉树作了详细介绍，现在再回过头来讨论森林和二叉树的转换、树或森林的存储表示及其遍历算法。 5.5 树和森林 课堂提要 第5章 树 5.1 树的基本概念 5.2 二叉树 5.3 二叉树的遍历 5.5 树和森林 5.7 哈夫曼树和哈 夫曼编码 1. 树(Tree)转换为二叉树(BTree)算法 树可以唯一地表示成一棵二叉树： ⑴ 将树中的兄弟用线连接； ⑵ 对各结点，保留最左孩子的连线，去掉其余孩子的连线； ⑶ 调整为习惯的二叉树形(水平右斜，垂直左斜)。 A B C K D E F G H J A B C K D E H F J G (a)森林F=(T1,T2) (b) F所对应的二叉树 5.5.1 森林与二叉树的转换 D