搜索
第3章非线性数据结构第3章非线性数据结构3.1树及其基本概念3.2二叉树3.2.1二叉树的定义及其性质3.2.2二叉树的存储结构3.3二叉树的遍历3.4树的存储结构和遍历第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章非线性数据结构ABECFDGHJI图3-1树型结构第3章非线性数据结构下面结合图3-1，给出树型结构中的一些基本术语。结点的度：一个结点拥有的子树数目。如A结点的度为3，它有三个子树T1、T2和T3。E、F结点的度为0，它们没有子树。叶子：度为零的结点称叶子或终端结点。树的度：一棵树上所有结点的度的最大值就是这棵树的度。第3章非线性数据结构ABECFDGHJI图3-1树型结构第3章非线性数据结构结点的层次：根结点的层数为1，其它任何结点的层数等于它的父结点的层数加1。树的深度：一棵树中，结点的最大层次值就是树的深度。图3-1中树的深度为4。森林：森林是m(m≥0)棵互不相交的树的集合。孩子(child)：某结点子树的根称为该结点的孩子结点。如B、C、D是A的孩子。第3章非线性数据结构双亲(parent)：一个结点是它的那些子树的根的双亲结点。如A是B、C、D的双亲。兄弟(sibling)：同一个双亲的孩子之间互为兄弟。B、C、D是A的孩子；B、C、D互为兄弟。堂兄弟(cousins)：其双亲在同一层的结点互为堂兄弟。如G与E、F、H、I互为堂兄弟。第3章非线性数据结构有序树：若将树中每个结点的各子树看成是从左到右有次序的(即不能互换的)，则称该树为有序树，否则为无序树。作为有序树，图6.26中的两棵树是不同的，因为结点A的两个孩子在两棵树中的左右次序不同。以后若不特别指明，所讨论的树都是有序树。ABCACB图6.26两棵不同的有序树第3章非线性数据结构3.2二叉树3.2.1二叉树的定义及其性质1．二叉树的定义一个二叉树是一个有限结点的集合，该集合或者为空，或由一个根结点和两棵互不相交的被称为该根的左子树和右子树的二叉树组成。二叉树中每个结点最多只能有两棵子树，并且有左右之分，即有序。二叉树有下面两个主要特点：第3章非线性数据结构(1)每个结点最多只能有两个孩子，即二叉树中不存在度大于2的结点。(2)二叉树的子树有左、右之分，其次序不能任意颠倒。二叉树可以有五种基本形态，如图3-2所示。第3章非线性数据结构(a)(b)(c)(d)(e)图3-2二叉树的五种基本形态第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章非线性数据结构下面介绍两种特殊形态的二叉树，满二叉树和完全二叉树。如果一棵二叉树的深度为k，并且含有2k–1个结点，则称此二叉树为满二叉树。图3-6是一棵深度为4的满二叉树。ACDHIJKLMNOEFGB图3-6深度为4的满二叉树第3章非线性数据结构可以看出这种树的特点是每一层的结点数都是最大结点数。对满二叉树的结点进行连续编号：从根结点起，自上而下逐层从左到右给每个结点编一个从1开始的顺序号。图3-6就成为图3-7。134891011121314155672图3-7深度为4的满二叉树第3章非线性数据结构深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的编号从1到n的结点一一对应时，称之为完全二叉树。如图3-8所示是一棵深度为4的完全二叉树。134891011125672图3-8深度为4的完全二叉树第3章非线性数据结构完全二叉树是一个十分重要的概念，在许多算法和算法分析中，都明显或隐含地用到了完全二叉树的概念。下面介绍完全二叉树的两个重要特性。性质4：具有n个结点的完全二叉树的深度为⌊log2n⌋+1。第3章非线性数据结构性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第⌊log2n⌋+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有(1)如果i=1，则i是二叉树的根，无双亲；如果i1，则其双亲是结点i/2。(2)如果2in，则结点i无左孩子；否则其左孩子是2i。(3)如果2i+1n，则结点i无右孩子；否则其右孩子是结点2i+1。证明从略。第3章非线性数据结构134891011125672图3-8深度为4的完全二叉树如上图的树中，共有12个结点，第6号结点的左孩子序号为12，无右孩子。对于第7号结点，2i=1412=n,无孩子。其他可逐一验证。这里需要指出，上述性质4、性质5不能用于非完全二叉树。第3章非线性数据结构二叉树性质5算法实现：#includestdio.hvoidmain(){intbt[12],i,k;for(i=1;i12;i++)scanf(%d,&bt[i]);/*输入结点的值*/printf(nodeis:\n);for(i=1;i12;i++)printf(%d\n,bt[i]);/*输出结点的值*/printf(pleaseinputi:\n);第3章非线性数据结构scanf(%d,&i);while(1){if((k=2*i+1)12){printf(Lchildis%d\n,bt[2*i]);printf(Rchildis%d\n,bt[2*i+1]);}elseif((k=2*i)12){printf(Lchildis%d\n,bt[2*i]);printf(NoRchild\n);}elseprintf(Nochild\n);第3章非线性数据结构if((k=i/2)=1)printf(fatheris%d\n,bt[k]);elseprintf(nodeisroot\n);scanf(%d,&i);if(i==0)break;}}第3章非线性数据结构3.2.2二叉树的存储结构对于二叉树，我们既可采用顺序存储，又可采用链式存储。1．顺序存储结构顺序存储就是将一棵二叉树的所有结点按照一定的次序顺序存放到一组连续的存储单元中，为此，必须把二叉树中所有结点构成一个适当的线性序列，以使各个结点在这个序列中的相互位置能反映出结点之间的逻辑关系。第3章非线性数据结构对于完全二叉树，从树根起，自上而下，每层从左到右，给所有结点编号，即按图3-8中的编号顺序，就能得到一个足以反映整个二叉树结构的线性序列。因此，可将完全二叉树中所有结点按编号顺序依次存储到一组连续的存储单元(即向量bt[n+1]中，其中bt[0]不用。)中，这样既不浪费内存，又可以利用地址公式确定其结点的位置。134891011125672图3-8第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．二叉树的生成算法生成二叉树的二叉链表的方法有多种，而且算法都比较复杂，其原理是依次插入结点，构造二叉树的二叉链表。根据二叉树的二叉链表存储结构，使用一种有辅助数组的创建二叉树的二叉链表的算法。该算法是利用了二叉树的性质5，对于一般二叉树，必须添加若干个虚结点使其成为完全二叉树，然后按编号输入结点信息，构建二叉链表。例根据二叉链表结构，使用辅助数组，创建一棵如图1所示二叉树的二叉链表。第3章非线性数据结构算法思想：先按完全二叉树对其进行编号，编号后的情况如图2中第一行所示。该算法中使用一个辅助向量s用于存放二叉树结点的指针(地址)，如s[i]中应该存放编号为i的结点的地址指针。此例原始数据序列如图(2)所示，第一行是结点的编号，第二行是结点的数据。按编号、结点值顺序依次输入即可生成二叉链表。ABCDEF图11datas[i]存放地址132457ABCDEF图2第3章非线性数据结构当结点编号为1时，所产生的结点是根节点，同时将指向该结点的指针存入s[1]当结点编号i1时，产生一个新的结点之后，也要将指向该结点的指针存入s[i]。由性质5可知：它的双亲结点编号是j=[i/2]。当i为偶数，则它是双亲结点的左孩子，即让s[j]-lch=s[i];当i为奇数，则它是双亲结点的右孩子，即让s[j]-rch=s[i]。就是这样将新输入的结点逐一与其双亲结点相连，生成二叉链表。第3章非线性数据结构二叉链表的结点结构：structtnode{intdata;structtnode*lchild,*rchild;}typedefstructtnodeTNODE;辅助数组s是一个指针数组，每个数组元素是指向TNODE类型的指针，即TNODE*s[20]。二叉链表的生成算法如下：第3章非线性数据结构TNODE*creat()/*按性质5进行建树*/{TNODE*p；inti,j;intx;TNODE*s[20];TNODE*t=NULL;printf(“\ni,x=“);/*提示输入第1个元素与值*/scanf(“%d%c”,&i,&x);/*键盘输入第1个元素与值*/第3章非线性数据结构While((i!=0)&