【说明】<br />二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的..

免费智能真题库 > 历年试卷 > 程序员 > 2009年上半年程序员下午试卷案例

第3题

知识点：查找存储结构二叉查找树二叉排序树二叉树空指针排序指针

【说明】
二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：

若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；
若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；
左、右子树本身就是二叉查找树。

设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：

函数find_key(root, key)的功能是用递归方式在给定的二叉查找树(root指向根结点) 中查找键值为key的结点并返回结点的指针；若找不到，则返回空指针。

问题：3.1 【C函数】

问题：3.2 若某二叉查找树中有n个结点，则查找一个给定关键字时，需要比较的结点个数取决于（5)。


知识点讲解
· 查找 · 存储结构 · 二叉查找树 · 二叉排序树 · 二叉树 · 空指针 · 排序 · 指针

查找

1）顺序查找

顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。

2）折半查找

折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。

3）分块查找

在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。

4）哈希表及其查找

根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。

存储结构

邻接矩阵表示法

对于具有n个顶点的图G(V,E)来说，其邻接矩阵是一个n阶方阵，且满足

由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，有向图的邻接矩阵就不一定对称了。借助邻接矩阵易判定任意两个顶点之间是否有边（或弧）相连，并且容易求得各个顶点的度。

网（赋权图）的邻接矩阵可定义为

邻接链表表示法

邻接链表指的是为图的每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点v_i的边（对于有向图是以v_i为尾的弧）。邻接链表中的节点有表节点和表头节点两种类型。

邻接矩阵和邻接链表表示法对有向图和无向图都适用。

二叉查找树

二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树。

（1）若它的左子树非空，则左子树上所有结点的关键码值均小于根结点的关键码值；

（2）若它的右子树非空，则右子树上所有结点的关键码值均大于根结点的关键码值；

（3）左、右子树本身就是两棵二叉查找树。

一棵二叉查找树如下图（a）所示。下图（b）所示的二叉树不是二叉查找树，因为46比54小，它应该在根结点54的左子树上。

二叉查找树与非二叉查找树

从二叉查找树的定义可知，对二叉查找树进行中序遍历，可得到一个关键码递增有序的结点序列。

二叉排序树

二叉排序树又称为二叉查找树，它或者是一棵空树，或者是满足以下性质的二叉树。

（1）若它的左子树非空，则左子树上所有节点的值均小于根节点的值。

（2）若它的右子树非空，则右子树上所有节点的值均大于根节点的值。

（3）左、右子树本身就是两棵二叉排序树。

二叉排序树的查找过程是：若二叉排序树非空，则将给定值与根节点的关键字值相比较，若相等，则查找成功；若不等，则当根节点的关键字值大于给定值时，到根的左子树中进行查找；否则到根的右子树中进行查找。若找到，则查找过程是走了一条从树根到所找到节点的路径；否则查找过程终止于一棵空树。

二叉排序树中插入节点的操作：每读入一个元素，建立一个新节点，若二叉树非空，则将新节点的值与根节点的值相比较，如果小于根节点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空，则新节点作为二叉排序树的根节点。

二叉排序树中删除节点的操作：在二叉树中删除一个节点，不能把以该节点为根的子树都删除，只能删除这个节点并仍旧保持二叉排序树的特性，也就是说，删除二叉排序树上一个节点相当于删除有序数列中的一个元素。假设二叉排序树上的被删除节点为*p（p指针指向被删除节点），*f为其双亲节点，则删除节点*p的过程可分为以下3种情况。

①若*p节点为叶子节点，即p→lchild及p→rchild均为空，则由于删去叶子节点后不破坏整棵树的结构，因此只需修改*p节点的双亲节点*f的相应指针即可，即f→lchild（或f→rchild）=NULL。

②若*p节点只有左子树或者只有右子树，此时只要将*p的左子树或右子树接成其双亲节点*f左子树或右子树，即令f→lchild（或f→rchild）=p→lchild，或f→lchild（或f→rchild）=p→rchild。

