第七章 算法题

（1）试写出折半查找的递归算法。

 [算法描述]

int  BinSrch（rectype r[ ]，int  k，low，high）//在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。{if（low≤high）  //low和high分别是有序表的下界和上界{mid=（low+high）/2；if（r[mid].key==k）return  （mid）；else if（r[mid].key>k）return  （BinSrch（r,k，mid+1，high））;else return  （BinSrch（r,k，low，mid-1））;}else  return  （0）；//查找失败。}//算法结束

（2）试写一个判别给定二叉树是否为二叉排序树的算法。

[题目分析] 根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。

[算法描述]

#define true 1#define false 0typedef struct node{datatype data; struct node *lchild,*rchild;} *BTree;void  JudgeBST（BTree T,int  flag）// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。{ if（T!=null && flag）{ Judgebst（T->lchild,flag）；// 中序遍历左子树if（pre==null）pre=T；// 中序遍历的第一个结点不必判断else  if（pre->data<T->data）pre=T；//前驱指针指向当前结点else{flag=flase；}   //不是完全二叉树Judgebst （T->rchild,flag）；// 中序遍历右子树}//JudgeBST算法结束

（3）已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为（lchild,data,rchild），其中lchild，rchild分别指向该结点左、右孩子的指针，data域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值>=x的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其他满足条件的结点。

[题目分析]本题算法之一是如上题一样，中序遍历二叉树，在“访问根结点”处判断结点值是否≥x，如是则输出，并记住第一个≥x值结点的指针。这里给出另一个算法，利用二叉排序树的性质，如果根结点的值>=x,则除左分枝中可能有<x的结点外都应输出。所以从根结点开始查找，找到结点值<x的结点后，将其与双亲断开输出整棵二叉排序树。如果根结点的值<x,则沿右子树查找第一个≥x的结点，找到后，与上面同样处理。

  void  Print（BSTree  t）// 中序输出以t为根的二叉排序树的结点{if（t）{Print（t->lchild）；Cout<<t-data；Print（t->rchild）；}}void  PrintAllx(BSTree bst，datatype x）//在二叉排序树bst中，查找值≥x的结点并输出{p=bst；if（p）{while（p && p->data<x）p=p->rchild；//沿右分枝找第一个值≥x的结点bst=p; //bst所指结点是值≥x的结点的树的根if（p）{f=p; p=p->lchild ；//找第一个值<x的结点while（p && p->data≥x）//沿左分枝向下，找第一个值<x的结点{f=p；p=p->lchild ；} //f是p的双亲结点的指针，指向第一个值≥x的结点if(p) f->lchild=null; //双亲与找到的第一个值<x的结点断开Print(bst)；//输出以bst为根的子树}//while}//内层if（p）}//第一层if（p）}//PrintAllx

（4）已知二叉树T的结点形式为（lling,data,count,rlink），在树中查找值为X的结点，若找到，则记数（count）加1，否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。

[算法描述]

void SearchBST(BiTree &T,int target){BiTree s,q,f;  //以数据值target,新建结点ss=new BiTNode;s->data.x=target;s->data.count=0;s->lchild=s->rchild=NULL;if(!T){T=s;return ;}   //如果该树为空则跳出该函数f=NULL;q=T;while (q){if (q->data.x==target){q->data.count++;return ;}  //如果找到该值则计数加一f=q;if (q->data.x>target)   //如果查找值比目标值大，则为该树左孩子q=q->lchild;else                                     //否则为右孩子q=q->rchild;}  //将新结点插入树中if(f->data.x>target)f->lchild=s;elsef->rchild=s;}

（5）假设一棵平衡二叉树的每个结点都表明了平衡因子b，试设计一个算法，求平衡二叉树的高度。

[题目分析] 因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左（当b=1时）或右（当b=-1时）向下查找。

[算法描述]

   int   Height（BSTree t）// 求平衡二叉树t的高度{level=0；p=t；while（p）{level++； // 树的高度增1if（p->bf<0）p=p->rchild；//bf=-1 沿右分枝向下//bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存储定义else p=p->lchild；        //bf>=0 沿左分枝向下}//whilereturn  （level）；//平衡二叉树的高度} //算法结束

（6）分别写出在散列表中插入和删除关键字为K的一个记录的算法，设散列函数为H，解决冲突的方法为链地址法。

[算法描述]

bool insert(){int data;cin>>data;int ant=hash(data);LinkList p=HT[ant];   //初始化散列表while (p->next){if(p->next->data==data)return false;  p=p->next;}   //找到插入位置LinkList s;s=new LNode;s->data=data;s->next=p->next;p->next=s;  //插入该结点return true;}bool deletes(){int data;cin>>data;int ant=hash(data);LinkList p=HT[ant];  //初始化散列表while (p->next){if(p->next->data==data){LinkList s=p->next;p->next=s->next;delete s;  //删除该结点return true;}  //找到删除位置p=p->next； //遍历下一个结点}return false;}