2010考研真题点评
&您现在的位置：&&&&&拓展资源&&&&考研指导&&&&正文
2010考研真题点评
2010年考研计算机专业综合考试是统一命题后的第二次考试。本次考试统考科目仍然包括四门计算机专业课：数据结构 计算机 组成原理 、操作系统和计算机网络，这四门课程合在一起称为计算机科学专业基础综合，共150分。其中数据结构仍然占45分。
总体上来看，2010年的考研数据结构试题仍然注重对基础知识的考察。重点考察的是对基本知识点、基本概念的理解及应用。题目的难度适中，没有出现超出考试大纲的题目，也没有一眼就能看出答案的题目；在基础题中又有拔高，本次考试并非考查基本概念的填空，考题比较灵活，重点考察了对基础知识的应用能力、应变能力和实际动手能力。 与2009年的考研数据结构试题相比，难度略有提高，考察的内容更加深入、灵活，并且有针对性。
下面我们对2010的考研计算机专业综合考试进行简要的分析。
一、单项选择题
这部分共有40个选择题，每题2分，共80分。
单选题覆盖了大纲列出的各章的知识点，主要考察对各种数据结构、基本查找和排序算法的基本概念和特点的理解 以及灵活运用。1-11题是数据结构部分的试题。
1．若元素 a 、b 、c 、d 、e 、f 依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（ ）
A．dcebfa B．cbdaef C．bcaefd D．afedcb
点评： 此题考察对栈的基本操作（进栈、退栈）的理解和应用。栈的特点是后进先出。 若元素 a 、b&、c 、d 、e 、f 依次进栈，要得到出栈序列afedcb，需要进行的操作为：a进栈，a出栈，b，c，d，e，f 分别进栈，然后 f，e，d，c，b分别依次出栈，连续出栈操作超过3次。故答案为D。
2．某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。
A．bacde&& B．dbace& &C．dbcae&& D．ecbad
点评：此题考察对可以两端入队，一端出队的队列的操作。一般教材中讨论的队列都是一端入队，一端出队，而本题中的队列可以两端入队，一端出队，入队出队操作要复杂一些，是对教材内容的深化。对于序列 dbcae ，要先得到 d，a，b，c必须先从一端入队，d再从另一端入队，d出队得到序列中的d，但队列是先进先出，下面要得到b，而b是在a之后进队的，只有a先出队，b才能出队，故得不到所要求的序列。所以答案为C。
3．下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。
740)this.width=740">&
点评：此题考察对后序线索树的定义的理解。先得到后序序列为dbca，然后在后序线索树中将空的左孩子域指向其后序前驱，空的右孩子域指向其后序后继，因此答案为D。
4．在下列所示的平衡二叉树中插入关键字4后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点保存的关键字分别是（ ）。
740)this.width=740">&
A．13 ， 48&&&& &B．24 ， 48&&&& &C．24 ， 53&&&& &D．24 ， 90
点评： 此题考察对平衡二叉树插入操作的理解及应用，要熟悉平衡二叉树调整平衡的4种旋转方法。48插入后作为37的右孩子，此时破坏了二叉树的平衡，需旋转，旋转类型为RL型，根据RL型的操作可知答案为C。
5．在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为 的结点，则数T的叶结点个数是（ ）。
A．41&&& B．82&&& C．113&&& D．122
点评：此题考察对树中度、结点、叶子结点个数的计算。一般教材中多是对二叉树的讨论，二叉树性质3有结论：n0=n2+1。而本题是一棵度为4的树，因此需要引深。 n0=n2+2*n3+3*n4+1=1+2*10+3*20+1=82。故答案为B。
6．对n(n≥2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。
A．该树一定是一棵完全二叉树
B．树中一定没有度为1的结点
C．树中两个权值最小的结点一定是兄弟结点
D．树中任一非叶结点的权值一定不小于下一层任一结点的权值
点评： 此题考察对哈夫曼树的特性的理解。根据哈夫曼算法哈夫曼树中没有度为1的结点， 两个权值最小的结点一定是兄弟结点，任一非叶结点的权值一定不小于下一层任一结点的权值，但 哈夫曼树不是一棵 完全二叉树。因此答案是A。
7．若无向图 G=(V ， E) 中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（ ）。
A．6&&&&& B．15&&&&& C．16&&&&& D．21
点评： 此题考察对图的连通性的理解。一个有n个顶点的图要连通至少需要n-1条边。故答案是A。
8．对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。
740)this.width=740">&
A．4&&&&&&&&&& B．3&&&&&&&&&& C．2&&&&&&&& D．1
点评： 此题考察对拓扑序列的理解。拓扑序列不唯一。根据拓扑序列的求法可知此题有3个不同的拓扑序列 。故答案为B。
9．已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是（ ）
A．4 B．5 C．6 D．7
点评： 此题考察对折半查找最坏情况下的查找长度的理解。折半查找的查找过程可用一棵判定树来表示，折半查找失败时的过程对应判定树中从根结点到某个含空指针的结点的路径，因此，折半查找失败时关键字的比较次数最多不超过判定树的深度。n个结点的判定树的深度和n个结点的完全二叉树的深度相等，均为 log 2 n +1 。故答案为B。
10．采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（ ）
A．递归次数与初始数据的排列次序无关
B．每次划分后，先处理较长的分区可以减少递归次数
C．每次划分后，先处理较短的分区可以减少递归次数
D．递归次数与每次划分后得到的分区处理顺序无关
点评： 此题考察对递归方式下的 快速排序 算法的理解与应用。 快速排序的 递归的次数与 初始 数据的排列顺序有关， 递归次数与每次划分后得到的分区处理顺序无关。故答案为D。
11．对一组数据（ 2 ， 12 ， 16 ， 88 ， 5 ， 10 ）进行排序，若前三趟排序结果如下：（ ）
第一趟： 2 ， 12 ， 16 ， 5 ， 10 ， 88
第二趟： 2 ， 12 ， 5 ， 10 ， 16 ， 88
第三趟： 2 ， 5 ， 10 ， 12 ， 16 ， 88
则采用的排序方法可能是
A．起泡排序 B．希尔排序 C．归并排序 D．基数排序
点评： 此题考察对各种排序方法的步骤、特点的理解及应用。起泡排序第 i 趟结束后可以把第 i 大的数放到正确位置。希尔排序第i趟结束后把相距为某一值的同一组中元素排好序。归并排序第i趟结束后可以得到长度为2i的有序子序列。 基数排序第i趟按第i位分配收集。 故答案为A。
二、综合应用题
综合应用题主要考察综合运用基本知识分析问题、解决问题的能力。41-42为数据结构部分的题。 出题风格仍然沿用第一次的出题风格，一道问答题、一道算法设计题。
41．（10 分）将关键字序列（ 7 、8 、30 、11 、18 、9 、14 ）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组，散列函数： H(key)=(key×3) MOD T，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。
问题：(1)请画出所构造的散列表；
&&&&& (2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。
点评： 此题考察对 散列表相关知识的理解及应用，要求能够构造散列表，并且能够计算等概率情况下查找成功和查找不成功的平均查找长度。
(1)本题中涉及到装填（载）因子α，在散列函数中还有一个未知数T（可认为是散列表的长度）。因此需先求出 T 。α =数据个数/表长， 由装载因子0.7，数据总数7个可知存储空间长度为10即T =10。所以，散列函数为 H(key)=(key×3) MOD 10，线性探测再散列函数为：
Hi=( H(key)+d i ) MOD 10 ， (d i =1,2,3, … ,9)
因此，各数据的地址为：
H(7)= （7*3）MOD10=1&&& &H(8)= （8*3）MOD10=4&& &&H(30)= （30*3）MOD10=0
H(11)= （11*3）MOD10=3 & H(18)= （18*3）MOD10=4& &H1=(H(18)+1)MOD10=5
H(9)= （9*3）MOD10=7&&& &H(14)= （14*3）MOD10=2
构造的散列表为：　
&740)this.width=740">
平均查找长度可用下列公式计算：
740)this.width=740">
其中， ci为查找第i个元素所需的比较次数，即装入第i个元素时所需的比较次数。
处理冲突用线性探测再散列法，得到其哈希表及 各关键字的比较次数 如下图所示
740)this.width=740">
按照上述公式，在等概率情况下，查找成功时的平均查找长度为：
查找成功的 ASL=（1+1+1+1+2+1+1）/7=8/7
在等概率情况下，查找不成功时的平均查找长度是指在表中查找不到待查记录，但找到插入位置的平均探测次数，它是表中所有可能散列的位置上要插入新记录时为找到空位置的探测次数的平均值。在等概率情况下，手工计算查找不成功时的平均查找长度可用下列公式计算：
740)this.width=740">
其中， ci为哈希函数取值为i时查找不成功的比较次数。
查找不成功的情况：（1）遇到空单元（2）按处理冲突的方法完全探测一遍后仍未找到。0到r-1相当于r个不成功查找的入口，从每个入口进入后，直到确定查找不成功为止，其关键字比较次数就是与该入口对应的不成功查找长度。
在本题中，在线性探测再散列法处理冲突得到的哈希表中查找，假设待查的关键字k不在该表中，若H(k=0，将HT[0]中的关键字和k比较后发现HT[0]为空，即查找不成功，比较次数为1；若H(k)=1，则必须将HT[0..5]中的关键字和k比较后，再与HT[6]中的关键字比较时发现HT[6]为空，查找失败，比较次数为7，同理，位置 2，3，…，5，6 的比较次数分别为 6，5，…，2，1次，位置7，8，9的比较次数分别为2，1，1，因此，在等概率情况下， 查找不成功时的平均查找长度为
& 查找不成功的 ASL=（7+6+5+4+3+2+1+2+1+1）/10=3.2
42．（13 分）设将n（n&1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p（0&p&n）个位置，即将R中的数据由 x0,x1,…,xn-1）变换为 (xp,xp+1,…,xn-1,x0,x1,…,xp-1) 。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。
(3)说明设计算法的时间复杂度和空间复杂度。
点评： 此题是一道算法设计题，算法设计是数据结构课程的一个重点内容，也是一个难点。此题考察对顺序表的基本运算的理解及灵活运用、时间复杂度和空间复杂度的概念及应用。 要求时间和空间两方面都尽量最优的情况下，实现数组的循环左移，还要求算法的时间、空间的复杂度。具体要求给出算法思想，并且能用 C、C++、Java描述 该算法。思想可以描述为：建立一个可以存放P个整数的辅助队列，将数组R中的前p个整数依次进队；将R中后面的n-p个整数依次前移p个位置，然后将辅助队列中的p个数依次出队，依次放入数组末尾即第n-p开始的位置即可。
算法描述：
void shift(int *pr,int n,int p) //pr 是指向数组 R 的指针， n 为存放的整数个数，
//p 为循环左移的个数
{ int temp[p];// 辅助数组，存放要移出的整数
&&int i=0;
& while (i&p)// 将 R 中前 p 个数据存入辅助数组中
& { temp[i]=pr[i]; i++;}
&&& while(i&n-p) // 将 R 中从第 p 个整数开始的整数前移 p 个位置
&& { pr[i]=pr[i+p]; i++;}
&& while (i&p)// 将辅助数组中的 p 个数据放到 R 中第 n-p 个数据的后面
&& { pr[n-p+i]=temp[i]; i++;}
算法分析：循环需进行n次，故时间复杂度O(n)，需要p个空间存放进队数据，故空间复杂度O(p)。
上一篇资源：
下一篇资源：在查找表中插入一个数据元素;数据元素
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
在查找表中插入一个数据元素;
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口提醒：此博客暂时不再更新。
个人Wiki :
个人主页 :
建议先看看前言：
推荐在看算法导论的这一章之前先看看严蔚敏老师在《数据结构》上的二叉查找树。
整体来说二叉查找树不难，就是插入和删除节点时让人纠结，我就是在删除节点时各种纠结了。
二叉树执行基本操作的时间与树的高度成正比。
首先说下二叉查找树的性质：
设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点，则key[y]&=key[x];如果y是x的右子树的一个结点，则key[y]&=key[x]。
注意这个性质，和堆对比下，还是有区别的，并且这个性质表示二叉查找树的根节点的左子树中所有结点都小于根结点，所有右子树的结点都大于根结点。所以根据这个性质，可以用中序访问二叉查找数来实现从小大到排列。
首先看看这个二叉查找树(P151图12-1(a))：
按中序遍历结果为：
2-&3-&5-&5-&7-&8
接下来说说二叉查找树的几个操作：
SEARCH:查找关键字等于key的结点
MINIMUM:找出关键字最小的结点
MAXIMUM:找出关键字最大的结点
SUCCESSOR:找出结点x的后继y
INSERT:在二叉查找树中插入结点z
DELETE:在二叉查找树中删除结点z
里面就INSERT和DELETE麻烦一些。
首先逐步分析代码：
①.BST的数据结构：
typedef struct Node{
Node *lchild, *rchild, *
}Node, *BST
②.BST的中序遍历：
根据BST的性质，对于一个根结点x，所以比x小的结点都在x的左子树中，所有比x大的结点都在x的右子树中，并且没一个结点都满足这个性质，所以可以利用中序遍历，按从小到大的顺序输出这个BST。
代码如下：
// 递归版本
Node * BSTreeSearch(BSTree T, int k)
if(T == NULL || k == T->key)
return BSTreeSearch(T->lchild, k);
return BSTreeSearch(T->rchild, k);
// 非递归版本
BSNode * IterativeBSTreeSearch(BSTree T, int k)
while(T != NULL && k != T->key)
if(k lchild->key);
③.BST的最大值与最小值：
依然是利用BST的左子树结点，根结点，右子树结点的大小关系，不解释。。。
代码如下：
Node * BSTreeMinimum(BSTree T)
while(T->lchild != NULL)
Node * BSTreeMaximum(BSTree T)
while(T->rchild != NULL)
下面开始有些麻烦了。
④.BST的后继：
这是其伪代码：
TREE-SUCCESSOR(x)
if right[x] ≠ NIL
then return TREE-MINIMUM (right[x])
while y ≠ NIL and x = right[y]
根据其后继的特性，结点x的后继是具有大于key[x]中的关键字最小者的那个结点。
第1~2行，x的右子树的结点都是大于key[x]的结点，所以如果x有右子树，则在右子树中寻找最小值
第3~6行，如果没有右子树，则其后继y,是x的父亲结点的第一个右子树(考虑为什么呢？根据特性：结点x的后继是具有大于key[x]中的关键字最小者的那个结点。因为x没有右子树，所以这时，按中序遍历的x下一个结点即后继，应该是这样一个子树的根结点y，x的祖先是其左孩子，这样，y就大于其左子树所有结点，并且因为x是y的左子树中最大的结点了)。这个说着肯定是云里雾里，还是看图分析最好了，依然利用上面的图1：
叶子结点5的后继是根结点5.
具体代码如下：
Node *BSTreeSuccessor(Node *x)
if(x->rchild != NULL)
return BSTreeMinimum(x->rchild);
Node *y = x->
while(y != NULL && x == y->rchild)
⑤.BST的插入：
比如要把结点z插入二叉查找数T中，分以下几步：
1.将key[z]从根结点x开始比较，并用y记录x的父亲结点，直到到达最后一层某一叶节点比较完,此时y指向某一叶节点,x是NULL。
2.如果此时y是NULL，则证明是空树，于是根结点就是z
3.否则如果key[z]小于key[y]，则让left[y] = z；当key[z]大于或等于key[y]，则让right[y] = z。
插入就是那么简单。
看看伪代码，就是按这个步骤来的：
TREE-INSERT(T, z)
x ← root[T]
while x ≠ NIL
if key[z] < key[x]
then x ← left[x]
else x ← right[x]
if y = NIL
then root[T] ← z
// Tree T was empty
else if key[z] < key[y]
then left[y] ← z
else right[y] ← z
具体的代码如下：
void BSTreeInsert(BSTree &#038;T, int k)
Node *y = NULL;
Node *x = T;
Node *z = new N
z->lchild = z->parent = z->rchild = NULL;//////////
while(x != NULL)
z->parent =
if(y == NULL)
y->lchild =
y->rchild =
⑥.BST的删除：
比如要把二叉查找数T中的z结点删除掉，这是要分三种情况：
1.z没有左子树和右子树：
汗，这个就是直接删除z，把z的父亲结点parent[z]指向z的子树设置为NULL。
如图，直接删除z，并让结点12的右子树为NULL。
2.z只有左子树或者只有右子树：
这个是让z的子树与其父亲结点相连，删除z即可。
如图，此时直接删除z，并让z的子树20的父亲结点变成z的父亲结点15。
3.z既有左子树又有右子树：
这是先用SUCCESSOR找到z的后继y，因为y一定没有左子树(考虑为什么？下面解释)，所以可以删除y，并让y的父亲结点成为y的右子树的父亲结点(类似第2中情况)，并用y的key代替z的key。
如图,y的右子树7成为10的子树，并且y取代了z的未知。
这是我们来考虑一个关键问题，y为何一定没有左子树？(习题12.2-5)
答：因为y是z的后继，所以y是z的右子树中最小的一个结点，如果y还有左子树，则y的左子树中的结点一定比y小！
具体代码如下：
Node* BSTreeDelete(BSTree T, Node *z)
Node *x, *y;
// z是要删除的节点,而y是要替换z的节点
if(z->lchild == NULL || z->rchild == NULL)
// 当要删除的z至多有一个子树，则y=z；
y = BSTreeSuccessor(z);
// y是z的后继
if(y->lchild != NULL)
if(x != NULL)
x->parent = y->
//如果y至多只有一个子树，则使y的子树成为y的父亲节点的子树
if(y->parent == NULL)
// 如果y没有父亲节点，则表示y是根节点，词典其子树x为根节点
else if(y == y->parent->lchild)
// 如果y是其父亲节点的左子树，则y的子树x成为其父亲节点的左子树，
// 否则成为右子树
y->parent->lchild =
y->parent->rchild =
if(y != z)
z->key = y->
下面是整个二叉查找树的实现：
* Author: Tanky Woo
* Description: 《算法导论》第12章 BST
#define NULL 0
typedef struct Node{
Node *lchild, *rchild, *
}Node, *BST
Node * BSTreeSearch(BSTree T, int k)
if(T == NULL || k == T->key)
return BSTreeSearch(T->lchild, k);
return BSTreeSearch(T->rchild, k);
// 号改正，之前把T写成x了，感谢manfeyn提醒
Node * IterativeBSTreeSearch(BSTree T, int k)
while(T != NULL &#038;&#038; k != T->key)
if(k lchild->key)
Node * BSTreeMinimum(BSTree T)
while(T->lchild != NULL)
Node * BSTreeMaximum(BSTree T)
while(T->rchild != NULL)
Node *BSTreeSuccessor(Node *x)
if(x->rchild != NULL)
return BSTreeMinimum(x->rchild);
Node *y = x->
while(y != NULL &#038;&#038; x == y->rchild)
void BSTreeInsert(BSTree &#038;T, int k)
Node *y = NULL;
Node *x = T;
Node *z = new N
z->lchild = z->parent = z->rchild = NULL;
while(x != NULL)
z->parent =
if(y == NULL)
y->lchild =
y->rchild =
Node* BSTreeDelete(BSTree T, Node *z)
Node *x, *y;
// z是要删除的节点,而y是要替换z的节点
if(z->lchild == NULL || z->rchild == NULL)
// 当要删除的z至多有一个子树，则y=z；
y = BSTreeSuccessor(z);
// y是z的后继
if(y->lchild != NULL)
if(x != NULL)
x->parent = y->
//如果y至多只有一个子树，则使y的子树成为y的父亲节点的子树
if(y->parent == NULL)
// 如果y没有父亲节点，则表示y是根节点，词典其子树x为根节点
else if(y == y->parent->lchild)
// 如果y是其父亲节点的左子树，则y的子树x成为其父亲节点的左子树，
// 否则成为右子树
y->parent->lchild =
y->parent->rchild =
if(y != z)
z->key = y->
void InBSTree(BSTree T)
if(T != NULL)
InBSTree(T->lchild);
cout <key <rchild);
int main()
BSTree T = NULL;
for(int i=0; i>
BSTreeInsert(T, m);
cout << "二叉查找树中序查找：";
InBSTree(T);
cout << "删除根节点后：";
BSTreeDelete(T, T);
InBSTree(T);
结果如图：
OK,BST分析完了，这一章一定要搞懂，否则下一章的Red-Black-Tree就会一抹黑了~~~
Tanky Woo 标签: ，，
Tanky Woo @
私はオフトピック場合は、これを知っているが、私は自分の始めに探していますブログと不思議したすべてがに必要とされるものセットアップを設定取得するには？私はあなたのようなブログはかなりの費用がかかるだろう持つと仮定している？私は今ではない、非常にインターネット精通ので、私は100％ではないんだ一定。どれ提案やアドバイスをいただければ幸いです。 ありがとうございます
Tanky Woo. 目前就职于北京
关注于Python开发, Linux运维等方面
这个博客暂时废弃了
技术方面我分别记录在技术博客
和 个人维基
Hosting by://AVL树节点信息template&class&T&class&TreeNode{&&&&public:&&&&&&&&TreeNode():lson(NULL),rson(NULL),freq(1),hgt(0){}&&&&&&&&T&//值&&&&&&&&int&//以此节点为根的树的高度&&&&&&&&unsigned&int&//频率&&&&&&&&TreeNode*&//指向左儿子的地址&&&&&&&&TreeNode*&//指向右儿子的地址};第二步：平衡二叉树类的声明　　声明中的旋转函数将在后边的步骤中详解。代码如下：//AVL树类的属性和方法声明template&class&T&class&AVLTree{&&&&private:&&&&&&&&TreeNode&T&*&//根节点&&&&&&&&void&insertpri(TreeNode&T&*&&node,T&x);//插入&&&&&&&&TreeNode&T&*&findpri(TreeNode&T&*&node,T&x);//查找&&&&&&&&void&insubtree(TreeNode&T&*&node);//中序遍历&&&&&&&&void&Deletepri(TreeNode&T&*&&node,T&x);//删除&&&&&&&&int&height(TreeNode&T&*&node);//求树的高度&&&&&&&&void&SingRotateLeft(TreeNode&T&*&&k2);//左左情况下的旋转&&&&&&&&void&SingRotateRight(TreeNode&T&*&&k2);//右右情况下的旋转&&&&&&&&void&DoubleRotateLR(TreeNode&T&*&&k3);//左右情况下的旋转&&&&&&&&void&DoubleRotateRL(TreeNode&T&*&&k3);//右左情况下的旋转&&&&&&&&int&Max(int&cmpa,int&cmpb);//求最大值&&&&public:&&&&&&&&AVLTree():root(NULL){}&&&&&&&&void&insert(T&x);//插入接口&&&&&&&&TreeNode&T&*&find(T&x);//查找接口&&&&&&&&void&Delete(T&x);//删除接口&&&&&&&&void&traversal();//遍历接口};第三步：两个辅助方法　　旋转算法需要借助于两个功能的辅助，一个是求树的高度，一个是求两个高度的最大值。这里规定，一棵空树的高度为-1，只有一个根节点的树的高度为0，以后每多一层高度加1。为了解决指针NULL这种情况，写了一个求高度的函数，这个函数还是很有必要的。代码如下：//计算以节点为根的树的高度template&class&T&int&AVLTree&T&::height(TreeNode&T&*&node){&&&&if(node!=NULL)&&&&&&&&return&node-&&&&&return&-1;}//求最大值template&class&T&int&AVLTree&T&::Max(int&cmpa,int&cmpb){&&&&return&cmpa&cmpb?cmpa:}第四步：旋转　　对于一个平衡的节点，由于任意节点最多有两个儿子，因此高度不平衡时，此节点的两颗子树的高度差2.容易看出，这种不平衡出现在下面四种情况：　　1、6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左。　　2、6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右。　　3、2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左。　　4、2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种情况成为右右。　　从图2中可以可以看出，1和4两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，我们称之为单旋转。2和3两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，我们称之为双旋转。第五步：单旋转　　单旋转是针对于左左和右右这两种情况的解决方案，这两种情况是对称的，只要解决了左左这种情况，右右就很好办了。图3是左左情况的解决方案，节点k2不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的左子树X子树，所以属于左左情况。　　为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。　　这样的操作只需要一部分指针改变，结果我们得到另外一颗二叉查找树，它是一棵AVL树，因为X向上一移动了一层，Y还停留在原来的层面上，Z向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同，插入操作使得X高度长高了。因此，由于这颗子树高度没有变化，所以通往根节点的路径就不需要继续旋转了。代码如下：//左左情况下的旋转template&class&T&void&AVLTree&T&::SingRotateLeft(TreeNode&T&*&&k2){&&&&TreeNode&T&*&k1;&&&&k1=k2-&&&&&k2-&lson=k1-&&&&&k1-&rson=k2;&&&&k2-&hgt=Max(height(k2-&lson),height(k2-&rson))+1;&&&&k1-&hgt=Max(height(k1-&lson),k2-&hgt)+1;}//右右情况下的旋转template&class&T&void&AVLTree&T&::SingRotateRight(TreeNode&T&*&&k2){&&&&TreeNode&T&*&k1;&&&&k1=k2-&&&&&k2-&rson=k1-&&&&&k1-&lson=k2;&&&&k2-&hgt=Max(height(k2-&lson),height(k2-&rson))+1;&&&&k1-&hgt=Max(height(k1-&rson),k2-&hgt)+1;}第六步：双旋转　　对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。双旋转是针对于这两种情况的解决方案，同样的，这样两种情况也是对称的，只要解决了左右这种情况，右左就很好办了。图4是左右情况的解决方案，节点k3不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的右子树k2子树，所以属于左右情况。&　　为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次右右旋转，旋转之后就变成了左左情况，所以第二步再进行一次左左旋转，最后得到了一棵以k2为根的平衡二叉树树。代码如下：//左右情况的旋转template&class&T&void&AVLTree&T&::DoubleRotateLR(TreeNode&T&*&&k3){&&&&SingRotateRight(k3-&lson);&&&&SingRotateLeft(k3);}//右左情况的旋转template&class&T&void&AVLTree&T&::DoubleRotateRL(TreeNode&T&*&&k3){&&&&SingRotateLeft(k3-&rson);&&&&SingRotateRight(k3);}&第七步：插入　　插入的方法和二叉查找树基本一样，区别是，插入完成后需要从插入的节点开始维护一个到根节点的路径，每经过一个节点都要维持树的平衡。维持树的平衡要根据高度差的特点选择不同的旋转算法。代码如下：//插入template&class&T&void&AVLTree&T&::insertpri(TreeNode&T&*&&node,T&x){&&&&if(node==NULL)//如果节点为空,就在此节点处加入x信息&&&&{&&&&&&&&node=new&TreeNode&T&();&&&&&&&&node-&data=x;&&&&&&&&return;&&&&}&&&&if(node-&data&x)//如果x小于节点的值,就继续在节点的左子树中插入x&&&&{&&&&&&&&insertpri(node-&lson,x);&&&&&&&&if(2==height(node-&lson)-height(node-&rson))&&&&&&&&&&&&if(x&node-&lson-&data)&&&&&&&&&&&&&&&&SingRotateLeft(node);&&&&&&&&&&&&else&&&&&&&&&&&&&&&&DoubleRotateLR(node);&&&&}&&&&else&if(node-&data&x)//如果x大于节点的值,就继续在节点的右子树中插入x&&&&{&&&&&&&&insertpri(node-&rson,x);&&&&&&&&if(2==height(node-&rson)-height(node-&lson))//如果高度之差为2的话就失去了平衡,需要旋转&&&&&&&&&&&&if(x&node-&rson-&data)&&&&&&&&&&&&&&&&SingRotateRight(node);&&&&&&&&&&&&else&&&&&&&&&&&&&&&&DoubleRotateRL(node);&&&&}&&&&else&++(node-&freq);//如果相等,就把频率加1&&&&node-&hgt=Max(height(node-&lson),height(node-&rson));}//插入接口template&class&T&void&AVLTree&T&::insert(T&x){&&&&insertpri(root,x);}第八步：查找和二叉查找树相比，查找方法没有变法，不过根据存储的特性，AVL树能维持在一个O(logN)的稳定的时间，而二叉查找树则相当不稳定。代码如下：//查找template&class&T&TreeNode&T&*&AVLTree&T&::findpri(TreeNode&T&*&node,T&x){&&&&if(node==NULL)//如果节点为空说明没找到,返回NULL&&&&{&&&&&&&&return&NULL;&&&&}&&&&if(node-&data&x)//如果x小于节点的值,就继续在节点的左子树中查找x&&&&{&&&&&&&&return&findpri(node-&lson,x);&&&&}&&&&else&if(node-&data&x)//如果x大于节点的值,就继续在节点的左子树中查找x&&&&{&&&&&&&&return&findpri(node-&rson,x);&&&&}&&&&else&return&//如果相等,就找到了此节点}//查找接口template&class&T&TreeNode&T&*&AVLTree&T&::find(T&x){&&&&return&findpri(root,x);}第九步：删除　　删除的方法也和二叉查找树的一致，区别是，删除完成后，需要从删除节点的父亲开始向上维护树的平衡一直到根节点。代码如下：//删除template&class&T&void&AVLTree&T&::Deletepri(TreeNode&T&*&&node,T&x){&&&&if(node==NULL)&return&;//没有找到值是x的节点&&&&if(x&&&node-&data)&&&&{&&&&&&&&&Deletepri(node-&lson,x);//如果x小于节点的值,就继续在节点的左子树中删除x&&&&&&&&&if(2==height(node-&rson)-height(node-&lson))&&&&&&&&&&&&if(node-&rson-&lson!=NULL&&(height(node-&rson-&lson)&height(node-&rson-&rson))&)&&&&&&&&&&&&&&&&DoubleRotateRL(node);&&&&&&&&&&&&else&&&&&&&&&&&&&&&&SingRotateRight(node);&&&&}&&&&else&if(x&&&node-&data)&&&&{&&&&&&&&&Deletepri(node-&rson,x);//如果x大于节点的值,就继续在节点的右子树中删除x&&&&&&&&&if(2==height(node-&lson)-height(node-&rson))&&&&&&&&&&&&if(node-&lson-&rson!=NULL&&&(height(node-&lson-&rson)&height(node-&lson-&lson)&))&&&&&&&&&&&&&&&&DoubleRotateLR(node);&&&&&&&&&&&&else&&&&&&&&&&&&&&&&SingRotateLeft(node);&&&&}&&&&else//如果相等,此节点就是要删除的节点&&&&{&&&&&&&&if(node-&lson&&node-&rson)//此节点有两个儿子&&&&&&&&{&&&&&&&&&&&&TreeNode&T&*&temp=node-&//temp指向节点的右儿子&&&&&&&&&&&&while(temp-&lson!=NULL)&temp=temp-&//找到右子树中值最小的节点&&&&&&&&&&&&//把右子树中最小节点的值赋值给本节点&&&&&&&&&&&&node-&data=temp-&&&&&&&&&&&&&node-&freq=temp-&&&&&&&&&&&&&Deletepri(node-&rson,temp-&data);//删除右子树中最小值的节点&&&&&&&&&&&&if(2==height(node-&lson)-height(node-&rson))&&&&&&&&&&&&{&&&&&&&&&&&&&&&&if(node-&lson-&rson!=NULL&&&(height(node-&lson-&rson)&height(node-&lson-&lson)&))&&&&&&&&&&&&&&&&&&&&DoubleRotateLR(node);&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&&&&&SingRotateLeft(node);&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&else//此节点有1个或0个儿子&&&&&&&&{&&&&&&&&&&&&TreeNode&T&*&temp=&&&&&&&&&&&&if(node-&lson==NULL)//有右儿子或者没有儿子&&&&&&&&&&&&node=node-&&&&&&&&&&&&&else&if(node-&rson==NULL)//有左儿子&&&&&&&&&&&&node=node-&&&&&&&&&&&&&delete(temp);&&&&&&&&&&&&temp=NULL;&&&&&&&&}&&&&}&&&&if(node==NULL)&return;&&&&node-&hgt=Max(height(node-&lson),height(node-&rson))+1;&&&&return;}//删除接口template&class&T&void&AVLTree&T&::Delete(T&x){&&&&Deletepri(root,x);}第十步：中序遍历代码如下：//中序遍历函数template&class&T&void&AVLTree&T&::insubtree(TreeNode&T&*&node){&&&&if(node==NULL)&return;&&&&insubtree(node-&lson);//先遍历左子树&&&&cout&&node-&data&&"&";//输出根节点&&&&insubtree(node-&rson);//再遍历右子树}//中序遍历接口template&class&T&void&AVLTree&T&::traversal(){&&&&insubtree(root);}第十一步：关于效率　　此数据结构插入、查找和删除的时间复杂度均为O(logN)，但是插入和删除需要额外的旋转算法需要的时间，有时旋转过多也会影响效率。　　关于递归和非递归。我用的是递归的方法进行插入，查找和删除，而非递归的方法一般来说要比递归的方法快很多，但是我感觉非递归的方法写出来会比较困难，所以我还是选择了递归的方法。　　还有一种效率的问题是关于高度信息的存储，由于我们需要的仅仅是高度的差，不需要知道这棵树的高度，所以只需要使用两个二进制位就可以表示这个差。这样可以避免平衡因子的重复计算，可以稍微的加快一些速度，不过代码也丧失了相对简明性和清晰度。如果采用递归写法的话，这种微加速就更显得微乎其微了。&　　如果有哪些不对的或者不清晰的地方请指出，我会修改并加以完善。&　　附：&
插入函数：
node-&hgt=Max(height(node-&lson),height(node-&rson));
是否也需要 + 1
-_- 楼主文章写的不错。
另外SingRotateLeft()函数，最后是否需要k2 = k1;
-_- 期待作者的回复
zhuyf87 [at]
第六步
... 因为它的左子树k1比右子树Z深2层 ...
小笔误：右子树Z -& 右子树D
if(node-&lson==NULL)//有右儿子或者没有儿子
node=node-&
else if(node-&rson==NULL)//有左儿子
node=node-&此处应该是 temp = node-&
temp =node-&
不好意思是我分析错了
删除的时候维护平衡时，if(x & node-&data)
Deletepri(node-&lson,x);//如果x小于节点的值,就继续在节点的左子树中删除x
if(2==height(node-&rson)-height(node-&lson))
if(node-&rson-&lson!=NULL&&(height(node-&rson-&lson)&height(node-&rson-&rson)) )
DoubleRotateRL(node);
SingRotateRight(node);
}height(node-&rons-&lson)的高度不是等于0吗，求解释
删除那里，前面已经if(node==NULL)后面又有一个，这是LZ失误还是我没理解到
左旋和右旋之后更新树的高度，为什么只更新K1，K2的就可以，它们的子节点都不需要更新么，这样保存下来的树的高度是不是已经出错了？
@byd代码是错的，鉴定过。不能跑。我也纳闷，书上写的也是跟楼主一样。我自己用C语言写了一个，还没楼主这个错得这么离谱。
首先对LZ表示感谢，不过代码确实有问题，旋转之后没做处理，反正是衔接不上root,而且root没法改变，这样导致断层，根本构成不了一颗树，希望LZ尽快改好吧。
博主的但旋转代码是否有问题， 个人觉得是差了一个重要的东西：就是将转好了的k1 赋值给k 2，即 k2 = k1;
代码有问题，RL和LR两个函数有BUG楼主都没有调试就把代码发出来，真是误人子弟
评论里竟然都是找错的。文章就不看了哈
@Niteip当前节点0个儿子，删除后为NULL，直接退出，不用求hgt
ACM小菜奋斗史
欢迎交友！
留言簿(18)
随笔分类(144)
随笔档案(146)
各大OJ入口
南阳理工学院ACM大牛，目前在百度工作
积分与排名
阅读排行榜
评论排行榜