下图所示为一个二叉排序树（二叉査找树)，其先序遍历序列为（）。<br /> <span s..

" /> " />

2020年下半年上午试卷综合知识

第 38 题


知识点	动态查找表树的存储结构及遍历操作二叉排序树排序
关键词	遍历二叉排序树排序
章/节	常用数据结构常用算法

下图所示为一个二叉排序树（二叉査找树)，其先序遍历序列为（）。

A. 12,15,18,23,29,34,56,71

B. 12,18,15,34,29,71,56,23

C. 23,15,56,12,18,29,71,34

D. 23,15,12,18,56,29,34,71

相关试题常用算法

第42题

2016年上半年

对n个记录进行非递减排序，在第一趟排序之后，一定能把关键码序列中的最大或最小元素放在其最终排序位置上的排序算法是（42）。

第41题

2013年下半年

在一棵非空的二叉排序树(二叉查找树)中，进行(41)遍历运算并输出所访问结点的关键码后，可得到一个有序序列。

第41题

2019年上半年

对于给定的关键字序列｛47，34，13，12，52，38，33，27, 5｝，若用链地址法（拉链法）解决冲突来构造哈希表，且哈希函数为H（key）=key%11，则（）。

知识点讲解

· 动态查找表

· 树的存储结构及遍历操作

· 二叉排序树

· 排序

动态查找表

若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表。动态查找表的特点是表结构是动态生成的。

1）二叉排序树的定义

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

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

.若它的右子树非空，则右子树上所有节点的值均大于或等于根节点的值。

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

2）二叉排序树的查找过程

若二叉树为非空，将给定值与根节点的关键字值进行比较，若相等，则查找成功；若不等，则当根节点的关键字值大于给定值时，到根的左子树中进行查找；否则到根的右子树进行查找。

3）二叉排序树中插入节点的操作

二叉排序树是通过依次输入数据元素并把它们插到二叉树的适当位置上构造起来的，具体过程如下：读入一个元素，建立一个新节点。若二叉排序树非空，则将新节点的值与根节点的值进行比较，如果小于根节点的值，则插入左子树中，否则插入右子树中；若二叉树为空，则新节点作为二叉排序树的根节点。

4）二叉排序树中删除节点的操作

在二叉排序树中删除一个节点，不能把以该节点为根的子树都删除，只能删除这个节点并仍旧保持二叉排序树的特性。

树的存储结构及遍历操作

1）树的存储结构

树是非线性的结构，存储树时，须把树中节点之间存在的关系反映在树的存储结构中。树有很多存储结构，这里仅介绍最常用的两种。

（1）树的标准存储结构。

树的标准存储结构由节点的数据和指向子节点的指针数组组成；对于度为M的树，其指针数组中的元素个数为M。

（2）树的带逆存储结构。

由于树的带逆存储结构需要一个从子节点指向父节点的指针，因而该结构在标准存储结构的基础上，需要在树的节点中增加一个指向其双亲节点位置的指针。

2）树的遍历

树的遍历是树的基本操作之一，也是最重要的操作之一。树的遍历含义是指：按照某种要求依次访问树中的每个节点，每个节点均被访问一次且仅被访问一次。常用的树的遍历方法可分为前序遍历、后序遍历和中序遍历。

（1）树的前序遍历。

首先访问根节点，然后从左到右前序遍历根节点的各棵子树。树的前序遍历递归算法如下：

若利用栈来记录当前未访问完的子树的根节点指针，则前序遍历的非递归算法如下：

（2）树的后序遍历。

树的后序遍历的基本思想是：先依次遍历每棵子树，然后访问根节点，与后序遍历二叉树相同。树的后序遍历递归算法如下：

（3）树的中序遍历。

树的中序遍历的基本思想是：先左子树，遍历根节点，然后依次遍历其他各棵子树，类似二叉树的中序遍历。树的中序遍历递归算法如下：

二叉排序树

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

（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节点。

排序

假设含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）。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5