③若*p节点的左、右子树均不空，则不能像上面那样简单处理，删除*p节点时应将*p的左子树、右子树连接到适当的位置，并保持二叉排序树的特性。可采用以下两种方法进行处理：一是令*p的左子树为*f的左（或右）子树，而将*p的右子树下接到*p的中序遍历的直接前驱节点*s的右孩子指针上；二是用*p的中序直接前驱（或后继）节点*s代替*p节点，然后删除*s节点。

二叉树

二叉树的定义

二叉树（Binary Tree）是n(n≥0)个节点的有限集合，它或者是空树（n=0），或者是由一个根节点及两棵互不相交的、分别称为左子树和右子树的二叉树所组成。

二叉树与树的区别如下。

.二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

.二叉树的节点的最大度为2，而树中不限制节点的度数。

二叉树的运算

二叉树的基本运算是遍历，其他运算可建立在遍历运算的基础上。

二叉树的性质

二叉树具有以下性质。

（1）二叉树第i层上的节点数目最多为2ⁱ^-1(i≥1)个。

（2）深度为k的二叉树至多有2^k-1(k≥1)个节点。

（3）在任意一棵二叉树中，若终端节点数为n₀，度为2的节点数为n₂，则n₀=n₂+1。

（4）具有n个节点的完全二叉树的深度为[log₂n]+1。

（5）对一棵有n个节点的完全二叉树的节点按层次自左至右进行编号，则对任意节点i有以下性质。

.若i=1，则节点i是二叉树的根，无双亲；若i>1，则其双亲为

。

.若2i>n，则节点i无左孩子；否则其左孩子为2i。

.若2i+1>n，则节点i无右孩子；否则其右孩子为2i+1。

若深度为k的二叉树有2^k-1个节点，则称其为满二叉树。

深度为k、有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树编号从1至n的节点一一对应时，称之为完全二叉树。

二叉树的存储结构

1）顺序存储结构

用一组地址连续的存储单元存储二叉树中的数据元素，必须把节点排成一个适当的线性序列，并且节点在这个序列中的相互位置能反映出节点之间的逻辑关系。

顺序存储结构用于完全二叉树时既简单又节省空间，而对于一般二叉树则不适用。因为在顺序存储结构中，以节点在存储单元中的位置来表示节点之间的关系，那么对于一般的二叉树来说，也必须按照完全二叉树的形式存储，也就是要添上一些实际并不存在的"虚节点"，这将造成空间的浪费。

2）链式存储结构

由于二叉树中的节点包含有数据元素、左子树根、右子树根及双亲等信息，因此可以用三叉链表或二叉链表来存储二叉树，链表的头指针指向二叉树的根节点。

二叉树的遍历

遍历是指按某种策略访问树中的每个节点，且仅访问一次。由于二叉树所具有的递归性质，一棵非空的二叉树可以看作由根节点、左子树和右子树三部分构成，因此若能依次遍历这三部分中的每个节点信息，也就遍历了整棵二叉树。按照遍历左子树要在遍历右子树之前进行的约定，根据访问根节点位置的不同，可得到二叉树的前序、中序和后序3种遍历方法。

遍历二叉树的基本操作就是访问节点，不论按照哪种次序遍历，对含有n个节点的二叉树，遍历算法的时间复杂度都为O(n)。在最坏情况下，二叉树是有n个节点且深度为n的单枝树，遍历算法的空间复杂度也为O(n)。

遍历二叉树的过程实质上是按一定规则，将树中的节点排成一个线性序列的过程，因此遍历操作得到的是树中节点的一个线性序列。在每一种序列中，有且仅有一个起始点和一个终节点，其余节点有且仅有唯一的直接前驱和直接后继。

对二叉树还可以进行层序遍历。层序遍历就是从树的根节点出发，首先访问第1层的树根节点，然后从左到右依次访问第2层上的节点，以此类推，自上而下、自左到右逐层访问树中各层上节点的过程。

线索二叉树

若n个节点的二叉树采用链表作存储结构，则链表中含有n+1个空指针域，利用这些空指针域来存放指向节点的前驱和后继信息。线索链表的节点结构如下图所示。

