算法与数据结构c语言二叉树与树.pptVIP

小 结 本章主要介绍了：二叉树的定义、性质和存储表示；二叉树的周游和线索化；树的概念、存储表示和周游；树、树林与二叉树的相互转换以及二叉树的应用等。 二叉树是一类重要的树形结构，但它不是树的特例。在二叉树中严格地区分左、右子树。二叉树常用的存储方式是llink-rlink表示。 二叉树周游的方式主要有深度优先和广度优先两种方式，在深度优先周游中又分为：先根次序、对称序、和后根次序。每种深度优先周游方法都可写出它们的递归算法和非递归算法。 线索二叉树是二叉树的一种特殊链接表示。穿线后不用栈就可以实现二叉树的周游。 树是一种常见的树形结构，它常用的存储表示有三种：父指针表示法、子表表示法和长子－兄弟表示法。周游是树上的重要操作，主要有深度优先和广度优先两种方式，在深度优先中又分为先根次序周游和后根次序周游。 二叉树和树的各种存储方式是本章学习的重点。这些存储方式都应该包（隐）含所有的结点和结点之间关系的信息，不同的表示原则上应该可以相互转换。 由于树/树林与二叉树之间存在对应关系，所以常常把树与树林转换为二叉树处理。这使得二叉树的讨论和它的llink-rlink表示更加重要。 5.5.2 抽象数据类型 ADT Tree is operations Tree createEmptyTree (void) 创建一棵空树。 Tree consTree(Node p ,Tree t1, …Tree ti) 以P为根，t1 …ti 为子树 创建一棵树。 int isNull ( Tree t ) 判断树t是否为空树。 Node root ( Tree t ) 返回树t的根结点。若为空树，则返回一特殊值。 Node parent (Node p ) 返回结点p的父结点。当指定的结点为根时，它没有父结点，返回一个特殊值。 Tree leftChild (Tree t ) 返回树t的长子树。当指定树没有子树时，返回一特殊值。 Tree rightSibling (Tree t ) 返回树t的右兄弟树。当指定树没有右兄弟子树时，返回一特殊值。 end ADT Tree 5.5.3 树的周游 树的周游是一种按某种方式系统地访问树中的所有结点的过程，它使每个结点都被访问一次且只被访问一次。换句话说，通过一次周游，可使树中所有结点，按照某种（线性）序列进行一次处理。 深度优先周游：先根次序、后根次序 广度优先周游 深度优先周游：先根次序 首先访问根结点；然后从左到右按先根次序周游根结点的每棵子树。 和二叉树的先根次序周游类似。 程序实现： 递 归：void preOrder( Tree t ) 非递归：void nPreOrder ( Tree t ) 深度优先周游：后根次序 首先从左到右按后根次序周游根结点的每棵子树；最后访问根结点。 和二叉树的后根次序周游类似。 程序实现： 递 归：void postOrder( Tree t ) 广度优先周游 先访问层数为0的结点；然后从左到右逐个访问层数为1的结点；……；依此类推，直到访问完树中的全部结点。 根据广度优先周游树的定义不难想到，可以利用一个队列实现其算法。首先把被周游的树送入队列，其后，每当从队首取出一棵树，访问其根结点之后，马上把它的子树按从左到右的次序送入队列尾端；重复此过程直到队列为空。 程序实现：void levelOrder(Tree t) 5.6 树的实现 父指针表示法 子表表示法 长子-兄弟表示法 5.6.1 父指针表示法 由树的定义可以知道，树中除根以外的每个结点都有唯一的一个父结点。根据这一特性，可用一组连续的存储空间，即用一个数组存储树中的各个结点。数组中的一个元素为一个结构，其中包括结点本身的信息以及本结点的父结点在数组中的下标，树的这种存储方法称为父指针表示法。 结点的结构可定义为： struct ParTreeNode { DataType info; /* 结点中的元素 */ int parent; /* 结点的父结点位置 */ }; 树的类型定义为： struct ParTree{ int MAXNUM /* 树中最大结点个数 */ int n; /* 树中已有结点的个数 */ struct ParTreeNode * nodelist; /* 存放树中结点的数组 */ }; typedef struct ParTree * PParTree; / 树类型的指针类型 */