第九章链表和二叉树：链表概念、操作及存储特点解析

第九章涵盖了链表与二叉树的内容，其中9.1节专门介绍链表，包括9.1.1节对链表概念的阐述、9.1.2节对链表操作的讲解以及9.1.3节对循环链表的介绍。链表是一种线性表，由若干个同类型的数据元素构成，这些元素按照一定的顺序排列。具体来说，它由n个（n大于等于0）元素a1、a2、a3、……、an组成，形成一个有限序列，用LIST=(a1,a2,a3,……,an)来表示。在这个序列中，a1是起始结点，an是终止结点，而n则代表了线性表的长度。当n等于零时，表示为空表。元素ai的前一个元素是ai减一，后一个元素是ai加一。线性表的存储结构分为两种：一种是顺序存储结构，另一种是链式存储结构。顺序存储结构指的是通过一组连续的存储单元，依次存放线性表的各个数据元素。链表，即线性表的链式存储结构，通常被这样称呼。数据元素的存储方式涉及使用一组任意的存储单元，这些单元的排列可以是连续的，亦可以是分散的。在链表中，每个元素不仅要保存自身的资料，还需保留指向后续元素的信息。这样的存储单元被称作结点。其中，用于存放指向后续结点位置的特定区域被称为指针域，而存放数据元素信息的区域则称为数据域。通过指针相互连接的结点集合构成了链表。链表是一种数据结构，其中每个节点能够包含多个数据区域和指针区域。仅包含一个指针区域的链表被称为单链表。在本章内容中，除非有特殊说明，否则提到的链表均指代单链表。每个节点对应表中的一行，节点包含六个数据区域：学号、姓名、语文成绩、数学成绩、英语成绩、计算机成绩以及总分；此外，节点还包含一个指向下一个节点的指针域，称为link。structCJ{charxh;charxm;

该指令禁止对特定内容进行修改，包括但不限于intsx、intyy、intjsj以及intzf等。

存在一个结构体指针`struct CJ*link`，设有n位个体，每位个体的数据域分别标记为a1，a2，……，an。链表的起始指针`head`指向链表首个节点的存储位置。线性表的末尾节点指针被设为“空”（NULL）。若`head`的值为NULL，则表示其所指向的链表为空链表。为了便于操作，我们在链表前添加了一个头结点，该头结点的数据部分并无实际意义，但其指针部分指向线性表的起始结点。同时，链表的首指针head被设置为指向这个头结点。当头结点的指针部分显示为“空”（即NULL）时，这表明链表处于空状态。9.1.1节将介绍链表的基本概念。

链表属于一种非直接访问的存储方式，每个节点的存储位置都由其前一个节点的指针域中的指针所指向。因此，我们必须从链表的起始指针出发，沿着指针链依次追踪，才能到达需要访问的特定节点。链表的头部指针域设定为31，故首要任务是定位至该链表的起始节点，即内存地址为31的节点a1；随后，借助a1的指针域，我们能够追踪到下一个节点的存储位置，即1号地址上的节点(a2)；此过程不断重复，便能成功追踪到节点a3、a4。链表是一种动态的存储结构，其占用的存储空间是在程序运行过程中动态分配的。当链表需要添加一个新节点时，必须向系统申请相应的存储空间。而在删除一个节点后，需要将这个节点占用的存储空间释放，并将其归还给系统。以p为例，它是一个指向节点的指针变量。

此时，p所指示的节点尚未形成，必须为p申请一个新节点，具体操作是执行p=newCJ；同理，当p所指向的节点不再被使用时，必须释放该节点的存储空间，操作方式为。

对函数p进行操作，按照9.1.2节所述，链表的操作包括：首先创建一个节点p，将其设为链表的头节点，接着连续创建新的节点q，将q的数据域设定为特定值，指针域初始化为空（NULL），并将q链接到链表的末尾。在整个过程中，节点p始终指向链表的最后一个节点。包含CJ类型的指针head、p和q；定义create函数，接收一个整数n作为参数；在函数内部，声明整型变量i；创建一个新的CJ类型的对象p，并为其分配存储空间；将p赋值给head指针；使用for循环，从1开始到i小于xh，进行循环；在循环中，输入每一项的值。

读取q结构体的姓名字段，输入李绯；读取q结构体的语文成绩字段，输入85；读取q结构体的数学成绩字段，输入90；读取q结构体的英语成绩字段，输入78；读取q结构体的综合成绩字段，输入92；读取q结构体的总分字段，输入345；将q的指针指向NULL；将p的指针指向q；将p更新为q；执行create(3)函数后，输入的信息依次为04253101，王小霞，56，85，45，93，278，04253102，张海涛，76，48，83，65，272，生成的链表结构如下所示。9.1.2链表操作之插入节点：若需在链表中的元素a与b之间插入新元素x，且已知p是指向元素a所在节点的指针，具体操作可参照图9.5进行。若s是指向节点x的指针，那么操作可表述为：将s的link指向p的link，同时将p的link指向s。至于链表的其他操作，遵循同样的原则。在成绩管理系统中，若需在第2条和第3条记录之间新增一条记录，过程与此类似。将存储空间分配给待插入的记录（以指针s表示），接着寻找编号为04253102的记录（记为p），并更新s的指针域，使其指向p的link。随后，调整p的指针域，使其指向s。初始化指针CJ、head、p和s；定义函数insert，接收整数i作为参数；初始化指针p指向head，并设置计数器j为1；在p不为空且j小于i的情况下，循环查找第i-1个节点；如果p为空，则输出“已到表尾！”信息。对结点进行删除操作时，首先需将指针p定位至目标结点的前一个结点；接着，将p的指针域更新，使其指向目标结点的下一个结点；最后，释放目标结点的内存空间。删除操作的具体步骤是：首先，将指针q指向p的link域，接着将p的link域更新为q的link域，之后释放q所指向的内存空间。以成绩管理系统为例，若需删除学号xh为04253102的记录，需先找到该记录的前一个记录，并调整其指针，使其指向04253102记录的后继，最后释放04253102记录所占用的内存。CJ指针head、p、q；执行delete_link函数时，需要传入整数i；此时，声明CJ类型的指针p、q，以及整型变量j；初始化p指向head，j的值为1；进入while循环，条件是p不为空且j小于i；在循环体内，如果p不为空，则j自增；若j达到i，则跳出循环；若p为空，表示链表中不存在第i-1个结点，此时输出提示信息。

若将链表的末尾结点的指针指向链表的首个结点地址，则整个链表将形成一个闭环，此类链表被称作循环链表。循环链表的各个节点相互连接形成一个闭环，无论从哪个节点开始，都能遍历整个链表中的所有节点。此外，还可以在链表中添加一个特殊的头节点。其逻辑结构如图9.1.3所示。循环链表的操作与线性链表大体相同，唯一的区别在于，在算法中，循环结束的条件不是判断p或p->link是否为NULL，而是它们是否与头指针相等。在循环链表中，有时我们只设置尾指针而不设置首指针，这样做可以简化一些操作。以循环链表为例，比如将两个循环链表合并为一个，只需交换两个链表的尾指针即可。假设合并后的链表由指针a和b分别指向各自的尾结点，并且它们都带有头结点。合并操作的具体步骤与方法是：首先，将p的link指向a的link，接着，将q的link指向b的link；然后，将a的link设置为q的link；再将b的link设置为p；最后，释放q所占用的内存。此外，二叉树的单链表本质上是一种线性结构，除了首尾元素外，其余每个元素都只有一个直接的前一个元素和一个直接的后一个元素。二叉树作为非线性结构中的一种，主要探讨的是层级与分支的关联性，具体来说，除了拥有一个根节点之外，其余每个节点均存在一个唯一的前驱节点；此外，每个节点还可以拥有零个或多个后续节点。在现实世界中，诸多问题可通过树状结构来形象地表达。比如，家族的血统关系就能用这种结构来展现。以李大民为例，他有三个孩子：李一杨、李一力和李一军。其中，李一杨又有一个儿子名叫李辉，而李一力则有两个子女，分别是李晓和李亮。这种关联性可以借助树形结构来直观地展现。具体可参照图示。在9.2.1节中，我们探讨了树与二叉树的基本概念。树的定义如下：上图中展示的图形，其形状与一棵倒置的树木颇为相似。

树木是由若干个节点构成的有限集合。在每一棵树木中，都存在一个被特别标识为根节点的唯一节点；当节点数量超过一个时，剩余的节点可以被划分为若干个互不重叠的有限子集T1，T2，……，Tm，每个子集本身也构成一棵树木，并被称作根节点的子树。9.2.1树和二叉树的定义包括：(a)具有一个根节点的树；(b)拥有13个节点，根节点为A，其余节点分为三个互不重叠的集合：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.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.11(b)中，该树的度为3。孩子结点是指子树的根结点，而相应的结点则被称为孩子结点的双亲结点。图9.11(b)中，点D作为A的子树T3的根部，故D可被视为A的子节点，与此同时，A成为D的父节点。所谓兄弟节点，是指拥有相同父节点的子节点相互称呼。比如，H、I和J便互为兄弟节点。接下来，我们探讨树以及二叉树的基本概念。在树的术语中，我们提到祖先节点，指的是从树根出发，至该节点所经过的所有节点。以M为例，其祖先节点包括A、D和H。子孙结点指的是以某个结点作为根基的子树中，任何其他的结点都被称作该结点的子孙结点。比如，结点B的子孙结点包括了E、F、K和L。至于结点的层次，则是从根结点开始进行定义，根结点被划分为第一层，而根结点的直接子结点则被划分为第二层，以此类推。每一层的下一层即为第三层，如此递增。如果一个结点位于第i层，那么它所拥有的子树的根结点就会位于第i+1层。树及二叉树的基本术语包括：树的深度，即树中节点的最大层级，也称作树的高度；例如，图9.11(b)中展示的树的深度是4。此外，有序树是指树中每个节点的子树按照从左到右的顺序排列，此时，最左侧子树的根节点被称为第一个孩子，而最右侧子树的根节点则被称为最后一个孩子。无序树中，各个节点的子树排列无固定顺序，孩子节点的排列顺序可以随意调整。在树及二叉树的概念中，二叉树是一种特殊的树形结构，其特点是每个节点最多拥有两个子树，即二叉树中不存在度数超过2的节点。此外，二叉树的子树有左右之分，且这种左右顺序是不可随意更改的。二叉树由n个节点组成，其中n的取值范围是大于等于0的整数。当节点数超过1时，存在一个唯一的根节点，而其他节点则被划分为两个互不重叠的子集T1和T2。这两个子集各自也是一棵二叉树，分别对应根节点的左子树和右子树。二叉树这一概念显而易见，它是一种递归定义。需要特别指出的是，二叉树并非指度为2的树。在度为2的树中，若一个节点度为1，其子树无需考虑顺序；然而，在二叉树中，若一个节点度为1，其子树则需考虑顺序，即它作为双亲的左子树还是右子树。此外，树不允许为空，而二叉树则可以允许为空。二叉树的基本概念，通过其递归定义可以明确，该结构具备五种典型的形态，具体如图9.13中所示。9.2.1相较于普通树，二叉树具有以下显著特性：首先，它仅含有一个根节点，即当i等于1时，2i-1等于20，也就是1。其次，由于二叉树的每个节点最多只能有两个子节点，即度数为2，因此从第二层开始，每一层的节点数都是上一层的两倍。具体来说，第二层最多有2×1=21个节点，第三层则有2×21=22个节点，以此类推，第i层最多有2×2i-1=2i个节点。性质1指出，二叉树的第i层最多可拥有2i-1个节点。与普通树相比，二叉树具有以下显著特性：根据性质1，我们可以推导出，深度为k的二叉树所能达到的最大节点数是1加上2加上4，以此类推，直至2的k次方减1，即等于2的k次方减1。性质2进一步说明，在深度为k的二叉树中，其节点数量不会超过2的k次方减1（其中k大于等于1）。在比较树与二叉树的概念时，我们可以发现二叉树具有一些显著的重要性质。具体来说，在二叉树中，我们设度为1的节点数量为n1，而整个树的节点总数n则可以表示为n0、n1和n2三个部分之和。每个结点除了根结点外，都只有一个指向它的父结点，因此，度为1的结点对应一个直接后继，度为2的结点则对应两个后继。根结点没有父结点，所以它没有指向的父结点。基于此，二叉树的结点总数n可以表示为n1加上2倍的n2再加1。同时，结点总数n也可以表示为n0、n1和n2的总和，即n=n0+n1+n2，这与n=n1+2*n2+1的表达式是等价的。

可得n0等于n2加1。性质3指出，对于任意一个二叉树T，如果它的叶子节点数量为n0，而度为2的节点数量为n2，那么n0就等于n2加1。在二叉树的范畴内，存在两种独特的二叉树类型——满二叉树与完全二叉树。所谓满二叉树，指的是深度为k的二叉树，当且仅当它拥有2k减1个节点时，它便被定义为满二叉树。满二叉树的节点仅包含度为0和度为2的类别，并且每一层的节点数量均达到该层可能的最大节点数。例如，图9.14(a)展示了一棵深度为4的满二叉树。在二叉树的分类中，存在两种特殊类型：满二叉树与完全二叉树。完全二叉树指的是，若一棵二叉树的深度为k，且其节点总数为n，那么该树中的任意节点，若其编号为n，则该节点不拥有左孩子。若2i加1小于等于n，那么i节点的右孩子即为编号为2i加1的节点；反之，若2i加1大于n，则该节点没有右孩子。在9.2.2节中，关于二叉树的建立，首先介绍二叉树的存储结构，其与线性结构相似，主要有两种形式：顺序存储结构和链式存储结构。二叉树中的各个节点可以按照某种顺序排列成一条线性序列，并且这些节点在序列中的相对位置能够揭示它们之间的逻辑联系。基于此，我们可以为二叉树分配一块连续的存储空间。这种方法特别适用于满二叉树和完全二叉树。在构建二叉树的过程中，以图9.15(a)中的完全二叉树为例，我们可以按照层次对节点进行编号，并利用图9.15(c)中展示的顺序结构进行存储。至于图9.15(b)中的一般二叉树，则可以采用图9.15(d)所展示的顺序结构进行存储。在这种存储方式中，数字“0”被用来表示节点不存在。依据二叉树的第五个特性，节点的标识（即顺序存储结构中节点存放的序号）实际上反映了节点间的相互联系。比如，节点D（其序号为4）的父节点是B（其序号为4除以2等于2），其左子节点是H（其序号为4乘以2等于8），而其右子节点是I（其序号为4乘以2再加1等于9）。例如，针对图9.15(a)所展示的完备二叉树，我们可以依照层级的顺序对节点进行编号，并利用图9.15(c)中展示的顺序结构进行存储。至于图9.15(b)所呈现的普通二叉树，我们可以采用图9.15(d)中展示的顺序结构进行存储。在此结构中，“0”代表该节点不存在。依据二叉树的第五个特性，节点的标识（即顺序存储结构中节点存放的序号）实际上揭示了节点间的相互联系。比如，节点D（其序号为4）的父节点是B（其序号为4除以2等于2），其左子节点是H（其序号为4乘以2等于8），而右子节点是I（其序号为4乘以2再加1等于9）。显而易见，在完全二叉树中，采用顺序存储方式能够有效减少空间占用。对于常规的二叉树，往往会导致大量空间的无效占用。我们可以采用一种更为高效的存储方式。在9.2.2节中，关于二叉树的构建（第二部分），我们定义了两种节点类型：二叉节点，它包含一个数据区域和两个分别指向其左右子节点的指针区域；而三叉节点，则是在二叉节点的基础上，额外增加了一个指向其父节点的指针区域，因此它包含一个数据区域和三个指针区域。关于二叉结点的结构，可以这样表述：它是一个包含字符类型的数据域和两个指向二叉结点的指针域的结构体，分别表示左子结点和右子结点。至于三叉结点，其结构则包括一个字符类型的数据域，以及三个指向结构体的指针域，分别指向左子结点、右子结点和父结点。在定义了二叉结点和三叉结点之后，我们可以利用二叉链表和三叉链表来存储和表示图9.17(a)所示的二叉树，具体表现形式如图9.17(b)和图9.17(c)所示。在采用二叉链表来存储表示二叉树的结构时，我们可以轻松地定位到任意节点的子节点，然而，直接追踪到该节点的父节点却相对困难。相反，若使用三叉链表来存储树结构，我们能够便捷地找到父节点，但这会带来额外的空间需求。在实际情况中，二叉链表结构更常被用于二叉树的存储。在运用二叉树前，需首先构建该树。此过程可通过遵循先序遍历的规则来完成，并需输入数据。具体做法是，通过键盘输入每个节点的具体数据。当输入“.”时，意味着当前操作的节点指针应设置为NULL。按照先左子树后右子树的顺序，根据输入数据的形态，生成相应的二叉树结构。创建二叉树的递归方法如下：首先，构建二叉树：声明一个void类型的函数creat_tree，其参数为指向二叉树节点的指针T和字符ch。在函数中，首先将ch赋值给T的数据域，然后读取一个字符ch，如果ch等于点号'.'，则将T设置为NULL；否则，创建一个新的二叉树节点T，将ch赋值给T的数据域，然后递归调用creat_tree函数分别创建T的左子树和右子树。关于二叉树的遍历，根据二叉树的递归定义，我们可以知道，二叉树由三个基本部分构成，分别是根节点、左子树以及右子树。依次完成对这三部分的遍历，即可实现对整棵二叉树的遍历。采用L、T、R分别代表遍历左子树、访问节点以及遍历右子树，我们可以得到六种不同的遍历方式：TLR、LTR、LRT、TRL、RTL、RLT。在这些方案中，普遍的做法是先遍历左子树，接着是遍历右子树。因此，二叉树的遍历主要涉及前三种方式，它们分别是先序遍历、中序遍历以及后序遍历。在9.2.3节中，我们将探讨二叉树遍历的递归定义。首先，我们来看先序遍历（也称作前序遍历）的算法。其操作定义如下：若二叉树为空，则执行空操作并返回；否则，依次进行以下步骤：访问根节点；对左子树进行先序遍历；对右子树进行先序遍历。先对二叉树进行前序遍历的算法表述如下：定义一个函数prev，参数为二叉树的根节点T，执行如下步骤：如果T不为空，则输出T的数据字符；然后递归调用prev函数对T的左子树进行遍历；最后递归调用prev函数对T的右子树进行遍历。以图9.18所示的二叉树为例，若按照前序遍历，其递归调用序列和访问顺序依次为：ABDGECF。将这些访问到的节点按照访问的先后顺序排列，便得到该二叉树的前序遍历序列。二叉树的遍历具有递归的特性。具体到中序遍历（LTR）的递归算法，其操作过程可以这样定义：当二叉树为空时，执行空操作并返回；反之，则需依次进行：中序遍历左子树，访问根节点，然后中序遍历右子树。中序遍历算法的具体实现如下：首先，检查二叉树节点T是否为空；如果不为空，则对T的左子树进行中序遍历，接着输出节点T的数据，最后对T的右子树进行中序遍历。以图9.18所示的二叉树为例，进行中序遍历后，可以得到该树的中序序列为DGBEAFC。9.2.3二叉树的遍历二叉树遍历的递归定义。在后序遍历（LRT）递归算法中，对二叉树的中序遍历操作规定如下：若二叉树为空，则执行空操作并返回；反之，则需依次进行以下步骤：先后序遍历左子树，再后序遍历右子树，最后访问根节点。具体实现如下：定义一个函数prev(bitreeT)，其中，如果T不为空，则调用pos(T->lchild)进行左子树的后序遍历，接着调用pos(T->rchild)进行右子树的后序遍历，最后输出T->data的值。对于图9.18所示的二叉树，进行中序遍历后，可以得到其后序序列为GDEBFCA。

二叉树的遍历表明，任何一棵二叉树的节点先序序列和中序序列都是独一无二的。然而，当我们仅拥有节点的先序序列和中序序列时，能否据此确定一棵特定的二叉树？这种确定是否也是唯一的呢？在二叉树的遍历实例中，已知节点的先序序列和中序序列分别为：先序序列为ABCDEFG，中序序列为CBEDAFG。通过先序序列可以确定二叉树的根节点为A，进而得出其左子树的中序序列为CBED，右子树的中序序列为FG。反之，通过中序序列CBEDAFG，可以推断出左子树的先序序列必然包含BCDE，而右子树的先序序列则为FG。通过左子树的先序和中序序列，我们可以构建出节点A的左子树；同样，利用右子树的先序和中序序列，我们可以构造出节点A的右子树。对于二叉树的遍历，如果已知某个节点的后序和中序序列，我们同样可以唯一确定这棵二叉树的结构。