第九章 链表和二叉树

第九章链表和二叉树9.1链表9.2二叉树9.1链表9.1.1链表的概念9.1.2链表的操作9.1.3循环链表9.1.1链表的概念1.线性表一个线性表LIST是由n(n≥0)个同类型数据元素a1,a2,a3,……，an组成的有限序列，记作LIST=(a1,a2,a3,……，an)a1为“起始结点”，an为“终止结点”n为线性表的长度。当n=0时为空表。ai的前驱为ai-1，后续为ai+1。9.1.1链表的概念线性表的存储结构有两种：顺序存储结构和链式存储结构。其中顺序存储结构是用一组连续的存储单元依次存放它的各个数据元素。9.1.1链表的概念2.链表链表是线性表的链式存储结构的别称。其存储特点是用一组任意的存储单元存储数据元素，这组存储单元可以是连续的，也可以是不连续的。9.1.1链表的概念2.链表每个元素除需存储自身信息外，还需存储其后续元素的信息。每个元素的存储映像称为结点。存储后续结点的存储位置的域称为指针域，存储数据元素信息的域称为数据域。用指针相连的结点序列称为链表。9.1.1链表的概念链表中每个结点可以包含若干个数据域和指针域。只有一个指针域的链表称为单链表。本章中若没有特别指出，所有的链表均指单链表。表中每一行作为一个结点，结点有六个数据域：学号，姓名，语文，数学，英语，计算机，总分；另外还要有一个指针域（link）。structCJ{charxh[8];charxm[6];

intyw;intsx;intyy;intjsj;intzf;

structCJ*link;};假设有n个人，每个人的数据域分别用a1，a2，……an表示。首指针head指示链表第一个结点的存储位置。线性表中最后一个结点的指针为“空”（NULL）。当head为NULL时，head所指向的链表为空表。为操作方便，给链表增加一个头结点，头结点的数据域无意义，而指针域指向线性表的第一个结点，并且首指针head指向头结点，当头结点的指针域为“空”（NULL）时，表示该链表为空表。9.1.1链表的概念

链表也是一种非直接存取的存储结构，因为每一个结点的存储位置都被包含在其前驱结点的指针域的指针中。必须从首指针开始，沿指针链向后找到要存取的结点。由于head的指针域为31，首先找到该链表的第一个结点即存储地址为31的结点a1，再通过a1的指针域可得其后续元素的存储地址为1即(a2)，依次类推，可以找到a3，a4。9.1.2链表的操作链表是一种动态存储结构，所占用的存储空间是在程序的执行的过程中得到当链表需要增加一个结点时，要为结点向系统申请一个存储空间。当链表删除一个结点时，要将已删除的结点的存储空间释放，归还给系统。9.1.2链表的操作例如，p为指向结点的指针变量，

CJ*p;这时，p所指向的结点还不存在，需要为p申请一个结点，方法为p=newCJ;同样，当p所指向结点不再需要时，要释放该结点空间，方法为

free(p);9.1.2链表的操作1.建立链表建立一个有n个结点并带头结点的链表，最直接的方法是：首先生成一个结点p，将其作为头结点，然后依次建立新的结点q，将其数据域置入相应的值，指针域赋“空”（NULL），并将其链接到链表的尾部，且p始终指向链表最后一个结点。#include<stdio.h> CJ*head,*p,*q;voidcreate(intn){inti;p=newCJ;//分配存储单元head=p;for(i=1;i<=n;i++){q=newCJ;scanf(“%s”,q->xh);//输入各项值

