数据结构A第5章(南邮).ppt

层次结构的数据在现实自然界中大量存在。 国家、省、市、县和区。 书的章节、回目。 上级和下级。 整体和部分。 祖先和后裔。 操作系统的目录结构 2. 树的递归定义 定义5.2 树是包括n个结点的有限非空集合T，其中一个特定的结点r称为根，其余结点（T-{r}）划分成m（m≥0）个互不相交的子集T1，T2，...Tm，其中，每个子集都是树，被称为树根r的子树。 定义5.2是递归的，用子树来定义树，也就是说，在树的定义中引用了树概念本身，所以，树被称为递归数据结构。 int func(int n) { if (n==1) return 1; return func(n-1)*n; } int func(int n) { if (n==1) return 1; return func(n-1)*n; } 二叉树是非常重要的树形数据结构。 很多从实际问题中抽象出来的数据是二叉树形的；以后我们将看到任意树或森林可方便地转换成二叉树，从而为一般树和森林的存储和处理提供了有效方法。 先看一个二叉树应用例子。 设有序表为（21，25，28，33，36，45），现在要在表中查找元素33。 定义5.6 扩充二叉树也称2-树，其中除叶子结点外，其余结点都必须有两个孩子。 如果应用程序需要经常执行从孩子到双亲访问，可在二叉链表结点中增加一个parent域，令它指向该结点的双亲结点。这就实现了从孩子到双亲，以及从双亲到孩子的双向链接结构，形成多重链表。 本小节中，我们主要实现MakeTree、BreakTree和Root运算，而将二叉树遍历算法留待下一小节专门讨论。 Clear()函数释放二叉链表中的所有结点，它需要通过遍历二叉树来实现。 先序遍历序列： A B D G H E C F 中序遍历 后序遍历 层次遍历 对于遍历运算，设计了一个面向用户的公有成员函数和一个具体实现遍历操作的递归私有成员函数，两者共同完成遍历运算的功能。 公有成员函数：非递归函数，作为与用户的接 口。它调用私有的递归函数。 私有成员函数：递归函数，具体实现遍历操作。 被公有成员函数调用。 例 已知结点的先序序列和中序序列分别为： 前序序列 A B C D E F G 中序序列 C B E D A F G 则可按上述分解求得整棵二叉树。其构造过程如下图所示。首先由前序序列得知二叉树的根为A，则其左子树的中序序列为（CBED），又右子树的中序序列为（FG）。反过来得知其左子树的前序序列必为（BCDE），右子树的前序序列为（FG）。类似地，可由左子树的前序序列和中序序列构造A的左子树，由右子树的前序序列和中序序列构造得A的右子树。 编译原理中的表达式树 5.4 二叉树遍历的非递归算法 森林转换成二叉树的具体做法： 　　　１.将森林中各树的根用线连起来， 　　　２.在树中，凡是兄弟用线连起来--兄弟手拉手； 　　　３.去掉从双亲到除了第一个孩子以外的孩子的连线，只保留双亲到第一个孩子的连线--断绝非长子之间的父子关系； 　　　4.使之稍微倾斜成习惯的二叉树形--最后抖一抖。 　　　其实，这里讨论的森林是指有序森林，也可将一般的森林视为有序森林来对待。 5.5.2 树和森林的存储表示 5.5.3 树和森林的遍历 5.6 堆和优先权队列 堆是一种很有用的数据结构，它可以用于高效地实现优先权队列。 优先权队列中的元素，按其优先级的高低而不是按元素进入队列的次序，来确定出队列的次序。 5.6.1 堆 一个大小为n的堆是一棵包含n个结点的完全二叉树，该树中每个结点的关键字值大于等于其双亲结点的关键字值。 完全二叉树的根称为堆顶。它的关键字值是整棵树上最小的。这样定义的堆称为最小堆 。 也可构建最大堆 。 5.6.2 优先权队列ADT 1．优先权队列 优先权队列不同于先进先出（FIFO）队列，优先权队列中的元素，按其优先级的高低而不是按元素进入队列的次序，来确定出队列的次序。最小值为最高优先权。优先级的最高的元素放在队首，最先出队。 2．堆是实现优先权队列的有效的数据结构。 　 5.6.2 优先权队列ADT ADT PrioQueue{ 数据： n?0个元素的最小堆。 运算： Create()：建立一个空队列。 Destroy()：撤消一个队列。 IsEmpty()：若队列空，则返回true；否则返回false。 IsFull()：若队列满，则返回true；否则返回false Append(x):元素值为x的新元素入队列。 　Serve(x): 在x中返回