线索链表的节点结构

若二叉树的二叉链表采用上图所示的节点结构，则相应的链表称为线索链表，其中指向节点前驱、后继的指针称为线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

二叉树的应用：最优二叉树

霍夫曼树又称最优二叉树，是一类带权路径长度最短的树。

路径：是指从树中一个节点到另一个节点之间的通路，路径上的分支数目称为路径长度。

树的路径长度：是从树根到每一个叶子的路径长度之和。节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。

树的带权路径长度：指树中所有叶子节点的带权路径长度之和，记为

式中，n为带权叶子节点的数目；w_i为叶子节点的权值；l_i为叶子节点到根的路径长度。

霍夫曼树是指权值为w₁，w₂，…，w_n的n个叶子节点的二叉树中带权路径长度最小的二叉树。

构造最优二叉树的霍夫曼算法如下。

（1）根据给定的n个权值w₁，w₂，…，W_n构成n棵二叉树的集合F={T₁,T₂,…,T_n}，其中每棵二叉树T_i中只有一个带权为w_i的根节点，其左右子树均空。

（2）在F中选取两棵根节点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根节点的权值为其左、右子树根节点的权值之和。

（3）从F中删除这两棵树，同时将新得到的二叉树加入到F中。

重复（2）、（3），直到F中只含一棵树时为止。这棵树便是霍夫曼树。

树和森林

1）树的存储结构

.树的双亲表示法：用一组地址连续的单元存储树的节点，并在每个节点中附设一个指示器，指示其双亲节点在该存储结构中的位置。显然这种表示对于求指定节点的双亲或祖先都十分方便，但对于求指定节点的孩子及后代则需要遍历整个数组。

.树的孩子表示法：在存储结构中用指针指示出节点的每个孩子，由于树中每个节点的子树数目不尽相同，因此在采用链式存储结构时可以考虑多重链表。

.树的孩子兄弟表示法：又称二叉链表表示法。在链表的节点中设置两个指针域分别指向该节点的第一个孩子和下一个兄弟。利用这种存储结构便于实现树的各种操作。

2）树和森林的遍历

（1）树的遍历。树的遍历分为先根遍历和后根遍历两种。

.先根遍历：先访问树的根节点，然后依次先根遍历根的各棵子树。对树的先根遍历等同于对转换所得的二叉树进行先序遍历。

.后根遍历：先依次后根遍历树根的各棵子树，然后访问树根节点。树的后根遍历等同于对转换所得的二叉树进行中序遍历。

（2）森林的遍历。森林的遍历分为前序遍历和后序遍历两种。

.前序遍历森林：若森林非空，访问森林中第一棵树的根节点，前序遍历第一棵子树根节点的子树森林，再前序遍历除第一棵树之外剩余的树所构成的森林。

.后序遍历森林：若森林非空，后序遍历森林中第一棵树的子树森林，访问第一棵树的根节点，后序遍历除第一棵树之外剩余的树所构成的森林。

3）树、森林与二叉树的转换

（1）树、森林转换为二叉树。利用树的孩子兄弟表示法可导出树与二叉树的对应关系，在树的孩子兄弟表示法中，从物理结构上看与二叉树的二叉链表表示法相同，因此就可以用这种同一存储结构的不同解释将一棵树转换为一棵二叉树。

将一个森林转换为一棵二叉树的方法是：先将森林中的每一棵树转换为二叉树，再将第一棵树的根作为转换后的二叉树的根，第一棵树的左子树作为转换后二叉树根的左子树，第二棵树作为转换后二叉树根的右子树，第三棵树作为转换后二叉树根的右子树的右子树，以此类推，森林就可以转换为一棵二叉树。

（2）二叉树转换为树和森林。若二叉树非空，则二叉树根及其左子树为第一棵树的二叉树形式，二叉树根的右子树又可以看作一个由森林转换后的二叉树，应用同样的方法，直到最后产生一棵没有右子树的二叉树为止，这样就得到了一个森林。为了进一步得到树，可用树的二叉链表表示的逆方法，即节点的右子树的根、右子树的右子树的根……找出原本是同一个双亲的兄弟。二叉树转换为树或森林是唯一的。

