第3章 非线性数据结构

第3章非线性数据结构第3章非线性数据结构3.1树及其基本概念3.2二叉树3.3二叉树的遍历3.4树的存储结构和遍历3.5树、森林与二叉树的转换3.6霍夫曼树及其应用第3章非线性数据结构3.7图及其基本概念3.8图的存储结构3.9图的遍历3.10图的连通性及最小生成树习题第3章非线性数据结构3.1树及其基本概念树型结构是一种应用十分广泛的非线性数据结构，它很类似自然界中的树，直观地讲，树型结构是以分支关系定义的层次结构。树(Tree)是n(n≥0)个结点的有限集合。当n=0时称为空树，否则在任一非空树中：第3章非线性数据结构(1)有且仅有一个称为该树之根的结点；(2)除根结点之外的其余结点可分为m(m≥0)个互不相交的集合T1，T2，„，Tm，且其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。第3章非线性数据结构ABECFDGHJI图3-1树型结构第3章非线性数据结构这是一个递归定义，即在树的定义中又用到了树，它显示了树的固有特性。树中的每一个结点都是该树中某一棵子树的根。如图3-1所示的树中，A为根结点，其余的结点分为三个互不相交的有限集合：T1={B，E，F}，T2={C，G，J}，T3={D，H，I}。T1、T2和T3都是A的子树，而它们本身也是一棵树。例如，T1是一棵以B为根的树，其余结点分为互不相交的两个集合{E}和{F}，而{E}和{F}本身又是仅有一个根结点的树。第3章非线性数据结构下面结合图3-1，给出树型结构中的一些基本术语。结点的度：一个结点拥有的子树数目。如A结点的度为3，它有三个子树T1、T2和T3。E、F结点的度为0，它们没有子树。叶子：度为零的结点称叶子或终端结点。树的度：一棵树上所有结点的度的最大值就是这棵树的度。第3章非线性数据结构结点的层次：根结点的层数为1，其它任何结点的层数等于它的父结点的层数加1。树的深度：一棵树中，结点的最大层次值就是树的深度。图3-1中树的深度为4。森林：森林是m(m≥0)棵互不相交的树的集合。孩子(child)：某结点子树的根称为该结点的孩子结点。第3章非线性数据结构双亲(parent)：一个结点是它的那些子树的根的双亲结点。兄弟(sibling)：同一个双亲的孩子之间互为兄弟。如A是B、C、D的双亲；B、C、D是A的孩子；B、C、D互为兄弟。堂兄弟(cousins)：其双亲在同一层的结点互为堂兄弟。如G与E、F、H、I互为堂兄弟。第3章非线性数据结构有序树：树T中各子树T1，T2，„，Tn的相对次序是有意义的，则称T为有序树。在有序树中，改变了子树的相对次序就变成了另一棵树。在计算机中表示一棵树时，就隐含着一种确定的相对次序，所以后面我们讨论的都是有序树。第3章非线性数据结构3.2二叉树3.2.1二叉树的定义及其性质1．二叉树的定义一个二叉树是一个有限结点的集合，该集合或者为空，或由一个根结点和两棵互不相交的被称为该根的左子树和右子树的二叉树组成。这是一个递归定义，由定义可知二叉树有下面两个主要特点：第3章非线性数据结构(1)每个结点最多只能有两个孩子，即二叉树中不存在度大于2的结点。(2)二叉树的子树有左、右之分，其次序不能任意颠倒。二叉树可以有五种基本形态，如图3-2所示。第3章非线性数据结构(a)(b)(c)(d)(e)图3-2二叉树的五种基本形态第3章非线性数据结构例3-1画出具有3个结点的树和二叉树的所有不同形态。解：(1)具有3个结点的树有2种不同的形态，如图3-3所示。图3-3有3个结点的所有树的不同形态第3章非线性数据结构(a)(b)图3-3有3个结点的所有树的不同形态第3章非线性数据结构(2)具有3个结点的二叉树有5种不同的形态，如图3-4所示。(a)(b)(c)(d)(e)图3-43个结点的所有二叉树的不同形态第3章非线性数据结构注意：树和二叉树的区别主要是二叉树的结点的子树要区分左子树和右子树，即使在结点只有一个子树的情况下，也要明确指出该子树是左子树还是右子树。如二叉树T和T′是不同的二叉树，但作为树，它们就是相同的。如图3-5所示。第3章非线性数据结构ABT:(a)(b)AB:TAB(c):T图3-5二叉树与树的区别(a)二叉树T；(b)二叉树T '；(c)树T''第3章非线性数据结构2．二叉树的性质二叉树具有下列重要特性。性质1：在二叉树中，第i层的结点数最多有2i-1(i≥1)个。例如：层次i第i层最多结点数120=1221=2322=4k2k−1此性质可以用数学归纳法证明。第3章非线性数据结构性质2：在深度为k的二叉树中结点总数最多有2k–1个。由性质1可见，深度为k的二叉树的最大结点数为：k1i1i2=2k−1第3章非线性数据结构性质3： 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：(1)由于在二叉树中，任一结点的度数小于或等于2，所以其结点总数n=n0+n1+n2第3章非线性数据结构(2)设B为二叉树中总的分支数目，由于二叉树中除了根结点之外，其余结点都有一个分支进入，所以B=n−1即n=B+1而这些分支只能是由度数为1或2的结点所发出，所以B=n1+2n2于是得：n=n1+2n2+1第3章非线性数据结构(3)由(1)和(2)得：n0+n1+n2=n1+2n2+1所以n0=n2+1证毕下面介绍两种特殊形态的二叉树，满二叉树和完全二叉树。如果一棵二叉树的深度为k，并且含有2k–1个结点，则称此二叉树为满二叉树。图3-6是一棵深度为4的满二叉树。第3章非线性数据结构ACDHIJKLMNOEFGB图3-6深度为4的满二叉树第3章非线性数据结构可以看出这种树的特点是每一层的结点数都是最大结点数。对满二叉树的结点进行连续编号：从根结点起，自上而下逐层从左到右给每个结点编一个从1开始的顺序号。图3-6就成为图3-7。第3章非线性数据结构134891011121314155672图3-7深度为4的满二叉树第3章非线性数据结构深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的编号从1到n的结点一一对应时，称之为完全二叉树。如图3-8所示是一棵深度为4的完全二叉树。第3章非线性数据结构134891011125672图3-8深度为4的完全二叉树第3章非线性数据结构可以看出，完全二叉树有下面的特点：(1)叶子只可能在层次最大的两层上出现。(2)最下面一层的结点都集中在该层最左边的若干位置上。完全二叉树是一个十分重要的概念，在许多算法和算法分析中，都明显或隐含地用到了完全二叉树的概念。下面介绍完全二叉树的两个重要特性。性质4：具有n个结点的完全二叉树的深度为lbn+1第3章非线性数据结构证明：假设深度为k，则根据性质22k−1−1＜n≤2k−1或2k−1≤n＜2k于是k−1≤lbn＜k因为k是整数所以k=+1第3章非线性数据结构性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有(1)如果i=1，则i是二叉树的根，无双亲；如果i1，则其双亲是结点。(2)如果2in，则结点i无左孩子；否则其左孩子是2i。(3)如果2i+1n，则结点i无右孩子；否则其右孩子是结点2i+1。证明从略。第3章非线性数据结构另外，还有两种特殊的二叉树，平衡二叉树和二叉排序树。二叉排序树将在第4章中介绍，这里只介绍平衡二叉树的概念。二叉树上任一结点的左子树深度减去右子树深度的差值，称为此结点的平衡因子。若一棵二叉树中，每个结点的平衡因子之绝对值都不大于1，则称这棵二叉树为平衡二叉树。第3章非线性数据结构例3-2图3-9中有两棵二叉树，试判定其是否是平衡二叉树？解：二叉树(a)是平衡二叉树。二叉树(b)中结点C的平衡因子为2，大于1，故不是平衡二叉树。第3章非线性数据结构ABDECCBFEDA(a)(b)图3-9两棵二叉树第3章非线性数据结构3.2.2二叉树的存储结构对于二叉树，我们既可采用顺序存储，又可采用链式存储。1．顺序存储结构顺序存储就是将一棵二叉树的所有结点按照一定的次序顺序存放到一组连续的存储单元中，为此，必须把二叉树中所有结点构成一个适当的线性序列，以使各个结点在这个序列中的相互位置能反映出结点之间的逻辑关系。第3章非线性数据结构对于完全二叉树，按图3-8中的编号顺序，就能得到一个足以反映整个二叉树结构的线性序列。因此，可将完全二叉树中所有结点按编号顺序依次存储到一组连续的存储单元(即向量)中，这样既不浪费内存，又可以利用地址公式确定其结点的位置。但对于一般的二叉树，顺序分配常会造成内存的浪费，因为一般的二叉树也必须按完全二叉树的形式来存储。图3-8所示的完全二叉树，其顺序存储结构如图3-10(a)所示。第3章非线性数据结构而图3-10(b)所示的二叉树，其顺序存储结构如图3-10(c)所示，图中以“0”表示不存在此结点。在最坏情况下，一个深度为k且只有k个结点的单支树(树中无度为2的结点)却需要2k–1个存储单元。可见，浪费很大。所以，一般情况下，还是用链表来表示二叉树。第3章非线性数据结构123456789101112(a)102000(c)3123(b)图3-10二叉树的顺序存储结构第3章非线性数据结构2．链式存储结构因为树型结构是非线性的结构，所以在存储器里表示树型结构的最自然的方法是链式存储。根据二叉树的特性，任何一个结点最多有左、右两棵子树，所以每个结点至少设有三个域：数据域和左、右指针域。其结点结构为：lchildDatarchild第3章非线性数据结构其中，lchild是左指针域，指向结点的左子树的根；data是数据域；rchild是右指针域，指向结点的右子树的根。这种存储结构又称为二叉链表。在二叉链表中，我们可以比较方便地从某个结点出发，找到它的一个子结点，但如果要从某个结点找其父结点就比较麻烦了。有时为便于找到结点的双亲，还可增加一个指向其双亲的指针域(parent)，其结点结构如下：lchilddataparentrchild第3章非线性数据结构由这种结点结构所得的二叉树存储结构称为三叉链表。另外，还需设一个指针T指向树的根。若树为空，则T=NULL，否则T指向树的根。例3-3画出给定二叉树的二叉链表和三叉链表存储结构。结果如图3-11所示。第3章非线性数据结构CBFEDA(a)(b)ABCDEFT(c)ABCDEFT图3-11二叉树及其链表存储结构第3章非线性数据结构3.3二叉树的遍历遍历二叉树就是按一定的次序，系统地访问树中的所有结点，使每个结点恰好被访问一次。所谓访问结点，其含义是很广的，可以理解为对结点的增、删、修改等各种运算的抽象。在本节讨论中，假定访问结点即为输出结点数据域值。二叉树的遍历是最重要和最基本的运算，二叉树的许多操作都是以遍历为基础的。第3章非线性数据结构遍历二叉树的过程实际上就是按某种规律把二叉树的结点排成一个线性序列。由于二叉树是非线性结构，它的每个结点都可能有两个分支，也就是说一个结点可能有两个后继，所以，二叉树的遍历比较复杂，按照不同规则遍历得到的结果也就不同。令L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对二叉树的遍历有六种规律：DLR、LDR、LRD、DRL、RDL、RLD。若规定先左后右，则只有三种方案：DLR、LDR和LRD，按照访问根的先后，分别称之为二叉树的先序(根)遍历，中序(根)遍历和后序(根)遍历。第3章非线性数据结构基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义。二叉树的三种遍历方式：(1)先序遍历：若二叉树为空，则空操作；否则①访问根结点；②先序遍历左子树；③先序遍历右子树。第3章非线性数据结构(2)中序遍历：若二叉树为空，则空操作；否则①中序遍历左子树；②访问根结点；③中序遍历右子树。(3)后序遍历：若二叉树为空，则空操作；否则①后序遍历左子树；②后序遍历右子树。③访问根结点；第3章非线性数据结构二叉链表的C语言描述如下：structtnode{intdata;struct