第4章 非线性数据结构基础(1).ppt

1、第4章 非线性数据结构基础(1),石志国,大纲, 树与二叉树的基本概念、他们的存储结构 图的基本概念和存储结构,4.1 树与二叉树,树型结构是一类重要的非线性结构。树型结构是结点之间有分支、并且具有层次关系的结构。 在计算机领域中，树有着非常广泛的应用。 例如，在编译程序中，用树来表示源程序的语法结构。在数据库系统中，用树来组织信息等。,4.1.1 树的基本概念,树(Tree)是n(n0)个结点的有限集，如该有限集为空，则称为空树。对于非空的树，应该满足如下2个条件： 有且仅有一个称为根(Root)的结点； 除根结点外的其余结点可分为m(m0)个互不相交的子集T1,T2,T3Tm，其中每个子集

2、又是一棵树，并称其为根的子树(Subtree),4.1.1 树的基本概念,树中常用的术语有： 结点的度 结点所拥有的子树的个数称为该结点的度。 叶结点 度为 0 的结点称为叶结点，或者称为终端结点。 分支结点 度不为 0 的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。除根结点以外的分支结点也称为内部结点。 孩子、双亲、兄弟 树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。,4.1.1 树的基本概念, 路径、路径长度 如果一棵树的一串结点 n1，n2，nk存在如下关系： 结点 ni是 ni+1

3、的父结点（1ik），就把 n1，n2，nk称为一条由 n1至 nk的路径。这条路径的长度是 k-1 祖先、子孙 在树中，如果存在一条从结点 P 到结点 Q路径，则称结点 P为结点Q的祖先，而结点Q称为结点P的子孙。 结点的层数 规定树的根结点的层数为 1，其余结点的层数等于它的双亲结点的层数加 1。,4.1.1 树的基本概念, 树的深度 树中所有结点中的最大层数称为树的深度或高度。 树的度 树中各结点度的最大值称为该树的度。 有序树和无序树 如果一棵树中结点的各子树从左到右是有次序的，即若交换了某结点在各子树的相对位置，则构成不同的树，则称这棵树为有序树；反之称之为无序树。 11 森林 森林是

4、指具有m（m0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，它就变成了一棵树。,4.1.2 二叉树,二叉树（Binary Tree）在实际应用中有着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。 所谓二叉树是指由n(n0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 这是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树具有如下性质： 在二叉树的第i层上至多有2i-1个结

5、点。 深度为k的二叉树至多有2k1个结点（k1)。 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0n21。,证明：,证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和： n=no+n1+n2 (式子1) 另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是： nl+2n2 树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为： n=n1+2n2+1 (式子2)由式子1和式子2得到： no=n2+1,满二叉树(Full Binary Tree),对于一棵二叉树，如果所有

6、分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，此时称这棵二叉树为满二叉树。 一棵深度为k 的有n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（1in）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。 完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。,完全二叉树(Complete Binary Tree),完全二叉树具有如下性质： 有n个结点的完全二叉树的深度为 1。 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第 +1层，每层从左到右)，则对任一结点i

7、(1in)有： 如果i1，则结点i无双亲，是二叉树的根； 如果i1，则其双亲是结点 ； 如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i； 如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。 显然，一棵满二叉树一定是一棵完全二叉树，而完全二叉树未必是满二叉树,4.2 树与二叉树的存储结构,二叉树的存储结构主要有两种： 顺序存储结构和链式存储结构。 （1）顺序存储结构 依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以惟一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置及结点之

8、间的关系。 对于一般的二叉树而言，采用顺序存储方式是有可能造成存储空间浪费，例如，在极端的情况下，一个深度为h且只有h个结点的右单支树只需要2h-1个结点存储空间。如图4-1所示。 另外，若经常需要插入与删除树中结点时，顺序存储方式也不是一个很好的结构。,顺序存储结构,（2）链式存储结构,链式存储结构是指用链表来表示一棵二叉树，即用链来表示元素间的逻辑关系。 链式存储结构通常有二叉链表存储和三叉链表存储两种形式。 对于二叉链表存储结构，链表中每个结点由三个域组成，一个数据域，两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。 与二叉链表存储结构相比，三叉链表存储结构的每个结点

9、多一个指向其双亲的指针域。,4.2.2 树的存储结构,（1）双亲表示法 这种方法用一组连续的空间来存储树中的结点，在保存每个结点的同时设置一个指向其双亲结点的索引，即指示其双亲结点在表中的位置。 （2）孩子表示法 BTNode *lChild,*rChild;,4.2.3 二叉树的遍历,遍历二叉树(Traversing Binary Tree)是指按照某条搜索路径访问树中的结点，保证树中每个结点均被访问一次，且仅被访问一次。 如果用L、D、R分别表示遍历左子树、访问根结点、 遍历右子树， 那么对二叉树的遍历顺序就可以有六种方式：,4.2.3 二叉树的遍历,如果用L、D、R分别表示遍历左子树、访

10、问根结点、 遍历右子树， 那么对二叉树的遍历顺序就可以有六种方式： 访问根，遍历左子树，遍历右子树（记做DLR）。 访问根，遍历右子树，遍历左子树（记做DRL）。 遍历左子树，访问根，遍历右子树（记做LDR）。 遍历左子树，遍历右子树，访问根（记做LRD）。 遍历右子树，访问根，遍历左子树（记做RDL）。 遍历右子树，遍历左子树，访问根（记做RLD）。,4.2.3 二叉树的遍历,如果限定先左后右的访问顺序，则只有DLR、LDR、LRD三种遍历形式。下面主要对这三种遍历形式进行描述。 先序遍历 先序遍历（Preorder Traversal）操作过程： 若二叉树为空， 则空操作， 否则依次执行如下3个操作： 访问根结点； 按先序遍历左子树； 按先序遍历右子树。,4.2.3 二叉树的遍历, 中序遍历 中序遍历（Inorder Traversal）操作过程。 若二叉树为空， 则空操作， 否则依次执行如下3个操作： 按中序遍