空指针

标准预处理宏NULL（它的值为0，称为空指针常量）常用来表示指针不指向任何内存单元，可以把NULL赋给任意类型的指针变量，以初始化指针变量。例如：

需要注意：全局指针变量会被自动初始化为NULL，局部指针变量的初始值是随机的。编程时常见的一个错误是没有给指针变量赋初值。未初始化的指针变量可能表示了一个非法的地址，导致程序运行时出现内存访问错误，从而使程序异常终止。

排序

假设含n个记录的文件内容为｛R₁，R₂，…，R_n｝，其相应的关键字为｛k₁，k₂，…，k_n｝。经过排序确定一种排列｛R_j₁，R_j₂，…，R_jn｝，使得它们的关键字满足如下递增（或递减）关系：k_j₁≤k_j₂≤…≤k_jn（或k_j₁≥k_j₂≥…≥k_jn）。

指针

简单来说，指针是内存单元的地址，它可能是变量的地址、数组空间的地址，或者是函数的入口地址。存储地址的变量称为指针变量，简称为指针。指针是C语言中最有力的武器，能够为程序员提供极大的编程灵活性。

指针的定义

指针类型的变量是用来存放内存地址的，下面是两个指针变量的定义：

变量ptr1和ptr2都是指针类型的变量，ptr1用于保存一个整型变量的地址（称ptr1指向一个整型变量），ptr2用于保存一个字符型变量的地址（称ptr2指向一个字符变量）。

使用指针时需明确两个概念：指针对象和指针指向的对象。指针对象是明确命名的指针变量，如上例中的ptr1、ptr2；指针指向的对象是另一个变量，用“*”和指针变量联合表示，如上例中的整型变量*ptr1和字符变量*ptr2，由于上面的定义中未对ptr1和ptr2进行初始化，它们的初始值是随机的，也就是*ptr1和*ptr2可视为并不存在。

借助指针变量可以针对指定的地址进行操作，例如，设置地址为0x1234开始的存储空间存放一个整型变量的值0x5678，代码如下。

定义指针变量时需要在每个变量名前加“*”，如下：

指针的加减运算

对指针变量进行加减运算时，是以指针所指向的数据类型存储宽度为单位计算的。

例如，下面的指针p和s在进行加1运算时有不同的结果。

p+1实际上是按照公式p+1*sizeof（int）来计算的，s+1则是按照s+1*sizeof（char）进行计算。

空指针

“&”和“*”

“&”称为地址运算符，其作用是获取变量的地址。“*”称为间接运算符，其作用是获取指针所指向的变量。

例如，下面的语句“pa=&b；”执行后，变量pa就得到了b的地址（称为指针pa指向b），*pa表示pa指向的变量（也就是变量b）。

例如：

在上面的例子中，通过指针pa修改了变量b的值，本质上是对b的间接访问。在程序中通过指针访问数据对象或函数对象，提供了运算处理上的灵活性。

如果指针变量的值是空指针或者是随机的，通过指针来访问数据就是一种错误（在编译时报错，或者在运行时发生异常），下面的语句会产生一个运行时错误（vp可能表示了一个非法的地址，因此它所指向的对象*vp也是非法的）。

void*类型可以与任意的数据类型匹配。void指针在被使用之前，必须转换为明确的类型。例如：

指针与堆内存

在程序运行过程中，堆内存能够被动态地分配和释放，在C程序中通过malloc（或calloc、realloc）和free函数实现该处理要求。

例如：

在堆中分配的内存块的生存期是由程序员自己控制的，应在程序中显式地释放。例如：

注意：指针为空（指针值为0或NULL）时表示不指向任何内存单元，因此释放空指针没有意义。

因为内存资源是有限的，所以若申请的内存块不再需要就及时释放。如果程序中存在未被释放（由于丢失其地址在程序中也不能再访问）的内存块，则称为内存泄漏。持续的内存泄漏会导致程序性能降低，甚至崩溃。嵌入式系统存储空间非常有限，一般情况下应尽量采用静态存储分配策略。