scanf(“%s”,q->xm);scanf(“%d”,&q->yw);scanf(“%d”,&q->sx);scanf(“%d”,&q->yy);scanf(“%d”,&q->jsj);scanf(“%d”,&q->zf);q->link=NULL;p->link=q;p=q;}}执行create(3)后，若输入的信息依次为04253101，李绯，85，90，78，92，345，04253102，王小霞，56，85，45，93，278，04253132，张海涛，76，48，83，65，272，得到的链表下图所示。9.1.2链表的操作2.插入结点假设我们要在链表的两个数据元素a，b之间插入一个数据元素x，已知p为链表存储结构中指向结点a的指针。如图9.5所示。假设s为指向结点x的指针，则语句描述为s->link=p->link;p->link=s9.1.2链表的操作同理，如果要在成绩管理系统中第2条和第3条记录之间插入一条记录。分配存储单元给要插入记录（设为指针s）然后查找xh为04253102这条记录（p），并修改s的指针域，使其为p->link然后再修改p的指针域，使其指向s即可CJ*head,*p,*s;voidinsert(inti){intj;p=head;j=1;while((p!=NULL)&&(j<i)){p=p->link;j++;}//寻找第i-1个结点if(p==NULL)printf("已到表尾！");{s=newCJ;scanf(“%s”,s->xh);scanf(“%s”,s->xm);scanf(“%d”,&s->yw);scanf(“%d”,&s->sx);scanf(“%d”,&q->yy);scanf(“%d”,&s>jsj);scanf(“%d”,&s->zf);s->link=p->link;p->link=s;}}9.1.2链表的操作3.删除结点假定在如图(a)所示线性表中，要删除b所在的结点，删除的方法是：使指针p指向要删除结点的前驱结点；将p的指针域指向要删除的结点的后继结点；将要删除的结点释放。删除过程如下：q=p->link;p->link=q->link;free(q);9.1.2链表的操作以成绩管理系统为例假设要删除xh为04253102记录，如图所示。可以先查找xh为04253102的前驱记录，并修改其指针域，使其指向04253102的后续记录，然后释放空间。CJ*head,*p,*q;delete_link(inti){CJ*p,*q;intj;p=head;j=1;while((p!=NULL)&&(j<i)){p=p->link;j++;}//寻找第i-1个结点if(p==NULL)printf("链表中没有要删除的结

点");else{q=p->link;p->link=q->link;free(q);//删除指定结点q}}9.1.3循环链表如果将链表最后一个结点的指针域改为存放链表中第一个结点的地址值，就使整个链表构成一个环形，这样的链表称为循环链表。循环链表中所有的结点链接成一个环，从表的任何一个结点出发都能访问到表中的所有结点，也可以给表增加一个特殊头结点。其逻辑结构如图所示：9.1.3循环链表循环链表的操作和线性链表基本一致，差别仅在于算法中的循环结束条件不是p或者p->link是否为NULL，而是它们是否等于首指针。有时在循环链表中设立尾指针而不设立首指针，可以简化某些操作。9.1.3循环链表例如，将两个循环链表合并成一个，仅需将两个表的表尾指针交换即可。设合并的链表由指针a和b分别指向各自尾结点，且都带有头结点。合并过程及合并方法如下：p=a->link;q=b->link;a->link=q->link;b->link=p;free(q);9.2二叉树单链表实际上是线性结构，即除首元素和尾元素以外，每个元素有惟一的前驱和后续元素。而二叉树是一种重要的非线性结构，它所讨论的是层次和分支关系，即除了有一个根元素没有前驱以外，每个元素都有惟一的前驱元素；另外，每一个元素都有零个或多个后续元素。9.2二叉树9.2.1树及二叉树的概念9.2.2二叉树的建立9.2.3二叉树的遍历9.2.1树及二叉树的概念1.树的定义现实生活中存在着许多用树结构描述的实际问题。例如，一家族血统关系。假设李大民有三个孩子：李一杨、李一力和李一军，而李一杨有一个孩子李辉，李一力有两个孩子李晓和李亮。这种关系可很自然的用树结构来表示。如图所示。9.2.1树及二叉树的概念1.树的定义上图很像一棵倒画的树，树的定义如下：

树(tree)是n(n>0)个结点的有限集。在任意一棵树中：有且仅有一个特定的称为根(root)的结点；当n>1时，其余结点可分为m(m>0)个互个相交的有限集T1，T2，…，Tm，其中每个集合本身又是一棵树，并且称为根的子树(subtree)。9.2.1树及二叉树的概念(a)是只有一个根结点的树；(b)是有13个结点的树，其中A根，其余结点分成3个互不相交的子集：T1={B，E，F，K，L}，T2={C，G}，T3={D，H，I，J，M}；T1、T2和T3都是根A的子树，且本身也是一棵树。例如T1，其根为B，其余结点分为两个互不相交的子集：T11={E，K，L}，T12={F}。T11、T12都是B的子树。而T11中E是根，{K}和{L}是E的两棵互不相交的子树，其本身又是只有一个根结点的树。9.2.1树及二叉树的概念树的一些基本术语：结点：是包含一个数据元素的若干指向其子树的分支。结点的度：结点拥有的子树数。例如，在图9.11(b)中，A的度为3，C的度为1，E的度为2，K的度为0。叶子：度为0的结点。又称为终端结点。图9.11(b)中的结点K，L，F，G，M，I，J都是树的叶子。分支结点：度不为0的结点。又称为非终端结点。图9.11(b)中的结点A，B，C，D，E，H都是树的分支结点。9.2.1树及二叉树的概念树的一些基本术语：内部结点：除根结点之外的所有分支结点。树的度：树内各结点的度的最大值。图9.11(b)的树的度为3。孩子结点：结点的子树的根结点。相应地，该结点称为孩子结点的双亲结点。在图9.11(b)中，D为A的子树T3的根，则D是A的孩子结点，而A则是D的双亲结点。兄弟结点：同一个双亲的孩子结点之间互称为兄弟。例，H，I和J互为兄弟。9.2.1树及二叉树的概念树的一些基本术语：祖先结点：从根到该结点的所经分支上的所有结点。例如M的祖先结点为A，D和H。子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙结点。例如B的子孙结点有E，F，K，L。结点的层次：从根开始定义起，根为第一层，根的孩子为第二层，再下一层为第三层，依次类推。若某结点在第i层，则其子树的根就在第i+1层。9.2.1树及二叉树的概念树的一些基本术语：树的深度：树中结点的最大层次。又称树的高度。在图9.11(b)所示的树的深度为4。有序树：树中结点的各子树看成从左至右是有次序的，则称该树为有序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。无序树：树中结点的各子树没有次序的，孩子结点的顺序可以调整。9.2.1树及二叉树的概念1.二叉树的概念二叉树是另一种树型结构，它的特点是每个结点至多有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树是n(n≥0)个结点的有限集，当n>1时，有而仅有一个结点为根结点，其余结点构成为2个互不相交的子集T1、T2，其中每一个子集又是一棵二叉树，分别称作为根结点的左子树和右子树。9.2.1树及二叉树的概念1.二叉树的概念很显然，这也是一个递归定义，值得注意的是：二叉树不是度为2的树，在度为2的树中，当一个结点的度为1时，其子树是不考虑序的；而在二叉树中，当一个结点的度为1时，其子树要考虑序，即是作为双亲的左子树还是作为双亲的右子树。另外，树不允许为空树，但二叉树允许为空。9.2.1树及二叉树的概念1.二叉树的概念由二叉树的递归定义可知，二叉树有五种基本形态，如图9.13所示。9.2.1树及二叉树的概念和普通树相比，二叉树具有下列重要性质：当i=1时，只有一个根结点，2i-1=20=1，由于二叉树的每一个结点的度最多为2，因此当i≥2时，第i层上的结点数最多为上一层的2倍，所以第2层最多有2×1=21个结点，第3层最多有2×21=22个，依次类推，第i层最多有2×2i-1=2i个。性质1：在二叉树的第i层上的结点数最多为2i-1。9.2.1树及二叉树的概念和普通树相比，二叉树具有下列重要性质：由性质1可知，深度为k的二叉树的最大结点数为1+2+4+……2k-1=i-1=2k-1性质2：在深度为k的二叉树中至多有2k-1个结点(k≥1)。9.2.1树及二叉树的概念和普通树相比，二叉树具有下列重要性质：设在二叉树中，度为1的结点为n1，树的结点数n=n0+n1+n2。除根结点外每个结点有惟一的双亲结点指向该结点，所以度为1的结点指向一个后续，而度为2的结点指向两个后续，根结点没有指向的它双亲结点，因此，二叉树结点数n=n1+2*n2+1。n=n0+n1+n2=n1+2*n2+1

可得n0=n2+1。性质3：对于任何一个二叉树T，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。9.2.1树及二叉树的概念在二叉树中有两种特殊的二叉树——满二叉树和完全二叉树。满二叉树：一棵深度为k的二叉树，若其有2k-1个结点，则称为满二叉树。在满二叉树中只有度为0和度为2的结点，并且在每一层上的结点数都是该层所能取结点的最大值。如图9.14(a)所示为一个深度为4的满二叉树。9.2.1树及二叉树的概念在二叉树中有两种特殊的二叉树——满二叉树和完全二叉树。完全二叉树：一个深度为k的二叉树，其结点数n<2k-1，并且这n个结点所构成的二叉树，与一个深度为k的满二叉树的前n个结点的位置相同，则该树是一棵深度为k的完全二叉树。如图9.14(b)为一个深度为4，结点数为10的完全二叉树。9.2.1树及二叉树的概念完全二叉树有两个重要性质：证明：假设深度为k，则根据性质2和完全二叉树的定义有2k-1-1<n≤2k-1或2k-1≤n<2k即k-1≤log2n<k由于k为整数，所有k=[log2n]+1.性质4：具有n个结点的完全二叉树的深度为[log2n]+1。9.2.1树及二叉树的概念完全二叉树有两个重要性质：性质5：如果对一棵有n个结点的完全二叉树（深度为[log2n]+1）的结点按顺序标号，标号的顺序从根开始，按层次自上而下，在第一层上从左至右，如图9.14(b)所示的完全二叉树，就是按此规则标号，对于树中任意标号为I的结点有以下特性：i≠1时，i的双亲结点是[i/2]。若2i≤n，则i的左孩子是标号为2i的结点；若2i>n，则该结点不存在左孩子。若2i+1≤n，则i的右孩子是标号为2i+1的结点；若2i+1>n，则该结点不存在右孩子。9.2.2二叉树的建立1.二叉树的存储结构二叉树的存储结构和线性一样，有两种方式：顺序结构和链式结构。(1)顺序结构可以设想把二叉树中的各结点按一定次序排列成线性序，而且结点在这个序列中的相对位置能反映出结点之间的逻辑关系。然后分配一块连续的存储单元来存储二叉树。这种存储方法对于满二叉树和完全二叉树是非常适合的。9.2.2二叉树的建立例如，对于图9.15(a)的完全二叉树，按层给结点编号可用图9.15(c)的顺序结构来存储。9.2.2二叉树的建立对于图9.15(b)的一般二叉树，则可用图9.15(d)所示的顺序结构来存储。其中“0”表示该结点不存在。根据二叉树性质5，结点的编号（对应顺序存储结构中结点存放位置序号）中蕴含着结点之间的关系。例如，结点D（序号为4）的双亲为B（序号为4/2=2），左孩子为H（序号为4*2=8），右孩子为I（序号为4*2+1=9）。9.2.2二叉树的建立例如，对于图9.15(a)的完全二叉树，按层给结点编号可用图9.15(c)的顺序结构来存储。对于图9.15(b)的一般二叉树，则可用图9.15(d)所示的顺序结构来存储。其中“0”表示该结点不存在。根据二叉树性质5，结点的编号（对应顺序存储结构中结点存放位置序号）中蕴含着结点之间的关系。例如，结点D（序号为4）的双亲为B（序号为4/2=2），左孩子为H（序号为4*2=8），右孩子为I（序号为4*2+1=9）。9.2.2二叉树的建立显然，对于完全二叉树，采用顺序结构存储可节省空间。而对于一般二叉树，则会造成空间的极大浪费。可采用另一种有效的存储结构。9.2.2二叉树的建立(2)二叉树的链式存储结构定义两种结点形式：二叉结点，有一个数据域和两个分别指向左、右孩子的指针域；三叉结点，在二叉结点的基础上，增加一个指向其双亲的指针域即一个数据域和三个指针域。对于二叉结点可描述如下：structbitree{charch;structbitree*lchild,*rchild;}三叉结点的结构如下：structbitree{charch;srtuctbitree*lchild,*rchild,*parent;}9.2.2二叉树的建立定义了二叉结点和三叉结点之后，相应地可用二叉链表和三叉链表存储、表示图9.17(a)的二叉树，如图9.17(b)和图9.17(c)所示。9.2.2二叉树的建立用二叉链表存储表示树结构时，由任一结点可方便地找到子孙，但难以直接找到其双亲。而用三叉链表存储表示树结构却可以方便地找到双亲结点，但却需要额外的空间。实际应用中主要用二叉链表结构来存储二叉树。9.2.2二叉树的建立2、二叉树的建立在使用二叉树之前必须先建立二叉树，可以采用先序遍历的顺序进行创建，并输入数据，由键盘输入每个节点的数据，假设当输入为“.”时，当前操作的节点指针为NULL，采用先左子树后右子树的顺序函数根据输入数据的形式，生成相应的二叉树结构。建立二叉树的递归算法如下：建立二叉树：voidcreat_tree(bitree&T,charch){charch;scanf(“%c”,&ch);if(ch=='.')T=NULL;else{T=newbitnode;T->data=ch;creat_tree(T->lchild,ch);creat_tree(T->rchild,ch);}}9.2.3二叉树的遍历由二叉树的递归定义可知，二叉树是由三个基本单元组成，即根结点、左子树和右子树。因此，若能依次遍历出这三部分，便是遍历了整个二叉树。若以L，T，R分别表示遍历左子树、访问根和遍历右子树，则可有六种遍历方案：9.2.3二叉树的遍历六种遍历方案：TLR，LTR，LRT，TRL，RTL，RLT。通常限定先遍历左子树，后遍历右子树。所以，二叉树的遍历主要指前三种，分别称为先序遍历、中序遍历和后序遍历。9.2.3二叉树的遍历二叉树遍历的递归定义。1.先序遍历（TLR）算法先序遍历（也可以称为前序遍历）二叉树的操作定义为：若二叉为空，则空操作返回，否则：访问根结点；先序遍历左子树；先序遍历右子树。先序遍历的算法如下：voidprev(bitreeT){if(T!=NULL){printf(“%c”,T->data);prev(T->lchild);prev(T->rchi