下图所示为一个二叉排序树（二叉査找树)，其先序遍历序列为（）。<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

相关试题查找算法

第38题

2019年下半年

对关键码序列{12,15，18，23, 29, 34, 56, 71, 82}进行二分查找（折半查找），若要查找关键码71，则(38)。

第39题

2010年下半年

对n个元素的有序表A[1..n]进行二分（折半）查找，则成功查找到表中的任意一个元素时，最多与A中的（39)个元素进行比较。

第39题

2014年下半年

在数据结构中，(39)是与存储结构无关的术语。

知识点讲解

· 动态查找表

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

· 二叉排序树

· 排序

动态查找表

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

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