第7章 集合与搜索
7-1 设A = { 1,2,3 },B = { 3,4,5 }，求下列结果：
(1) A + B (2) A * B (3) A - B
(4) A.Contains (1) (5) A.AddMember (1) (6) A.DelMember (1) (7) A.Min ( )
【解答】
(1) 集合的并A + B = { 1,2,3,4,5 }
(2) 集合的交A * B = { 3 }
(3) 集合的差A - B = { 1,2 }
(4) 包含A.Contains (1) = 1，表示运算结果为"True"
(5) 增加A.AddMember (1)，集合中仍为{ 1,2,3 }，因为增加的是重复元素，所以不加入
(6) 删除A.DelMember (1)，集合中为{ 2,3 }
(7) 求最小元素A.Min ( )，结果为1
7-2 试编写一个算法，打印一个有穷集合中的所有成员。要求使用集合抽象数据类型中的基本操作。如果集合中包含有子集合，各个子集合之间没有重复的元素，采用什么结构比较合适。
【解答】
集合抽象数据类型的部分内容
template <class Type> class Set {
//对象,零个或多个成员的聚集。其中所有成员的类型是一致的,但没有一个成员是相同的。
int Contains ( const Type x ); //判元素x是否集合this的成员
int SubSet ( Set <Type>& right ); //判集合this是否集合right的子集
int operator == ( Set <Type>& right ); //判集合this与集合right是否相等
int Elemtype ( ); //返回集合元素的类型
Type GetData ( ); //返回集合原子元素的值
char GetName ( ); //返回集合this的集合名
Set <Type>* GetSubSet ( ); //返回集合this的子集合地址
Set <Type>* GetNext ( ); //返回集合this的直接后继集合元素
int IsEmpty ( ); //判断集合this是否空。空则返回1,否则返回0
};
ostream& operator << ( ostream& out,Set <Type> t ) {
//友元函数,将集合t输出到输出流对象out。
t.traverse ( out,t ); return out;
}
void traverse ( ostream& out,Set <Type> s ) {
//友元函数,集合的遍历算法
if ( s.IsEmpty ( ) == 0 ) { //集合元素不空
if ( s.Elemtype ( ) == 0 ) out << s.GetName ( ) << ‘{’; //输出集合名及花括号
else if ( s.Elemtype ( ) == 1 ) { //集合原子元素
out << s.GetData ( ); //输出原子元素的值
if ( s.GetNext ( ) != NULL ) out << ‘,’;
}
else { //子集合
traverse ( s,GetSubSet ( ) ); //输出子集合
if ( s.GetNext ( ) != NULL ) out << ‘,’;
}
traverse ( s.GetNext ( ) ); //向同一集合下一元素搜索
}
else out << ‘}’;
}
如果集合中包含有子集合，各个子集合之间没有重复的元素，采用广义表结构比较合适。也可以使用并查集结构。
7-3 当全集合可以映射成1到N之间的整数时，可以用位数组来表示它的任一子集合。当全集合是下列集合时，应当建立什么样的映射？用映射对照表表示。
整数0,1,…,99
(2) 从n到m的所有整数，n ( m
(3) 整数n,n+2,n+4,…,n+2k
(4) 字母 ‘a’,‘b’,‘c’,…,‘z’
(5) 两个字母组成的字符串,其中,每个字母取自 ‘a’,‘b’,‘c’,…,‘z’。
【解答】
(1) i → i的映射关系，i = 0,1,2,…,99
(2) i → n-i 的映射关系，i = n,n+1,n+2,…,m
0
1
2
m-n
n
n+1
n+2
…
m
(3) i → (i-n)/2 的映射关系，i = n,n+2,n+4,…,n+2k
0
1
2
k
n
n+2
n+4
…
n+2k
(4) ord (c) → ord (c) - ord ('a') 的映射关系，c = 'a','b','c',…,'z'
0
1
2
25
'a'
'b'
'c'
…
'z'
(5) (ord (c1) - ord ('a') )*26 + ord (c2) - ord ('a')的映射关系，c1 = c2 = 'a','b','c',…,'z'
0
1
2
675
'aa'
'ab'
'ba'
…
'zz'
7-4 试证明：集合A是集合B的子集的充分必要条件是集合A和集合B的交集是A。
【证明】
必要条件：因为集合A是集合B的子集，有A ( B，此时，对于任一x ( A，必有x ( B，因此可以推得x ( A∩B，就是说，如果A是B的子集，一定有A∩B = A。
充分条件：如果集合A和集合B的交集A∩B是A，则对于任一x ( A，一定有x ( A∩B，因此可以推得x ( B，由此可得A ( B，即集合A 是集合B的子集。
7-5 试证明：集合A是集合B的子集的充分必要条件是集合A和集合B的并集是B。
【证明】
必要条件：因为集合A是集合B的子集，有A ( B，此时，对于任一x ( A，必有x ( B,它一定在A∪B中。另一方面，对于那些x' ( A,但x' ( B的元素，它也必在A∪B中，因此可以得出结论：凡是属于集合B的元素一定在A∪B中，A∪B = B。
充分条件：如果存在元素x ( A且x ( B，有x ( A∪B，但这不符合集合A和集合B的并集A∪B是B的要求。集合的并A∪B是集合B的要求表明，对于任一x ( A∪B，同时应有x ( B。对于那些满足x' ( A的x'，既然x' ( A∪B，也应当x' ( B，因此，在此种情况下集合A应是集合B的子集。
7-6 设+、*、-是集合的或、与、差运算，试举一个例子，验证
A + B = (A - B) + (B - A) + A * B
【解答】
若设集合A = { 1,3,4,7,9,15 }，集合B = { 2,3,5,6,7,12,15,17 }。则
A + B = { 1,2,3,4,5,6,7,9,12,15,17 }
又A * B = { 3,7,15 },A – B = { 1,4,9 },B – A = { 2,5,6,12,17 }
则 (A – B) + (B – A) + A * B = { 1,2,3,4,5,6,7,9,12,15,17 }
有 A + B = (A – B) + ( B – A ) + A * B。
7-7 给定一个用无序链表表示的集合，需要在其上执行operator+( ),operator*( ),operator- ( ),Contains(x),AddMember (x),DelMember(x),Min( )，试写出它的类声明，并给出所有这些成员函数的实现。
【解答】
下面给出用无序链表表示集合时的类的声明。
template <class Type> class Set; //用以表示集合的无序链表的类的前视定义
template <class Type> class SetNode { //集合的结点类定义
friend class SetList<Type>;
private:
Type data; //每个成员的数据
SetNode <Type> *link; //链接指针
public:
SetNode (const Type& item ),data (item),link (NULL); //构造函数
};
template <class Type> class Set { //集合的类定义
private:
SetNode <Type> *first,*last; //无序链表的表头指针,表尾指针
public:
SetList ( ) { first = last = new SetNode <Type>(0); } //构造函数
~SetList ( ) { MakeEmpty ( ); delete first; } //析构函数
void MakeEmpty ( ); //置空集合
int AddMember ( const Type& x ); //把新元素x加入到集合之中
int DelMember ( const Type& x ); //把集合中成员x删去
Set <Type>& operator = ( Set <Type>& right ); //复制集合right到this。
Set <Type>& operator + ( Set <Type>& right ); //求集合this与集合right的并
Set <Type>& operator * ( Set <Type>& right ); //求集合this与集合right的交
Set <Type>& operator - ( Set <Type>& right ); //求集合this与集合right的差
int Contains ( const Type& x ); //判x是否集合的成员
int operator == ( Set <Type>& right ); //判集合this与集合right相等
Type& Min ( ); //返回集合中的最小元素的值
}
operator + ( )
template <class Type> Set <Type>& Set <Type>,,operator + ( Set <Type>& right ) {
//求集合this与集合right的并,计算结果通过临时集合temp返回，this集合与right集合不变。
SetNode <Type> *pb = right.first->link; //right集合的链扫描指针
SetNode <Type> *pa,*pc; //this集合的链扫描指针和结果链的存放指针
Set <Type> temp;
pa = first->link; pc = temp.first;
while ( pa != NULL ) { //首先把集合this的所有元素复制到结果链
pc->link = new SetNode<Type> ( pa->data ) ;
pa = pa->link; pc = pc->link;
}
while ( pb != NULL ) { //将集合right中元素一个个拿出到this中查重
pa = first->link;
while ( pa != NULL && pa->data != pb->data ) pa = pa->link;
if ( pa == NULL ) //在集合this中未出现,链入到结果链
{ pc->link = new SetNode<Type> ( pa->data ); pc = pc->link; }
pb = pb->link;
}
pc->link = NULL; last = pc; //链表收尾
return temp;
}
(2) operator * ( )
template <class Type> Set <Type>& Set <Type>,,operator * ( Set <Type>& right ) {
//求集合this与集合right的交,计算结果通过临时集合temp返回，this集合与right集合不变。
SetNode<Type> *pb = right.first->link; //right集合的链扫描指针
Set <Type> temp;
SetNode <Type> *pc = temp.first; //结果链的存放指针
while ( pb != NULL ) { //将集合right中元素一个个拿出到this中查重
SetNode<Type> *pa = first->link; //this集合的链扫描指针
while ( pa != NULL ) {
if ( pa->data == pb->data ) //两集合公有的元素,插入到结果链
{ pc->link = new SetNode<Type> ( pa->data ); pc = pc->link; }
pa = pa->link;
}
pb = pb->link;
}
pc->link = NULL; last = pc; //置链尾指针
return temp;
}
(3) operator - ( ),
template <class Type> Set <Type>& Set <Type>,,operator - ( Set <Type>& right ) {
//求集合this与集合right的差,计算结果通过临时集合temp返回，this集合与right集合不变。
SetNode<Type> *pa = first->link; //this集合的链扫描指针
Set <Type> temp;
SetNode<Type> *pc = temp->first; //结果链的存放指针
while ( pa != NULL ) { //将集合this中元素一个个拿出到right中查重
SetNode <Type> *pb = right.first->link; //right集合的链扫描指针
while ( pb != NULL && pa->data != pb->data )
pb = pb->link;
if ( pb == NULL ) //此this中的元素在right中未找到,插入
{ pc->link = new SetNode <Type> ( pa->data ); pc = pc->link; }
pa = pa->link;
}
pc->link = NULL; last = pc; //链表收尾
return temp;
}
(4) Contains(x)
template <class Type> int Set <Type>,,Contains ( const Type& x ) {
//测试函数,如果x是集合的成员,则函数返回1,否则返回0。
SetNode<Type> * temp = first->link; //链的扫描指针
while ( temp != NULL && temp->data != x ) temp = temp->link; //循链搜索
if ( temp != NULL ) return 1; //找到,返回1
else return 0; //未找到,返回0
}
(5) AddMember (x)
template <class Type> int Set <Type>,,AddMember ( const Type& x ) {
//把新元素x加入到集合之中。若集合中已有此元素,则函数返回0,否则函数返回1。
SetNode<Type> * temp = first->link; // temp是扫描指针
while ( temp != NULL && temp->data != x ) temp = temp->link; /循链扫描
if ( temp != NULL ) return 0; //集合中已有此元素,不加
last = last->link = new SetNode (x); //否则,创建数据值为x的新结点,链入
return 1;
}
(6) DelMember (x)
template <class Type> int Set <Type>,,DelMember ( const Type& x ) {
//把集合中成员x删去。若集合不空且元素x在集合中,则函数返回1,否则返回0。
SetNode<Type> * p = first->link,*q = first;
while ( p != NULL ) {
if ( p->data == x ) { //找到
q->link = p->link; //重新链接
if ( p == last ) last = q; //删去链尾结点时改链尾指针
delete p; return 1; //删除含x结点
}
else { q = p; p = p->link; } //循链扫描
return 0; //集合中无此元素
}
(7) Min ( )
template <class Type> SetNode<Type> * Set <Type>,,Min ( ) {
//在集合中寻找值最小的成员并返回它的位置。
SetNode<Type> * p = first->link,*q = first->link; //p是检测指针,q是记忆最小指针
while ( p != NULL ) {
if ( p->data < q->data ) q = p; //找到更小的,让q记忆它
p = p->link; //继续检测
}
return q;
}
7-8 设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908。试画出对其进行折半搜索时的二叉搜索树,并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
【解答】
7-9 若对有n个元素的有序顺序表和无序顺序表进行顺序搜索,试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?
(1) 搜索失败;
(2) 搜索成功,且表中只有一个关键码等于给定值k的对象;
(3) 搜索成功,且表中有若干个关键码等于给定值k的对象,要求一次搜索找出所有对象。
【解答】
(1) 不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。
(2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。
(3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。
前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。
7-10 假定用一个循环链表来实现一个有序表，并让指针head指向具有最小关键码的结点。指针current初始时等于head，每次搜索后指向当前检索的结点，但如果搜索不成功则current重置为head。试编写一个函数search(head,current,key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针0。请说明如何保持指针current以减少搜索时的平均搜索长度。
【解答】
相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据成员。
template<class Type>
ListNode <Type> * Search ( ListNode<Type> * head,ListNode<Type> *& current,Type key ) {
ListNode <Type> * p,* q;
if ( key < current ) { p = head; q = current; } //确定检测范围,用p,q指示
else { p = current; q = head; }
while ( p != q && p->data < key ) p = p->link; //循链搜索其值等于key的结点
if ( p->data == key ) { current = p; return p; } //找到,返回结点地址
else { current = head; return NULL; } //未找到,返回空指针
}
7-11 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针p总是指向最后成功搜索到的结点，搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数search(head,p,key)，检索具有关键码key的结点，并相应地修改p。最后请给出搜索成功和搜索不成功时的平均搜索长度。
【解答】
template <class Type>
DblListNode<Type> * Search ( DblListNode<Type> * head,DblListNode<Type> *& p,Type key ) {
//在以head为表头的双向有序链表中搜索具有值key的结点。算法可视为双向链表类和双向链表结点类的友元
//函数。若给定值key大于结点p中的数据,从p向右正向搜索,否则,从p向左反向搜索。
DblListNode<Type> * q = p;
if ( key < p->data ) { while ( q != NULL && q->data > key ) q = q-> lLink; } //反向搜索
else { while ( q != NULL && q->data < key ) q = q-> rLink; } //正向搜索
if ( q != NULL && q->data == key ) { p = q; return p; } //搜索成功
else return NULL;
}
如果指针p处于第i个结点(i = 1,2,…,n)，它左边有i-1个结点，右边有n-i个结点。找到左边第i-1号结点比较2次，找到第i-2号结点比较3次，…，找到第1号结点比较i次，一般地，找到左边第k个结点比较i-k+1次(k = 1,2,…,i-1)。找到右边第i+1号结点比较2次，找到第i+2号结点比较3次，…，找到第n号结点比较n-i+1次，一般地，找到右边第k个结点比较k-i+1次(k = i+1,i+2,…,n)。因此，当指针处于第i个结点时的搜索成功的平均数据比较次数为
一般地，搜索成功的平均数据比较次数为
如果指针p处于第i个结点(i = 1,2,…,n)，它左边有i个不成功的位置，右边有n-i+1个不成功的位置。
一般地，搜索不成功的平均数据比较次数为
7-12 在一棵表示有序集S的二叉搜索树中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S = S1 ( S2 ( S3。若对于任意的a ( S1,b ( S2,c ( S3,是否总有a ( b ( c？为什么？
【解答】
答案是否定的。举个反例：看下图粗线所示的路径
S1 = { 15 },S2 = { 25,30,35,45 },S3 = { 40,50,65,70 }
c = 40 ( S3，b = 45 ( S2，b ( c 不成立。
7-13 请给出下列操作序列运算的结果：Union(1,2),Union(3,4),Union(3,5),Union(1,7),Union(3,6),Union(8,9),Union(1,8),Union(3,10),Union(3,11),Union(3,12),Union(3,13),Union(14,15),Union(16,17),Union(14,16),Union(1,3),Union(1,14)，要求
(1) 以任意方式执行Union；
(2) 根据树的高度执行Union；
(3) 根据树中结点个数执行Union。
【解答】
(1) 对于union(i,j)，以i作为j的双亲
(2) 按i和j为根的树的高度实现union(i,j)，高度大者为高度小者的双亲；
(3) 按i和j为根的树的结点个数实现union(i,j)，结点个数大者为结点个数小者的双亲。
7-14 有n个结点的二叉搜索树具有多少种不同形态?
【解答】
7-15 设有一个输入数据的序列是 { 46,25,78,62,12,37,70,29 },试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
【解答】
7-16 设有一个标识符序列{else,public,return,template}，p1=0.05,p2=0.2,p3=0.1,p4=0.05,q0=0.2,q1=0.1,q2=0.2,q3=0.05,q4=0.05，计算W[i][j]、C[i][j]和R[i][j]，构造最优二叉搜索树。
【解答】
将标识符序列简化为 { e,p,r,t }，并将各个搜索概率值化整，有
e
p
r
t
p1 = 1
p2 = 4
p3 = 2
p4 = 1
q0 = 4
q1 = 2
q2 = 4
q3 = 1
q4 = 1
(1) 首先构造只有一个内结点的最优二叉搜索树:
三个矩阵的内容如下:
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
4
7
15
18
20
0
0
7
22
32
39
0
0
1
2
2
2
1
2
10
13
15
1
0
10
20
27
1
0
2
2
2
2
4
7
9
2
0
7
12
2
0
3
3
3
1
3
3
0
3
3
0
4
4
1
4
0
4
0
W[i][j] C[i][j] R[i][j]
(2) 构造具有两个内结点的最优二叉搜索树
(3) 构造具有三个内结点的最优二叉搜索树
(4) 构造具有四个内结点的最优二叉搜索树
7-17 在二叉搜索树上删除一个有两个子女的结点时，可以采用以下三种方法：
(1) 用左子树TL上具有最大关键码的结点X顶替，再递归地删除X。
(2) 交替地用左子树TL上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。
(3) 用左子树TL上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。
试编写程序实现这三个删除方法，并用实例说明哪一个方法最易于达到平衡化。
【解答】
在被删结点有两个子女时用左子树TL中具最大关键码的结点顶替的算法：
template<class Type> BstNode<Type> * BST<Type>,,leftReplace ( BstNode<Type> * ptr ) {
BstNode<Type> * temp = ptr->leftChild; //进到ptr的左子树
while ( temp->rightChild != NULL ) temp = temp->rightChild; //搜寻中序下最后一个结点
ptr->data = temp->data; //用该结点数据代替根结点数据
return temp;
}
② 在被删结点有两个子女时用右子树TR中具最小关键码的结点顶替的算法：
template<class Type> BstNode<Type> * BST<Type>,,rightReplace ( BstNode<Type> * ptr ) {
BstNode<Type> * temp = ptr->rightChild; //进到ptr的右子树
while ( temp->leftChild != NULL ) temp = temp->leftChild; //搜寻中序下最后一个结点
ptr->data = temp->data; //用该结点数据代替根结点数据
return temp;
}
(1) 用左子树TL上具有最大关键码的结点X顶替，再递归地删除X。
template <class Type> void BST<Type>,,Remove ( Type& x,BstNode<Type> *& ptr ) {
//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。
BstNode<Type> * temp;
if ( ptr != NULL )
if ( x < ptr->data ) Remove ( x,ptr->leftChild ); //在左子树中执行删除
else if ( x > ptr->data ) Remove ( x,ptr->rightChild ); //在右子树中执行删除
else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {
// ptr指示关键码为x的结点，它有两个子女
temp = leftReplace ( ptr ); //在ptr的左子树中搜寻中序下最后一个结点顶替x
Remove ( ptr->data,temp ); //在temp为根的子树中删除该结点
}
else { // ptr指示关键码为x的结点，它只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女
else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女
delete temp;
}
}
(2) 交替地用左子树TL上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。
template <class Type> void BST<Type>,,Remove ( Type& x,BstNode<Type> *& ptr,int& dir ) {
//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。在参数表中有一个
//引用变量dir,作为调整方向的标记。若dir = 0,用左子树上具有最大关键码的结点顶替被删关键码; 若dir = 1,
//用右子树上具有最小关键码的结点顶替被删关键码结点,在调用它的程序中设定它的初始值为0。
BstNode<Type> * temp;
if ( ptr != NULL )
if ( x < ptr->data ) Remove ( x,ptr->leftChild,dir ); //在左子树中执行删除
else if ( x > ptr->data ) Remove ( x,ptr->rightChild,dir ); //在右子树中执行删除
else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {
// ptr指示关键码为x的结点，它有两个子女
if ( dir == 0 ) {
temp = leftReplace ( ptr ); dir = 1; //在ptr的左子树中搜寻中序下最后一个结点顶替x
} else {
temp = rightReplace ( ptr ); dir = 0; //在ptr的右子树中搜寻中序下第一个结点顶替x
}
Remove ( ptr->data,temp,dir ); //在temp为根的子树中删除该结点
}
else { // ptr指示关键码为x的结点，它只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女
else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女
delete temp;
}
}
(3) 用左子树TL上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。
#include <stdlib.h>
template <class Type> void BST<Type>,,Remove ( Type& x,BstNode<Type> *& ptr ) {
//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。在程序中用到一个
//随机数发生器rand( ),产生0(32767之间的随机数,将它除以16384,得到0(2之间的浮点数。若其大于1,用左
//子树上具有最大关键码的结点顶替被删关键码; 若其小于或等于1,用右子树上具有最小关键码的结点顶替被删
//关键码结点,在调用它的程序中设定它的初始值为0。
BstNode<Type> * temp;
if ( ptr != NULL )
if ( x < ptr->data ) Remove ( x,ptr->leftChild ); //在左子树中执行删除
else if ( x > ptr->data ) Remove ( x,ptr->rightChild ); //在右子树中执行删除
else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {
// ptr指示关键码为x的结点，它有两个子女
if ( (float) ( rand ( ) / 16384 ) > 1 ) {
temp = leftReplace ( ptr ); dir = 1; //在ptr的左子树中搜寻中序下最后一个结点顶替x
} else {
temp = rightReplace ( ptr ); dir = 0; //在ptr的右子树中搜寻中序下第一个结点顶替x
}
Remove ( ptr->data,temp ); //在temp为根的子树中删除该结点
}
else { // ptr指示关键码为x的结点，它只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女
else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女
delete temp;
}
}
7-18 (1) 设T是具有n个内结点的扩充二叉搜索树,I是它的内路径长度,E是它的外路径长度。试利用归纳法证明 E = I + 2n,n ( 1。
(2) 利用(1)的结果,试说明,成功搜索的平均搜索长度Sn与不成功搜索的平均搜索长度Un之间的关系可用公式
Sn = ( 1 + 1/n ) Un - 1,n ( 1
表示。
【解答】
(1) 用数学归纳法证明。当n = 1时，有1个内结点(I = 0)，2个外结点(E = 2)，满足E = I+2n。设n = k 时结论成立，Ek = Ik + 2k。则当n = k + 1时，将增加一个层次为l的内结点，代替一个层次为l的外结点，同时在第l+1层增加2个外结点，则Ek+1 = Ek – l + 2*(l+1) = Ek + l +2，Ik+1 = Ik + l，将Ek = Ik + 2k代入，有Ek+1 = Ek + l +2 = Ik + 2k + l +2 = Ik+1+ 2(k +1)，结论得证。
因为搜索成功的平均搜索长度Sn与搜索不成功的平均搜索长度Un分别为
其中，ci是各内结点所处层次，cj是各外结点所处层次。因此有
(n+1)Un = En = In + 2n = nSn – n +2n = nSn +n
7-19 求最优二叉搜索树的算法的计算时间为O(n3)，下面给出一个求拟最优二叉搜索树的试探算法，可将计算时间降低到O(nlog2n)。算法的思想是对于关键码序列{ keyl,keyl+1,…,keyh },轮流以keyk为根，k = l,l+1,…,h，求使得 | W[l-1][k-1] - W[k][h] | 达到最小的k，用keyk作为由该序列构成的拟最优二叉搜索树的根。然后对以keyk为界的左子序列和右子序列，分别施行同样的操作，建立根keyk的左子树和右子树。要求：
(1) 使用7.17题的数据，执行这个试探算法建立拟最优二叉搜索树，该树建立的时间代价是多少？
(2) 编写一个函数，实现上述试探算法。要求该函数的时间复杂度应为O(nlog2n)。
【解答】
(1) 各个关键码的权值为 { p1,p2,p3,p4 }，利用题7-17中的W矩阵，轮流让 k = 1,2,3,4为根，此时，下界l = 1,上界h = 4。有
min(W[l-1][k-1] – W[k][h]( = (W[0][1] – W[2][4]( = 2
求得 k = 2。则根结点为2，左子树的权值为 { p1 }，右子树的权值为 { p3,p4 }。
因为左子树只有一个结点，所以，权值为p1的关键码为左子树的根即可。 对于右子树 { p3,p4 }，采用上面的方法，轮流让 k = 3,4为根，此时，下界l = 3，上界h = 4。有
min(W[l-1][k-1] – W[k][h]( = (W[2][2] – W[3][4]( = 1
求得 k = 3。于是以权值为p3的关键码为根，其左子树为空，右子树为 { p4 }。这样，得到拟最优二叉搜索树的结构如下：
建立该拟最优二叉搜索树的时间代价为O(4+1+2+1) = O(8)
(2) 建立该拟最优二叉搜索树的算法
void nearOptiSrchTree ( int W[n+1][n+1],int n,int left,int right ) {
if ( left > right ) { cout <<,Empty Sequence!,<< endl; return; }
if ( left == right ) { cout << left; return; }
int p = 0; int k;
for ( int j = left; j <= right; j++ )
if ( p > abs ( W[left-1][j-1] – W[j][right] )
{ p = abs ( W[left-1][j-1] – W[j][right] ); k = j; }
cout << k;
if ( k == left ) nearOptiSrchTree ( W[n+1][n+1],n,k+1,right );
else if ( k == right ) nearOptiSrchTree ( W[n+1][n+1],n,left,k-1 );
else { nearOptiSrchTree ( W[n+1][n+1],n,left,k-1 );
nearOptiSrchTree ( W[n+1][n+1],n,k+1,right );
}
}
7-20将关键码DEC,FEB,NOV,OCT,JUL,SEP,AUG,APR,MAR,MAY,JUN,JAN 依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树，并标明平衡旋转的类型。
【解答】
7-21 从第7-20题所建立的AVL树中删除关键码MAY，为保持AVL树的特性，应如何进行删除和调整? 若接着删除关键码FEB，又应如何删除与调整?
【解答】
删除关键码MAY,调整
删除关键码FEB,不用调整
7-22 将关键码1,2,3,…,2k-1依次插入到一棵初始为空的AVL树中。试证明结果树是完全平衡的。
【解答】
所谓“完全平衡”是指所有叶结点处于树的同一层次上，并在该层是满的。此题可用数学归纳法证明。
当k = 1时，21-1 = 1，AVL树只有一个结点，它既是根又是叶并处在第0层，根据二叉树性质，应具有20 = 1个结点。因此，满足完全平衡的要求。
设k = n时，插入关键码1,2,3,…,2n-1到AVL树中，恰好每一层(层次号码i = 0,1,…,n-1)有2i个结点，根据二叉树性质，每一层达到最多结点个数，满足完全平衡要求。则当k = n+1时，插入关键码为1,2,3,…,2n-1,2n,…,2n+1-1，总共增加了从2n到2n+1-1的2n+1-1-2n +1 = 2n个关键码，使得AVL树在新增的第n层具有2n个结点，达到该层最多结点个数，因此，满足完全平衡要求。
7-23 对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树,其最大高度是多少? 最小高度是多少?
【解答】
设高度为h（空树的高度为 -1）的AVL树的最少结点数为Nh，则Nh = Fh+3 – 1。Fh是斐波那契数。又设AVL树有n个结点，则其最大高度不超过3 / 2 * log2 (n + 1)，最小高度为 (log2 ( n+1)( -1。
7-1 设A = { 1,2,3 },B = { 3,4,5 }，求下列结果：
(1) A + B (2) A * B (3) A - B
(4) A.Contains (1) (5) A.AddMember (1) (6) A.DelMember (1) (7) A.Min ( )
【解答】
(1) 集合的并A + B = { 1,2,3,4,5 }
(2) 集合的交A * B = { 3 }
(3) 集合的差A - B = { 1,2 }
(4) 包含A.Contains (1) = 1，表示运算结果为"True"
(5) 增加A.AddMember (1)，集合中仍为{ 1,2,3 }，因为增加的是重复元素，所以不加入
(6) 删除A.DelMember (1)，集合中为{ 2,3 }
(7) 求最小元素A.Min ( )，结果为1
7-2 试编写一个算法，打印一个有穷集合中的所有成员。要求使用集合抽象数据类型中的基本操作。如果集合中包含有子集合，各个子集合之间没有重复的元素，采用什么结构比较合适。
【解答】
集合抽象数据类型的部分内容
template <class Type> class Set {
//对象,零个或多个成员的聚集。其中所有成员的类型是一致的,但没有一个成员是相同的。
int Contains ( const Type x ); //判元素x是否集合this的成员
int SubSet ( Set <Type>& right ); //判集合this是否集合right的子集
int operator == ( Set <Type>& right ); //判集合this与集合right是否相等
int Elemtype ( ); //返回集合元素的类型
Type GetData ( ); //返回集合原子元素的值
char GetName ( ); //返回集合this的集合名
Set <Type>* GetSubSet ( ); //返回集合this的子集合地址
Set <Type>* GetNext ( ); //返回集合this的直接后继集合元素
int IsEmpty ( ); //判断集合this是否空。空则返回1,否则返回0
};
ostream& operator << ( ostream& out,Set <Type> t ) {
//友元函数,将集合t输出到输出流对象out。
t.traverse ( out,t ); return out;
}
void traverse ( ostream& out,Set <Type> s ) {
//友元函数,集合的遍历算法
if ( s.IsEmpty ( ) == 0 ) { //集合元素不空
if ( s.Elemtype ( ) == 0 ) out << s.GetName ( ) << ‘{’; //输出集合名及花括号
else if ( s.Elemtype ( ) == 1 ) { //集合原子元素
out << s.GetData ( ); //输出原子元素的值
if ( s.GetNext ( ) != NULL ) out << ‘,’;
}
else { //子集合
traverse ( s,GetSubSet ( ) ); //输出子集合
if ( s.GetNext ( ) != NULL ) out << ‘,’;
}
traverse ( s.GetNext ( ) ); //向同一集合下一元素搜索
}
else out << ‘}’;
}
如果集合中包含有子集合，各个子集合之间没有重复的元素，采用广义表结构比较合适。也可以使用并查集结构。
7-3 当全集合可以映射成1到N之间的整数时，可以用位数组来表示它的任一子集合。当全集合是下列集合时，应当建立什么样的映射？用映射对照表表示。
整数0,1,…,99
(2) 从n到m的所有整数，n ( m
(3) 整数n,n+2,n+4,…,n+2k
(4) 字母 ‘a’,‘b’,‘c’,…,‘z’
(5) 两个字母组成的字符串,其中,每个字母取自 ‘a’,‘b’,‘c’,…,‘z’。
【解答】
(1) i → i的映射关系，i = 0,1,2,…,99
(2) i → n-i 的映射关系，i = n,n+1,n+2,…,m
0
1
2
m-n
n
n+1
n+2
…
m
(3) i → (i-n)/2 的映射关系，i = n,n+2,n+4,…,n+2k
0
1
2
k
n
n+2
n+4
…
n+2k
(4) ord (c) → ord (c) - ord ('a') 的映射关系，c = 'a','b','c',…,'z'
0
1
2
25
'a'
'b'
'c'
…
'z'
(5) (ord (c1) - ord ('a') )*26 + ord (c2) - ord ('a')的映射关系，c1 = c2 = 'a','b','c',…,'z'
0
1
2
675
'aa'
'ab'
'ba'
…
'zz'
7-4 试证明：集合A是集合B的子集的充分必要条件是集合A和集合B的交集是A。
【证明】
必要条件：因为集合A是集合B的子集，有A ( B，此时，对于任一x ( A，必有x ( B，因此可以推得x ( A∩B，就是说，如果A是B的子集，一定有A∩B = A。
充分条件：如果集合A和集合B的交集A∩B是A，则对于任一x ( A，一定有x ( A∩B，因此可以推得x ( B，由此可得A ( B，即集合A 是集合B的子集。
7-5 试证明：集合A是集合B的子集的充分必要条件是集合A和集合B的并集是B。
【证明】
必要条件：因为集合A是集合B的子集，有A ( B，此时，对于任一x ( A，必有x ( B,它一定在A∪B中。另一方面，对于那些x' ( A,但x' ( B的元素，它也必在A∪B中，因此可以得出结论：凡是属于集合B的元素一定在A∪B中，A∪B = B。
充分条件：如果存在元素x ( A且x ( B，有x ( A∪B，但这不符合集合A和集合B的并集A∪B是B的要求。集合的并A∪B是集合B的要求表明，对于任一x ( A∪B，同时应有x ( B。对于那些满足x' ( A的x'，既然x' ( A∪B，也应当x' ( B，因此，在此种情况下集合A应是集合B的子集。
7-6 设+、*、-是集合的或、与、差运算，试举一个例子，验证
A + B = (A - B) + (B - A) + A * B
【解答】
若设集合A = { 1,3,4,7,9,15 }，集合B = { 2,3,5,6,7,12,15,17 }。则
A + B = { 1,2,3,4,5,6,7,9,12,15,17 }
又A * B = { 3,7,15 },A – B = { 1,4,9 },B – A = { 2,5,6,12,17 }
则 (A – B) + (B – A) + A * B = { 1,2,3,4,5,6,7,9,12,15,17 }
有 A + B = (A – B) + ( B – A ) + A * B。
7-7 给定一个用无序链表表示的集合，需要在其上执行operator+( ),operator*( ),operator- ( ),Contains(x),AddMember (x),DelMember(x),Min( )，试写出它的类声明，并给出所有这些成员函数的实现。
【解答】
下面给出用无序链表表示集合时的类的声明。
template <class Type> class Set; //用以表示集合的无序链表的类的前视定义
template <class Type> class SetNode { //集合的结点类定义
friend class SetList<Type>;
private:
Type data; //每个成员的数据
SetNode <Type> *link; //链接指针
public:
SetNode (const Type& item ),data (item),link (NULL); //构造函数
};
template <class Type> class Set { //集合的类定义
private:
SetNode <Type> *first,*last; //无序链表的表头指针,表尾指针
public:
SetList ( ) { first = last = new SetNode <Type>(0); } //构造函数
~SetList ( ) { MakeEmpty ( ); delete first; } //析构函数
void MakeEmpty ( ); //置空集合
int AddMember ( const Type& x ); //把新元素x加入到集合之中
int DelMember ( const Type& x ); //把集合中成员x删去
Set <Type>& operator = ( Set <Type>& right ); //复制集合right到this。
Set <Type>& operator + ( Set <Type>& right ); //求集合this与集合right的并
Set <Type>& operator * ( Set <Type>& right ); //求集合this与集合right的交
Set <Type>& operator - ( Set <Type>& right ); //求集合this与集合right的差
int Contains ( const Type& x ); //判x是否集合的成员
int operator == ( Set <Type>& right ); //判集合this与集合right相等
Type& Min ( ); //返回集合中的最小元素的值
}
operator + ( )
template <class Type> Set <Type>& Set <Type>,,operator + ( Set <Type>& right ) {
//求集合this与集合right的并,计算结果通过临时集合temp返回，this集合与right集合不变。
SetNode <Type> *pb = right.first->link; //right集合的链扫描指针
SetNode <Type> *pa,*pc; //this集合的链扫描指针和结果链的存放指针
Set <Type> temp;
pa = first->link; pc = temp.first;
while ( pa != NULL ) { //首先把集合this的所有元素复制到结果链
pc->link = new SetNode<Type> ( pa->data ) ;
pa = pa->link; pc = pc->link;
}
while ( pb != NULL ) { //将集合right中元素一个个拿出到this中查重
pa = first->link;
while ( pa != NULL && pa->data != pb->data ) pa = pa->link;
if ( pa == NULL ) //在集合this中未出现,链入到结果链
{ pc->link = new SetNode<Type> ( pa->data ); pc = pc->link; }
pb = pb->link;
}
pc->link = NULL; last = pc; //链表收尾
return temp;
}
(2) operator * ( )
template <class Type> Set <Type>& Set <Type>,,operator * ( Set <Type>& right ) {
//求集合this与集合right的交,计算结果通过临时集合temp返回，this集合与right集合不变。
SetNode<Type> *pb = right.first->link; //right集合的链扫描指针
Set <Type> temp;
SetNode <Type> *pc = temp.first; //结果链的存放指针
while ( pb != NULL ) { //将集合right中元素一个个拿出到this中查重
SetNode<Type> *pa = first->link; //this集合的链扫描指针
while ( pa != NULL ) {
if ( pa->data == pb->data ) //两集合公有的元素,插入到结果链
{ pc->link = new SetNode<Type> ( pa->data ); pc = pc->link; }
pa = pa->link;
}
pb = pb->link;
}
pc->link = NULL; last = pc; //置链尾指针
return temp;
}
(3) operator - ( ),
template <class Type> Set <Type>& Set <Type>,,operator - ( Set <Type>& right ) {
//求集合this与集合right的差,计算结果通过临时集合temp返回，this集合与right集合不变。
SetNode<Type> *pa = first->link; //this集合的链扫描指针
Set <Type> temp;
SetNode<Type> *pc = temp->first; //结果链的存放指针
while ( pa != NULL ) { //将集合this中元素一个个拿出到right中查重
SetNode <Type> *pb = right.first->link; //right集合的链扫描指针
while ( pb != NULL && pa->data != pb->data )
pb = pb->link;
if ( pb == NULL ) //此this中的元素在right中未找到,插入
{ pc->link = new SetNode <Type> ( pa->data ); pc = pc->link; }
pa = pa->link;
}
pc->link = NULL; last = pc; //链表收尾
return temp;
}
(4) Contains(x)
template <class Type> int Set <Type>,,Contains ( const Type& x ) {
//测试函数,如果x是集合的成员,则函数返回1,否则返回0。
SetNode<Type> * temp = first->link; //链的扫描指针
while ( temp != NULL && temp->data != x ) temp = temp->link; //循链搜索
if ( temp != NULL ) return 1; //找到,返回1
else return 0; //未找到,返回0
}
(5) AddMember (x)
template <class Type> int Set <Type>,,AddMember ( const Type& x ) {
//把新元素x加入到集合之中。若集合中已有此元素,则函数返回0,否则函数返回1。
SetNode<Type> * temp = first->link; // temp是扫描指针
while ( temp != NULL && temp->data != x ) temp = temp->link; /循链扫描
if ( temp != NULL ) return 0; //集合中已有此元素,不加
last = last->link = new SetNode (x); //否则,创建数据值为x的新结点,链入
return 1;
}
(6) DelMember (x)
template <class Type> int Set <Type>,,DelMember ( const Type& x ) {
//把集合中成员x删去。若集合不空且元素x在集合中,则函数返回1,否则返回0。
SetNode<Type> * p = first->link,*q = first;
while ( p != NULL ) {
if ( p->data == x ) { //找到
q->link = p->link; //重新链接
if ( p == last ) last = q; //删去链尾结点时改链尾指针
delete p; return 1; //删除含x结点
}
else { q = p; p = p->link; } //循链扫描
return 0; //集合中无此元素
}
(7) Min ( )
template <class Type> SetNode<Type> * Set <Type>,,Min ( ) {
//在集合中寻找值最小的成员并返回它的位置。
SetNode<Type> * p = first->link,*q = first->link; //p是检测指针,q是记忆最小指针
while ( p != NULL ) {
if ( p->data < q->data ) q = p; //找到更小的,让q记忆它
p = p->link; //继续检测
}
return q;
}
7-8 设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908。试画出对其进行折半搜索时的二叉搜索树,并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
【解答】
7-9 若对有n个元素的有序顺序表和无序顺序表进行顺序搜索,试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?
(1) 搜索失败;
(2) 搜索成功,且表中只有一个关键码等于给定值k的对象;
(3) 搜索成功,且表中有若干个关键码等于给定值k的对象,要求一次搜索找出所有对象。
【解答】
(1) 不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。
(2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。
(3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。
前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。
7-10 假定用一个循环链表来实现一个有序表，并让指针head指向具有最小关键码的结点。指针current初始时等于head，每次搜索后指向当前检索的结点，但如果搜索不成功则current重置为head。试编写一个函数search(head,current,key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针0。请说明如何保持指针current以减少搜索时的平均搜索长度。
【解答】
相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据成员。
template<class Type>
ListNode <Type> * Search ( ListNode<Type> * head,ListNode<Type> *& current,Type key ) {
ListNode <Type> * p,* q;
if ( key < current ) { p = head; q = current; } //确定检测范围,用p,q指示
else { p = current; q = head; }
while ( p != q && p->data < key ) p = p->link; //循链搜索其值等于key的结点
if ( p->data == key ) { current = p; return p; } //找到,返回结点地址
else { current = head; return NULL; } //未找到,返回空指针
}
7-11 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针p总是指向最后成功搜索到的结点，搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数search(head,p,key)，检索具有关键码key的结点，并相应地修改p。最后请给出搜索成功和搜索不成功时的平均搜索长度。
【解答】
template <class Type>
DblListNode<Type> * Search ( DblListNode<Type> * head,DblListNode<Type> *& p,Type key ) {
//在以head为表头的双向有序链表中搜索具有值key的结点。算法可视为双向链表类和双向链表结点类的友元
//函数。若给定值key大于结点p中的数据,从p向右正向搜索,否则,从p向左反向搜索。
DblListNode<Type> * q = p;
if ( key < p->data ) { while ( q != NULL && q->data > key ) q = q-> lLink; } //反向搜索
else { while ( q != NULL && q->data < key ) q = q-> rLink; } //正向搜索
if ( q != NULL && q->data == key ) { p = q; return p; } //搜索成功
else return NULL;
}
如果指针p处于第i个结点(i = 1,2,…,n)，它左边有i-1个结点，右边有n-i个结点。找到左边第i-1号结点比较2次，找到第i-2号结点比较3次，…，找到第1号结点比较i次，一般地，找到左边第k个结点比较i-k+1次(k = 1,2,…,i-1)。找到右边第i+1号结点比较2次，找到第i+2号结点比较3次，…，找到第n号结点比较n-i+1次，一般地，找到右边第k个结点比较k-i+1次(k = i+1,i+2,…,n)。因此，当指针处于第i个结点时的搜索成功的平均数据比较次数为
一般地，搜索成功的平均数据比较次数为
如果指针p处于第i个结点(i = 1,2,…,n)，它左边有i个不成功的位置，右边有n-i+1个不成功的位置。
一般地，搜索不成功的平均数据比较次数为
7-12 在一棵表示有序集S的二叉搜索树中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S = S1 ( S2 ( S3。若对于任意的a ( S1,b ( S2,c ( S3,是否总有a ( b ( c？为什么？
【解答】
答案是否定的。举个反例：看下图粗线所示的路径
S1 = { 15 },S2 = { 25,30,35,45 },S3 = { 40,50,65,70 }
c = 40 ( S3，b = 45 ( S2，b ( c 不成立。
7-13 请给出下列操作序列运算的结果：Union(1,2),Union(3,4),Union(3,5),Union(1,7),Union(3,6),Union(8,9),Union(1,8),Union(3,10),Union(3,11),Union(3,12),Union(3,13),Union(14,15),Union(16,17),Union(14,16),Union(1,3),Union(1,14)，要求
(1) 以任意方式执行Union；
(2) 根据树的高度执行Union；
(3) 根据树中结点个数执行Union。
【解答】
(1) 对于union(i,j)，以i作为j的双亲
(2) 按i和j为根的树的高度实现union(i,j)，高度大者为高度小者的双亲；
(3) 按i和j为根的树的结点个数实现union(i,j)，结点个数大者为结点个数小者的双亲。
7-14 有n个结点的二叉搜索树具有多少种不同形态?
【解答】
7-15 设有一个输入数据的序列是 { 46,25,78,62,12,37,70,29 },试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
【解答】
7-16 设有一个标识符序列{else,public,return,template}，p1=0.05,p2=0.2,p3=0.1,p4=0.05,q0=0.2,q1=0.1,q2=0.2,q3=0.05,q4=0.05，计算W[i][j]、C[i][j]和R[i][j]，构造最优二叉搜索树。
【解答】
将标识符序列简化为 { e,p,r,t }，并将各个搜索概率值化整，有
e
p
r
t
p1 = 1
p2 = 4
p3 = 2
p4 = 1
q0 = 4
q1 = 2
q2 = 4
q3 = 1
q4 = 1
(1) 首先构造只有一个内结点的最优二叉搜索树:
三个矩阵的内容如下:
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
4
7
15
18
20
0
0
7
22
32
39
0
0
1
2
2
2
1
2
10
13
15
1
0
10
20
27
1
0
2
2
2
2
4
7
9
2
0
7
12
2
0
3
3
3
1
3
3
0
3
3
0
4
4
1
4
0
4
0
W[i][j] C[i][j] R[i][j]
(2) 构造具有两个内结点的最优二叉搜索树
(3) 构造具有三个内结点的最优二叉搜索树
(4) 构造具有四个内结点的最优二叉搜索树
7-17 在二叉搜索树上删除一个有两个子女的结点时，可以采用以下三种方法：
(1) 用左子树TL上具有最大关键码的结点X顶替，再递归地删除X。
(2) 交替地用左子树TL上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。
(3) 用左子树TL上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。
试编写程序实现这三个删除方法，并用实例说明哪一个方法最易于达到平衡化。
【解答】
在被删结点有两个子女时用左子树TL中具最大关键码的结点顶替的算法：
template<class Type> BstNode<Type> * BST<Type>,,leftReplace ( BstNode<Type> * ptr ) {
BstNode<Type> * temp = ptr->leftChild; //进到ptr的左子树
while ( temp->rightChild != NULL ) temp = temp->rightChild; //搜寻中序下最后一个结点
ptr->data = temp->data; //用该结点数据代替根结点数据
return temp;
}
② 在被删结点有两个子女时用右子树TR中具最小关键码的结点顶替的算法：
template<class Type> BstNode<Type> * BST<Type>,,rightReplace ( BstNode<Type> * ptr ) {
BstNode<Type> * temp = ptr->rightChild; //进到ptr的右子树
while ( temp->leftChild != NULL ) temp = temp->leftChild; //搜寻中序下最后一个结点
ptr->data = temp->data; //用该结点数据代替根结点数据
return temp;
}
(1) 用左子树TL上具有最大关键码的结点X顶替，再递归地删除X。
template <class Type> void BST<Type>,,Remove ( Type& x,BstNode<Type> *& ptr ) {
//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。
BstNode<Type> * temp;
if ( ptr != NULL )
if ( x < ptr->data ) Remove ( x,ptr->leftChild ); //在左子树中执行删除
else if ( x > ptr->data ) Remove ( x,ptr->rightChild ); //在右子树中执行删除
else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {
// ptr指示关键码为x的结点，它有两个子女
temp = leftReplace ( ptr ); //在ptr的左子树中搜寻中序下最后一个结点顶替x
Remove ( ptr->data,temp ); //在temp为根的子树中删除该结点
}
else { // ptr指示关键码为x的结点，它只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女
else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女
delete temp;
}
}
(2) 交替地用左子树TL上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。
template <class Type> void BST<Type>,,Remove ( Type& x,BstNode<Type> *& ptr,int& dir ) {
//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。在参数表中有一个
//引用变量dir,作为调整方向的标记。若dir = 0,用左子树上具有最大关键码的结点顶替被删关键码; 若dir = 1,
//用右子树上具有最小关键码的结点顶替被删关键码结点,在调用它的程序中设定它的初始值为0。
BstNode<Type> * temp;
if ( ptr != NULL )
if ( x < ptr->data ) Remove ( x,ptr->leftChild,dir ); //在左子树中执行删除
else if ( x > ptr->data ) Remove ( x,ptr->rightChild,dir ); //在右子树中执行删除
else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {
// ptr指示关键码为x的结点，它有两个子女
if ( dir == 0 ) {
temp = leftReplace ( ptr ); dir = 1; //在ptr的左子树中搜寻中序下最后一个结点顶替x
} else {
temp = rightReplace ( ptr ); dir = 0; //在ptr的右子树中搜寻中序下第一个结点顶替x
}
Remove ( ptr->data,temp,dir ); //在temp为根的子树中删除该结点
}
else { // ptr指示关键码为x的结点，它只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女
else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女
delete temp;
}
}
(3) 用左子树TL上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。
#include <stdlib.h>
template <class Type> void BST<Type>,,Remove ( Type& x,BstNode<Type> *& ptr ) {
//私有函数：在以ptr为根的二叉搜索树中删除含x的结点。若删除成功则新根通过ptr返回。在程序中用到一个
//随机数发生器rand( ),产生0(32767之间的随机数,将它除以16384,得到0(2之间的浮点数。若其大于1,用左
//子树上具有最大关键码的结点顶替被删关键码; 若其小于或等于1,用右子树上具有最小关键码的结点顶替被删
//关键码结点,在调用它的程序中设定它的初始值为0。
BstNode<Type> * temp;
if ( ptr != NULL )
if ( x < ptr->data ) Remove ( x,ptr->leftChild ); //在左子树中执行删除
else if ( x > ptr->data ) Remove ( x,ptr->rightChild ); //在右子树中执行删除
else if ( ptr->leftChild != NULL && ptr->rightChild != NULL ) {
// ptr指示关键码为x的结点，它有两个子女
if ( (float) ( rand ( ) / 16384 ) > 1 ) {
temp = leftReplace ( ptr ); dir = 1; //在ptr的左子树中搜寻中序下最后一个结点顶替x
} else {
temp = rightReplace ( ptr ); dir = 0; //在ptr的右子树中搜寻中序下第一个结点顶替x
}
Remove ( ptr->data,temp ); //在temp为根的子树中删除该结点
}
else { // ptr指示关键码为x的结点，它只有一个或零个子女
temp = ptr;
if ( ptr->leftChild == NULL ) ptr = ptr->rightChild; //只有右子女
else if ( ptr->rightChild == NULL ) ptr = ptr->leftChild; //只有左子女
delete temp;
}
}
7-18 (1) 设T是具有n个内结点的扩充二叉搜索树,I是它的内路径长度,E是它的外路径长度。试利用归纳法证明 E = I + 2n,n ( 1。
(2) 利用(1)的结果,试说明,成功搜索的平均搜索长度Sn与不成功搜索的平均搜索长度Un之间的关系可用公式
Sn = ( 1 + 1/n ) Un - 1,n ( 1
表示。
【解答】
(1) 用数学归纳法证明。当n = 1时，有1个内结点(I = 0)，2个外结点(E = 2)，满足E = I+2n。设n = k 时结论成立，Ek = Ik + 2k。则当n = k + 1时，将增加一个层次为l的内结点，代替一个层次为l的外结点，同时在第l+1层增加2个外结点，则Ek+1 = Ek – l + 2*(l+1) = Ek + l +2，Ik+1 = Ik + l，将Ek = Ik + 2k代入，有Ek+1 = Ek + l +2 = Ik + 2k + l +2 = Ik+1+ 2(k +1)，结论得证。
因为搜索成功的平均搜索长度Sn与搜索不成功的平均搜索长度Un分别为
其中，ci是各内结点所处层次，cj是各外结点所处层次。因此有
(n+1)Un = En = In + 2n = nSn – n +2n = nSn +n
7-19 求最优二叉搜索树的算法的计算时间为O(n3)，下面给出一个求拟最优二叉搜索树的试探算法，可将计算时间降低到O(nlog2n)。算法的思想是对于关键码序列{ keyl,keyl+1,…,keyh },轮流以keyk为根，k = l,l+1,…,h，求使得 | W[l-1][k-1] - W[k][h] | 达到最小的k，用keyk作为由该序列构成的拟最优二叉搜索树的根。然后对以keyk为界的左子序列和右子序列，分别施行同样的操作，建立根keyk的左子树和右子树。要求：
(1) 使用7.17题的数据，执行这个试探算法建立拟最优二叉搜索树，该树建立的时间代价是多少？
(2) 编写一个函数，实现上述试探算法。要求该函数的时间复杂度应为O(nlog2n)。
【解答】
(1) 各个关键码的权值为 { p1,p2,p3,p4 }，利用题7-17中的W矩阵，轮流让 k = 1,2,3,4为根，此时，下界l = 1,上界h = 4。有
min(W[l-1][k-1] – W[k][h]( = (W[0][1] – W[2][4]( = 2
求得 k = 2。则根结点为2，左子树的权值为 { p1 }，右子树的权值为 { p3,p4 }。
因为左子树只有一个结点，所以，权值为p1的关键码为左子树的根即可。 对于右子树 { p3,p4 }，采用上面的方法，轮流让 k = 3,4为根，此时，下界l = 3，上界h = 4。有
min(W[l-1][k-1] – W[k][h]( = (W[2][2] – W[3][4]( = 1
求得 k = 3。于是以权值为p3的关键码为根，其左子树为空，右子树为 { p4 }。这样，得到拟最优二叉搜索树的结构如下：
建立该拟最优二叉搜索树的时间代价为O(4+1+2+1) = O(8)
(2) 建立该拟最优二叉搜索树的算法
void nearOptiSrchTree ( int W[n+1][n+1],int n,int left,int right ) {
if ( left > right ) { cout <<,Empty Sequence!,<< endl; return; }
if ( left == right ) { cout << left; return; }
int p = 0; int k;
for ( int j = left; j <= right; j++ )
if ( p > abs ( W[left-1][j-1] – W[j][right] )
{ p = abs ( W[left-1][j-1] – W[j][right] ); k = j; }
cout << k;
if ( k == left ) nearOptiSrchTree ( W[n+1][n+1],n,k+1,right );
else if ( k == right ) nearOptiSrchTree ( W[n+1][n+1],n,left,k-1 );
else { nearOptiSrchTree ( W[n+1][n+1],n,left,k-1 );
nearOptiSrchTree ( W[n+1][n+1],n,k+1,right );
}
}
7-20将关键码DEC,FEB,NOV,OCT,JUL,SEP,AUG,APR,MAR,MAY,JUN,JAN 依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树，并标明平衡旋转的类型。
【解答】
7-21 从第7-20题所建立的AVL树中删除关键码MAY，为保持AVL树的特性，应如何进行删除和调整? 若接着删除关键码FEB，又应如何删除与调整?
【解答】
删除关键码MAY,调整
删除关键码FEB,不用调整
7-22 将关键码1,2,3,…,2k-1依次插入到一棵初始为空的AVL树中。试证明结果树是完全平衡的。
【解答】
所谓“完全平衡”是指所有叶结点处于树的同一层次上，并在该层是满的。此题可用数学归纳法证明。
当k = 1时，21-1 = 1，AVL树只有一个结点，它既是根又是叶并处在第0层，根据二叉树性质，应具有20 = 1个结点。因此，满足完全平衡的要求。
设k = n时，插入关键码1,2,3,…,2n-1到AVL树中，恰好每一层(层次号码i = 0,1,…,n-1)有2i个结点，根据二叉树性质，每一层达到最多结点个数，满足完全平衡要求。则当k = n+1时，插入关键码为1,2,3,…,2n-1,2n,…,2n+1-1，总共增加了从2n到2n+1-1的2n+1-1-2n +1 = 2n个关键码，使得AVL树在新增的第n层具有2n个结点，达到该层最多结点个数，因此，满足完全平衡要求。
7-23 对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树,其最大高度是多少? 最小高度是多少?
【解答】
设高度为h（空树的高度为 -1）的AVL树的最少结点数为Nh，则Nh = Fh+3 – 1。Fh是斐波那契数。又设AVL树有n个结点，则其最大高度不超过3 / 2 * log2 (n + 1)，最小高度为 (log2 ( n+1)( -1。