指针与数组

通过指针访问数组元素

在C程序中，常利用指针访问数组元素，数组名表示数组在内存中的首地址，即数组中第一个元素的地址。可以通过下标访问数组元素，也可以通过指针访问数组元素。

例如：

数组arr的元素可以用*ptr、*（ptr+1）、*（ptr+2）、*（ptr+3）来引用。

数组名是常量指针，数组名的值不能改变，因此arr++是错误的，而ptr++是允许的。例如，下面的代码通过修改指针ptr来访问数组中的每个元素。

一般情况下，一个int型变量占用4个字节的内存空间，一个char型变量占用一个字节的空间，所以str是字符指针的话，str++就使str指向下一个字符；而整型指针ptr++则使ptr指向下一个int型整数，即指向数组的第二个元素。

可以用指针访问二维数组元素。例如，对于一个m行、n列的二维整型数组，其定义为

由于二维数组元素在内存中是以线性序列方式存储的，且按行存放，所以用指针访问二维数组的关键是如何计算出某个二维数组元素在内存中的地址。二维数组a的元素a[i][j]（ii][j]之前的元素所占空间形成的偏移量，概念上表示为a+（i×n+j）*sizeof（int），在程序中需要表示为（&a[0][0]+i×n+j）。

通过指针访问字符串常量

可将指针设置为指向字符串常量（存储在只读存储区域），通过指针读取字符串或其中的字符。例如，

不允许在程序运行过程中修改字符串常量。例如，下面代码试图通过修改字符串的第2个字符将“hello”改为“hallo”，程序运行时该操作会导致异常，原因是str指向的是字符串常量“hello”，该字符串在运行时不能被修改。

如果用const进行修饰，这个错误在编译阶段就能检查出来，修改如下：

指针数组

如果数组的元素类型是指针类型，则称之为指针数组。下面的ptrarr是一维数组，数组元素是指向整型变量的指针。

若需要动态生成二维整型数组，则传统的处理方式是先设置一个指针数组arr2，然后将其每个元素的值（指针）初始化为动态分配的“行”。

指针运算

在C程序中，对指针变量加一个整数或减一个整数的含义与指针指向的对象有关，也就是与指针所指向的变量所占用存储空间的大小有关。例如：

常量指针与指针常量

常量指针是指针变量指向的对象是常量，即指针变量可以修改，但是不能通过指针变量来修改其指向的对象。例如，

指针常量是指针本身是个常量，不能再指向其他对象。

在定义指针时，如果在指针变量前加一个const修饰符，就定义了一个指针常量，即指针值是不能修改的。

指针常量定义时被初始化为指向整型变量d。p本身不能修改（即p不能再指向其他对象），但它所指向变量的内容却可以修改，例如，*p=5（实际上是将d的值改为5）。

区分常量指针和指针常量的关键是“*”的位置，如果const在“*”的左边，则为常量指针，如果const在“*”的右边则为指针常量。如果将“*”读作“指针”，将const读作“常量”，内容正好符合。对于定义“int const *p；”p是常量指针，而定义“int* const p；”p是指针常量。

指针与函数

指针可以作为函数的参数或返回值。

指针作为函数参数

函数调用时，用指针作为函数的参数可以借助指针来改变调用函数中实参变量的值。以下面的swap函数为例进行说明，该函数的功能是交换两个整型变量的值。

若有函数调用swap（&x，&y），则swap函数执行后两个实参x和y的值被交换。函数中参与运算的值不是pa、pb本身，而是它们所指向的变量，也就是实参x、y（*pa与x、*pb与y所表示的对象相同）。在调用函数中，是把实参的地址传送给形参，即传送&x和&y，在swap函数中指针pa和pb并没有被修改。

如果在被调用函数中修改了指针参数的值，则不能实现对实参变量的修改。例如，下面函数get_str中的错误是将指针p指向的目标修改了，从而在main中调用get_str后，ptr的值仍然是NULL。