|
《王道数据结构》算法设计题
整理出《王道数据结构》一书中所有(不确定)的课后代码题
二、线性表
(2.1) 顺序表
2.1.1 顺序表查找最小值并返回被删元素的值
/*
搜索整个顺序表，查找最小值元素并记住其位置，搜索结束后用最后一个元素填补空出的原最小值元素的位置。
*/
bool Del_Min(sqList &L,int &value)
{
if(L.length ==0)
return false;
value = L.data[0];
int pos = 0;
for(int i=1;idata ==x)
{
q = p; //q指向该结点
p = p->next;
pre->next = p; //删除*q结点
free(q);
}
else //否则,pre和p同步后移
{
pre= p;
p = p->next;
}
}//while
}
2.3.5 带头结点的单链表L逆向输出每个结点的值
void R_Print(LinkList &L)
{
if(L->next != NULL)
{
R_Print(L->next);
}
print(L->data);
}
2.3.6 带头结点的单链表L中删除最小值结点(假设最小值结点唯一)，时间高效
LinkList Delete_Min(LinkList &L)
{
LNode *pre = L,*P = pre->next; //p为工作指针,pre指向其前驱
LNode *minpre = pre,*minp = p; //保存最小值结点及其前驱
while(p!=NULL)
{
if(p->data < minp->data)
{
minp = p; //找到比之前找到的最小值结点更小的结点
minpre = pre;
}
pre = p; //继续扫描下一个结点
p = p->next;
}
minpre->next = minp->next; //删除最小值结点
free(minp);
return L;
}
//若本题改为不带头结点的单链表，则实现上会有所不同，请读者自行思考。
2.3.7 带头结点的单链表就地逆置，即辅助空间复杂度为O(1)。
/*
将头结点摘下，然后从第一结点开始，依次插入到头结点的后面，直到最后一个结点为止，这样就实现了链表的逆置。
*/
LinkList Reverse_1(LinkList L)
{
LNode *p,*r; //p为工作指针，r为p的后继，以防断链
p = L->next; //从第一个元素结点开始
L->next = NULL; //先将头结点L的next域置为NULL
while(p!=NULL) //依次将元素结点摘下
{
r = p->next; //暂存p的后继
p->next = L->next; //将p结点插入到头结点之后
L->next = p;
p = r;
}
return L;
}
2.3.8 带头结点的单链表L使其元素递增有序
/*
采用直接插入排序算法的思想，先构成只含一个数据结点的有序单链表，然后依次扫描单链表中剩下的结点*p (直至p==NULL为止)，在有序表中通过比较查找 *p 的前驱结点*pre，然后*p插入到*pre之后。该算法时间复杂度为O(n^2).
*/
void Sort(LinkList &L)
{
LNode *p = L->next,*pre;
LNode *r = p->next; //r保持*p后继结点指针，以保证不断链
p->next = NULL; //构造只含一个数据结点的有序表
p = r;
while(p!=NULL)
{
r = p->next; //保存*p 的后继结点指针
pre = L;
while(pre->next != NULL && pre->next->data < p->data)
pre = pre->next; //在有序表中查找插入*p的前驱结点*pre
p->next = pre->next; //将*p插入到*pre之后
pre->next = p;
p = r; //扫描单链表中剩下的结点
}
}
2.3.9 带头结点的单链表L无序，删除表中所有介于给定的两个值之间的元素(若存在)
/*
因为链表是无序的，所以只能逐个结点进行检查，进行删除。
*/
void RangeDelete(LinkList &L,int min,int max)
{
LNode *pr = L,
*p = L->link; //p是检测指针，pr是其前驱
while(p!=NULL)
{
if(p->data>min && p->datalink = p->link;
free(p);
p = pr->link;
}
else //否则继续寻找被删结点
{
pr = p;
p = p->link;
}
}
}
2.3.10 找出两个链表的公共结点
/*
两个链表有公共结点，则两条链表的拓扑形状像一条平放的Y。
算法思路: 首先分别遍历两个链表得到它们的长度，并求出两个长度之差。在长的链表上先遍历长度之差个结点之后，再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束。此时，该方法的时间复杂度为O(len1+len2)。
*/
LinkList Search_lst_Common(LinkList L1,LinkList L2)
{
int len1 = Length(L1),len2 = Length(L2);
LinkList longList,shortList;
if(len1>len2)
{
longList = L1->next;
shortList = L2->next;
dist = len1 - len2;
}
else
{
longList = L2->next;
shortList = L1->next;
dist = len2-len1;
}
while(dist--)
longList = longList->next;
while(longList != NULL)
{
if(longList == shortList)
return longList;
else
{
longList = longList->next;
shortList = shortList->next;
}
}//while
return NULL;
}
2.3.11 带头结点的单链表,head为头指针,递增输出数据元素，并释放结点存储空间。(不允许使用数组作为辅助空间)
/*
对链表遍历，在每次遍历中找出整个链表的最小值元素，输出并释放结点所占空间;再查找次小值元素，输出并释放空间，如此下去，直至链表为空，最后释放头结点所占存储空间。该算法的时间复杂度为O(n^2)。
*/
void Min_Delete(LinkList &head)
{
while(head->next !=NULL) //循环到仅剩头结点
{
pre = head; //pre为元素最小值结点的前驱结点的指针
p = pre->next; //p为工作指针
while(p->next != NULL)
{
if(p->next->data < pre->next->data);
pre = p; //记住当前最小值结点的前驱
p = p->next;
}
print(pre->next->data); //输出最小值
u = pre->next; //删除元素值最小的结点，释放结点空间
pre->next = u->next;
free(u);
}//while
free(head); //释放头结点
}
2.3.12 带头结点的单链表A分解为使A表中含有原表中序号为奇数的元素，B表中含有原表中序号为偶数的元素，相对顺序保持不变。
/*
设置一个访问变量(初值为0),每访问一个结点序号自动加1，然后根据序号的奇偶性将结点插入到A表或B表中，重复以上操作直到表尾。
为了保持原来结点的顺序，采用尾插法建立单链表。此外，本算法完全可以不用设置序号变量。while循环中的代码改为将结点插入到表A中并将下一结点插入到B中，这样while中第一处理的结点就是奇数号结点，第二处理的就是偶数号结点。
*/
LinkList DisCreat_1(LinkList &A)
{
int i=0;
B = (LinkList)malloc(sizeof(LNode));
B->next = NULL;
LNode *ra = A,*rb = B;
p = A->next;
A->next = NULL;
while(p!=NULL)
{
i++;
if(i%2==0)
{
rb->next = p;
rb = p;
}
else
{
ra-next = p;
ra = p;
}
p = p->next;
}
ra->next = NULL;
rb-next = NULL;
return B;
}
2.3.13 带头结点的单链表C={a1,b1,a2,b2······am,bn}拆解为两个线性表，使得A={a1,a2···an}，B = {bm,····b2,b1}
/*
采用上题的思路，不设序号变量，二者的的区别在于对B表的建立采用头插法。这里需要注意的是，采用头插法插入结点后，*p的指针域已改变，若不设变量保存其后继结点则会引起断链，从而导致算法出错。
*/
LinkList DisCreat_2(LinkList &A)
{
LinkList B = (LinkList)malloc(sizeof(LNode)); //创建B表表头
B->next = NULL; // B表的初始化
LNode *p = A->next,*q; //p为工作指针
LNode *ra = A; //ra始终指向A的尾结点
while(p!=NULL)
{
ra->next = p; //将*p链到A的表尾
ra = p;
p = p->next;
q = p->next; // 头插后,*p将断链，因此用q记忆*p的后继
p->next = B->next; //将*p插入到B的前端
B->next = p;
p = q;
}
ra->next = NULL; //A尾结点的next域置空
return B;
}
2.3.14 递增的单链表，去掉表中重复的元素，只保留一个数值
/*
由于是有序表，所有相同值域的结点都是相邻的。用p扫描递增单链表L,若*p结点的值域等于其后继结点的值域，则删除后者，否则p移向下一个结点。实际时间复杂度为O(n),空间复杂度为O(1)。
*/
void Del_Same(LinkList &L)
{
LNode *P = L->next,*q;
if(p==NULL)
return;
while(p->next !=NULL)
{
q = p->next; //q指向*p的后继结点
if(p->data == q->data) //找到重复的结点
{
p->next = q->next; //释放*q结点
free(q);
}
else
p = p->next;
}
}
2.3.15 两个递增的单链表归并为一个递减的单链表，并要求利用原来两个单链表的结点存放归并后的单链表
/*
合并时，均从第一个结点起开始比较，将较小的结点链入链表中，同时后移工作指针。该问题要求结果链表按元素值递减次序排列，故新链表的建立应该采用头插法。比较结束后，可能会有一个链表非空，此时用头插法将剩下的结点依次插入新链表中即可。
*/
void MergeList(LinkList &La,LinkList &Lb)
{
LNode *r,*pa = La->next, *pb = Lb->next;
La->next = NULL; //La作为结构链表的头指针，先将结果链表初始化为空
while(pa && pb) //当两链表不空时，循环
{
if(pa->data next)
{
r = pa->next;
pa->next = La->next;
La->next = pa;
pa = r;
}
else
{
r = pb->next; //r暂存pb的后继结点指针
pb->next = La->next;
La->next = pb; //将pb结点链于结果表中，同时逆置
pb =r; //恢复pb为当前待比较结点
}
if(pa)
pb = pa; //通常情况下会剩一个链表非空，处理剩余的部分。
while(pb) //处理剩下的一个非空链表
{
r = pb->next; //依次插入到La中
pb->next = La->next;
La->next = pb;
pb =r;
}
free(Lb);
}
}
2.3.16 两个带头结点并且递增的单链表A和B中产生单链表C，C中包含它们的公共元素，要求不破坏A、B的结点
/*
表A、B都有序，可从第一个元素起依次比较A、B两表的元素，若元素值不等，则值小的指针往后移。若元素值相等，则创建一个值等于两结点的元素值的新结点，使用尾插法插入到新的链表中，并将两个原表指针后移一位，直到其中一个链表遍历到表尾。
*/
void Get_Common(LinkList A,LinkList B)
{
LNode *p = A->next,*q = B->next. *r,*s;
LinkList C = (LinkList)malloc(sizeof(LNode)); //建立表C
r = C; //r始终指向C的尾结点
while(p!=NULL && q!=NULL) //循环跳出条件
{
if(p->data < q->data)
p = p->next; //若A的当前元素较小，后移指针
else if(p->data > q->data)
q = q->next; //若B的当前元素较小，后移指针
else //找到公共元素结点
{
s = (LNode*)malloc(sizeof(LNode));
s->data = p->data; //复制产生结点*s
r-next = s; //将*s链接到C上
r = s;
p = p->next; //表A和B继续向后扫描
q = q->next;
}
r ->next = NULL; //置C尾结点指针为空
}
}
2.3.17 两个递增的单链表A和B，将A和B的公共元素存放于A链表中
/*
采用归并的思想，设置两个工作指针pa和pb,对两个链表进行归并扫描，只有同时出现在两集合中的元素才链接到结果表中且仅保留一个，其他的结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点。时间复杂度为O(len1+len2),空间复杂度为O(1).
*/
LinkList Union(LinkList &la,LinkList &lb)
{
pa = la->next;
pb = lb->next;
pc = la; //结果表中当前合并结点的前驱指针
while(pa && pb)
{
if(pa->data == pb->data) //交集并入结果表中
{
pc->next = pa; //A中结点链表到结果表
pc =pa;
pa = pa->next;
u = pb;
pb = pb->next;
free(u);
}
else if(pa->data < pb->data) //若A中当前结点值小于B中当前结点值
{
u=pa;
pa = pa->next;
free(u);
}
else //若B中当前结点值小于A中当前结点值
{
u = pb;
pb = pb->next;
free(u); //释放B中剩余结点
}
}//while结束
while(pa) //B已遍历完，A未完
{
u = pa;
pa = pa->next;
free(u); //释放A中剩余结点
}
while(pb){ //A已遍历完，B未完
u = pb;
pb = pb->next;
free(u); //释放B中剩余结点
}
pc->next = NULL; //置结果链表尾指针为NULL
free(lb); //释放B表的头结点
return la;
}
2.3.18 判断单链表B中的序列是否是单链表A中序列的连续子序列
/*
操作从两个链表的第一个结点开始，若对应数据相等，则后移指针;若对应数据不等，则A链表从上次开始比较结点的后继开始，B链表仍从第一个结点开始比较，直到B链表表到尾表示匹配成功。A链表到尾而B链表未到尾表示失败。操作中应记住A链表每次的开始结点，以便下次匹配时好从其后继开始。
*/
int Pattern(LinkList A,LinkList B)
{
LNode *p = A; //p为A链表的工作指针，本题假定A和B均为结点
LNode *pre =p; //pre记住每趟比较中A链表的开始结点
LNode *q = B; //q是B链表的工作指针
while(p && q)
{
if(p->data == q->data) //结点值相同
{
p = p->next;
q = q->next;
}
else
{
pre = pre->next;
p = pre; //A链表新的开始比较结点
q = B; //q从链表第一个结点开始
}
if(q==NULL) //B已经比较结束
return 1; //说明B是A的子列
else
return 0; //B不是A的子列
}
}
2.3.19 判断带头结点的循环双链表是否对称
/*
让p从左到右扫描，q从右向左扫描，直到它们指向同一结点(p==q,当循环双链表中结点个数为奇数时)或相邻(p->next=q 或q->prior =p,当循环双链表中结点个数为偶数时)为止若它们所指结点值相同，则继续进行下去，否则返回0。若比较全部相等，则返回1。
*/
int Symmetry(DLinkList L)
{
DNode *p = L->next,*q = L->prior; //两头工作指针
while(p!=q && p->next!=q)
{
if(p->data == q->data) //所指结点值相同则继续比较
{
p = p->next;
q = q->prior;
}
else //否则，返回0
return 0;
return 1; //比较结束后返回1
}
}
2.3.20 将循环单链表h2链接到h1之后，要求链接后的链表仍保持循环链表形式
/*
先找到两个链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，再使之成为循环的。
*/
LinkList Link(LinkList &h1,LinkList &h2)
{
LNode *p,*q; //分别指向两个链表的尾结点
p = h1;
while(p->next != h1) //寻找h1的尾结点
p = p->next;
q = h2;
while(q->next != h2) //寻找h2的尾结点
q = q->next;
p->next = h2; //将h2链接到h1之后
q->next = h1; //令h2的尾结点指向h1
return h1;
}
2.3.21 带头结点的循环单链表，结点值均为正整数，反复找出结点值最小的结点输出并删除，直到单链表为空，再删除表头结点。
/*
对于循环单链表L，在不空时循环，每循环一次查找一个最小结点(由minp指向最小值结点，minpre指向其前驱结点)并删除它。最后释放头结点。
*/
void Del_All(LinkList &L)
{
LNode *p,*pre,*minp,*minpre;
while(L->next != L)
{
P = l->next; pre = L; //p为工作指针，pre指向其前驱
min = p;
minpre = pre; //minp指向最小值结点
while(p != L) //循环一遍，查找最小值结点
{
if(p->data < minp->data)
{
minp = p; //找到值更小的结点
minpre = pre;
}
pre = p; //=查找下一个结点
p = p->next;
}
prinf("%d",minp->data);
minpre->next = minp->next; //将最小值结点从表中"断开"
free(minp);
}
free(L); //释放头结点
}
(2.4) 单链表真题
2.4.1 查找链表倒数第 k 个位置上的结点 (k为正整数)。若查找成功，输出该结点的data域的值，并返回1;否则只返回0。
/*
描述算法的基本思想:定义两个指针变量p和q,初始时均指向头结点的下一个结点(链表的第一个结点),p指针沿链表移动;当p指针移动到第k个结点时，q指针开始于p指针同步移动;当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。
描述算法的详细实现步骤:
① count=0, p和q指向链表表头结点的下一个结点。
② 若p为空，转⑤
③ 若count等于k,则q指向下一个结点;否则，count = count +1。
④ p指向下一个结点，转②
⑤ 若count等于k,则查找成功，输出该结点的data域的值，返回1;否则，说明超过了线性表的长度,查找长度,返回0。
⑥ 算法结束。
程序设计语言描述算法:
*/
typedef struct LNode
{
int data;
struct LNode *link;
}LNode,*LinkList
int Search_k(LinkList list,int k)
{
LNode*p = list->link,*q = list->link; //指针p、q指示第一个结点
int count =0;
while(p!=NULL) //遍历链表直到第一个结点
{
if(count < k) count++; //计数，若countlink;
p = p->link; //之后让p、q同步移动
}//while
if(count < k) //查找失败返回0
return 0; //否则打印并返回1
else
{
printf("%d",q->data);
}
}
2.4.2 带头结点的单链表保存保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，找出由 str1 和 str2所指向两个链表共同后缀的起始位置。
/*
描述算法的基本设计思想
采用程序设计语言描述算法
说明时间复杂度为O(len1+len2)
*/
typedef struct Node
{
char data;
struct Node *next;
}SNode;
/*求链表长度的函数*/
int listlen(SNode *head)
{
int len = 0;
while(head->next != NULL)
{
len++;
head = head->next;
}
return len;
}
/*找出共同后缀的起始地址*/
SNode* find_addr(SNode *str1,SNode *str2)
{
int m,n;
SNode *p,*q;
m = listlen(str1); //求str1的长度
n = listen(str2); //求str2的长度
for(p = str1; m>n;m--) //若m>n，使q指向链表中的第 n-m+1 个结点
p = p->next;
for(q = str2; mnext!= NULL && p->next!= q->next) //将指针p和q同步向后移动
{
p = p->next;
q = q->next;
}//while
return p->next; //返回共同后缀的起始地址
}
2.4.3 带头结点的单链表保存 m 个整数，且 |data|data>0 ? p->link->data: -p->link->data;
if(*(q+m)==0)
{
*(q+m)=1;
p = p->link;
}
else
{
r = p->link;
p->link = r->link;
free(r);
}
}
free(q);
}
三、栈和队列
(3.1) 栈
3.1.1 单链表头指针为L，data域为字符型。判断链表的全部 n 个字符是否中心对称。例如 xyx 是中心对称。
/*
让链的前一半元素依次进栈，在处理链表的最后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两个元素比较，若相等，则将链表中的下一个元素与栈中弹出的元素比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论;否则，当链表中的一个元素与弹出元素不等时，结论为非中心对称。
*/
int dc(LinkList L,int n)
{
int i;
char s[n/2]; //s字符栈
p = L->next; //p是链表的工作指针，指向待处理的当前元素
for(i=0;idata;
p = p->next;
}
i--; //恢复最后的i值
if(n%2 == 1) //若n是奇数，后移过中心结点
p = p->next;
while(p!=NULL && s[i]==p->data) //检测是否中心对称
{
i--; //i充当栈顶指针
p = p->next;
}
if(i==-1) //栈为空栈
return i; //链表中心对称
else
return 0; //链表不中心对称
}
(3.2) 队列
3.2.1 循环队列设置一个标志域tag，并以 tag 的值为 0 或 1 来区分队头指针 front 和 队尾指针 rear 相同时的队列状态是 " 空" 还是 “满”,试编写此结构相应的入队和出队算法。
/*
进队时置tag为1,出队时置tag为0。置tag =0、front =rear =0,这样队列的4要素如下:
队空条件: Q.front == Q.rear且Q.tag ==0
队满条件: Q.front == Q.rear且Q.tag ==1
进队操作: Q.data[Q.rear] =x; Q.rear = (Q.rear +1)% MaxSize; Q.tag =1
出队操作: x = Q.data[Q.front]; Q.front = (Q.front+1) % MaxSize; Q.tag =0
*/
/*
设"tag"法循环入队算法
*/
int EnQueue1(SqQueue &Q,int x)
{
if(Q.front==Q.rear && Q.tag==1)
return 0; //两个条件都满足时则队满
Q.data[Q.rear] = x;
Q.rear = (Q.rear +1) % MaxSize;
Q.tag = 0; //可能队满
return 1;
}
/*
设"tag"法循环出队算法
*/
int DeQueue1(SeQueue &Q,int x)
{
if(Q.front==Q.rear && Q.tag == 0)
return 0; //两个条件都满足时则队空
x = Q.data[Q.front];
Q.front = (Q.front +1) % MaxSize;
Q.tag = 0; //可能队空
return 1;
}
3.2.2 Q是一个队列，S是一个空栈，实现将队列中的元素逆置的算法。
/*
让队列中的元素逐个出队列,入栈;
全部入栈后再逐个出栈,入队列。
*/
void Inverser(Stack S,Queue Q)
{
while(!QueueEmpty(Q))
{
x = DeQueue(Q); //栈中全部元素依次出队
Push(S,x); //元素依次入栈
}
while(!StackEmpty(S))
{
Pop(S,x); //栈中全部元素依次出栈
EnQueue(Q,x); //再入队
}
}
3.2.3 利用两个栈 S1、S2 来模拟一个队列，已知栈的4个运算来实现该队列的 3 个运算。
/*
4个运算定义如下:
Push(S,x);
pop(S,x);
StackEmpty(S);
StackOverflow(S);
队列的3个运算分别是 Enqueue、Dequeue、QueueEmpty
*/
//进队算法
int EnQueue(Stack &S1,Stack &S2,int e)
{
if(!StackOverflow(S1))
{
Push(S1,e);
return 1;
}
if(StackOverflow(S1) && !StackEmpty(S2))
{
while(!StackEmpty(S1))
{
Pop(S1,x);
Push(S2,x);
}
}
Push(S1,e);
return 1;
}
//出队算法
void DeQueue(Stack &S1,Stack &S2,int &x)
{
if(!StackEmpty(S2))
{
Pop(S2,x);
}
else if(StackEmpty(S1))
{
printf("队列为空");
}
else
{
while(!StackEmpty(S1))
{
Pop(S1,x);
Push(S2,x);
}
Pop(S2,x);
}
}
//队列为空
int QueueEmpty(Stack S1,Stack S2)
{
if(StackEmpty(S1) && StackEmpty(S2))
return 1;
else
return 0;
}
(3.3) 栈和队列的应用
3.3.1 判别算法表达式的括号是否配对，以字符"\0"作为算术表达式的结束符。
bool BracketCheck(char *str)
{
InitStack(S); //初始化栈
int i =0;
while(str[i] !='\0')
{
switch(str[i])
{ //左括号入栈
case '(':
Push(S,'(');
break;
case '[':
Push(S,'(');
break;
case '{':
Push(S,'(');
break;
//遇到右括号,检测栈顶
case ')':
Pop(S,e);
if(e!='(')
return false;
break;
case ']':
if(e!='[')
return false;
Pop(S,e);
break;
case '}':
Pop(S,e);
if(e!='{')
return false;
break;
default:
break;
}//switch
}//while
if(!IsEmpty(S))
{
printf("括号不匹配\n");
return false;
}
else
{
printf("括号匹配\n");
return true;
}
}
3.3.2 过江渡船每次只能载 10 辆车过江，过江车辆分为客车类和货车类，上渡船有如下规定：同类车先到先上船;客车先于货车上船，且每上4辆客车，才允许放上 1 辆货;若等待客车不足 4 辆，则以货车代替;若无货车等待，允许客车都上船，试设计一个算法模拟渡口管理。
/*
假设数组q的最大下标为10,,恰好是每次载渡的最大量。假设客车的队列为q1,货车的队列为q2。若q1充足，则每取4个q1元素后再取一个q2元素，直到q的长度为10。若q1不充足，则直接用q2补齐。
*/
Queue q; //过江渡船载渡队列
Queue q1; //客车队列
Queue q2; //货车队列
void manager()
{
int i=0,j=0; //j表示渡船上的总车辆数
while(jrchild; //转向右
push(S,p); //压入栈
p = p->lchild; //再走到最左
}
else{ //否则，弹出结点并访问
pop(S,p); //将结点弹出
visit(p->data); //访问该结点
r = p; //记录最近访问过的结点
p = NULL; //结点访问完后，重置该指针
}
}//else
}//while
}
4.1.2 编写二叉树的自下而上、自右到左的层次遍历算法
/*
一般的二又树层次遍历是自上而下、从左到右，这里的遍历顺序恰好相反。算法思想：利用原有的层次遍历算法，出队的同时将各结点指针入栈在所有结点入栈后再从栈顶开始依次访问即为所求的算法。具体实现如下：
1）把根结点入队列。
2）把一个元素出队列，遍历这个元素
3）依次把这个元素的右孩子、左孩子入队列。
4）若队列不空，则跳到（2），否则结束。
*/
void InvertLevel(BiTree bt){
Stack s;
Queue Q;
if(bt!=NULL)
{
InitStack(s); //栈初始化，栈中存放二叉树结点的指针
InitQueue(Q); //队列初始化，队列中存放二叉树结点的指针
EnQueue(Q,bt);
while(IsEmpty(Q)==false) //从上而下层次遍历
{
DeQueue(Q,p);
Push(s,p); //出队，入栈
if(p->lchild)
EnQueue(Q,p->lchild); //若左子女不空，则入队列
if(p->rchild)
EnQueue(Q,p->rchild); //若右子女不空，则入队列
}
while(IsEmpty(s) == false){
Pop(s,p);
visit(p->data);
} //自下而上、自右到左的层次遍历
}//if结束
}
4.1.3 非递归算法求二叉树的高度
/*
采用层次遍历的算法，设置变量1eve1记录当前结点所在的层数，设置变量last指向当前层的最右结点，每次层次遍历出队时与last 指针比较，若两者相等，则层数加1，并让last指向下一层的最右结点，直到遍历完成。1eve1的值即为二叉树的高度。
*/
int Btdepth(BiTree T)
{
if(!T)
return 0; //树空，高度为0
int front= -1, rear = -1;
int last = 0,level = 0; //last指向下一层第一个结点的位置
BiTree Q[MaxSize]; //设置队列Q，元素是二叉树结点指针且容量足够
Q[++rear] = T; //将根结点入队
BiTree p;
while(front < rear) //队不空，则循环
{
p = Q[++front]; //队列元素出队，即正在访问的结点
if(p->lchild)
Q[++rear] = p->lchild; //左孩子入队
if(p->rchild)
Q[++rear] = p->rchild; //右孩子入队
if(front == last){ //处理该层的最右结点
level++; //层数增1
last = rear; //last指向下层
}
}
return level;
}
/*
求某层的结点个数、每层的结点个数、树的最大宽度等，都采用与此题类似的思想。当然，此题可编写递归算法，其实现如下
*/
int Btdepth2(BiTree T)
{
if(T==NULL)
return 0; //空树，高度为0
ldep = Btdepth(T->lchild); //左子树高度
rdep = Btdepth(T->rchild); //右子树高度
if(ldep > rdep)
return ldep+1; //树的高度为子树最大高度加根节点
else
return rdep+1;
}
4.1.4 二叉树各结点的值互不相同，其先序遍历和中序遍历序列分别存于两个一维数组A[1···n]和B[1···n]中，试编写算法建立该二叉树的二叉链表。
/*
由先序序列和中序序列可以唯一确定一棵二叉树。算法的实现步骤如下：
1) 根据先序序列确定树的根结点。
2) 根据根结点在中序序列中划分出二叉树的左、右子树包含哪些结点，然后根据左、右子树结点在先序序列中的次序确定子树的根结点，即回到步骤1）。
3) 如此重复上述步骤，直到每棵子树仅有一个结点（该子树的根结点）为止。
*/
BiTree PreInCreat(int A[],int B[],int l1,int h1,int l2,int h2)
{
//11,h1为先序的第一和最后一个结点下标，12,h2为中序的第一和最后一个结点下标
//初始调用时,l1=l2=1, h1=h2=n
root = (BiTNode*)malloc(sizeof(BiTNode));
root->data = A[l1];
for(i = l2;B[i]!=root->data;i++);
llen = i - l2;
rlen = h2 - i;
if(llen)
root->lchild = PreInCreat(A,B,l1+1,l1+llen,l2,l2+llen-1);
else
root->lchild = NULL;
return root;
}
4.1.5 二叉树按二叉链表形式存储，写一个判别给定二叉树是否是完全二叉树的算法。
/*
根据完全二叉树的定义，具有n个结点的完全二叉树与满二又树中编号从1～n的结点一一对应。
算法思想：采用层次遍历算法，将所有结点加入队列（包括空结点）。遇到空结点时，查看其后是否有非空结点。若有，则二又树不是完全了叉树。
*/
bool IsComplete(BiTree T)
{
InitQueue(Q);
if(!T)
return 1; //空树为满二叉树
EnQueue(Q,T);
while(!IsEmpty(Q))
{
DeQueue(Q,p);
if(p) //结点非空，将其左、右子树入队列
{
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild);
}
else //结点为空，检查其后是否有非空结点
while(!IsEmpty(Q)){
DeQueue(Q,p);
if(p) //结点非空，则二叉树为非完全二叉树
return 0;
}
}
return 1;
}
4.1.6 二叉树按二叉链表形式存储，计算一棵给定二叉树的所有双分支结点个数。
/*
计算一棵二叉树b中所有双分支结点个数的递归模型f（b）如下:
f(b)=0 若b=NULL
f(b)=f(b->1chi1d) + f(b->rchild) + 1 若*b为双分支结点
f(b)=f(b->1chi1d) + f(b->rchild) 其他情况（*b为单分支结点或叶子结点）
*/
int DsonNodes(BiTree b)
{
if(b==NULL)
return 0;
else if(b->lchild!=NULL && b->rchild!=NULL)
return DsonNodes(b->lchild) + DsonNodes(b->rchild)+1;
else
return DsonNodes(b->lchild) + DsonNodes(b->rchild);
}
4.1.7 二叉树B按二叉链表形式存储，编写一个树B中所有结点的左、右子树进行交换的函数。
/*
采用递归算法实现交换二叉树的左、右子树，首先交换b结点的左孩子的左、右子树，然后交换b结点的右孩子的左、右子树，最后交换b结点的左、右孩子，当结点为空时递归结束（后序遍历的思想）。
*/
void swap(BiTree b)
{
if(b){
swap(b->lchild); //递归地交换左子树
swap(b->rchild); //递归地交换右子树
temp = b->lchild; //交换左、右孩子结点
b->lchild = b->rchild;
b->rchild = temp;
}
}
4.1.8 二叉树按二叉链表形式存储，求先序遍历序列中第 k (1data;
i++; //下一个结点
ch = PreNode(b->lchild,k); //左子树中递归寻找
if(ch !='#') //在左子树中，则返回该值
return ch;
ch = PreNode(b->rchild,k); //在右子树中递归寻找
return ch;
}
4.1.9 二叉树按二叉链表形式存储，对于树中每个元素值为 x 的结点，删去以它为根的子树，并释放相应的空间。
/*
删除以元素值x为根的子树，只要能删除其左、右子树，就可以释放值为x的根结点，因此宜采用后序遍历。
算法思想：删除值为x的结点，意味着应将其父结点的左（右）子女指针置空，用层次遍历易于找到某结点的父结点。
本题要求删除树中每个元素值为x的结点的子树，因此要遍历完整棵二叉树。
*/
void DeleteXTree(BiTree bt) //删除以bt为根的子树
{
if(bt){
DeleteTree(bt->lchild);
DeleteTree(bt->rchild); //删除bt的左子树、右子树
free(bt); //释放被删结点所占的存储空间
}
}
//在二叉树上查找所有以x为元素值的结点，并删除以其为根的子树
void Search(BiTree bt,int x)
{
BiTree Q[]; //Q是存放二叉树结点指针的队列，容量足够大
if(bt){
if(bt->data == x){ //若根结点值为x，则删除整棵树
DeleteXTree(p->lchild);
exit(0);
}
Init Queue(Q);
EnQueue(Q,bt);
while(!IsEmpty(Q)){
DeQueue(Q,p);
if(p->lchild) //若左子女非空
if(p->lchild->data == x){ //左子树符合则删除左子树
DeleteXTree(p->lchild);
p->lchild = NULL;
} //父结点的左子女置空
else
EnQueue(Q,p->lchild); //左子树入队列
if(p->rchild) //若右子女非空
if(p->rchild->data ==x){ //右子女符合则删除右子树
DeleteXTree(p->rchild);
p->rchild = NULL; //父结点的右子女置空
}
else
EnQueue(Q,p->rchild); //右子女入队列
}
}
}
4.1.10 二叉树中查找值为 x 的结点，打印值为 x 的结点的所有祖先，假设值为x的结点不多于一个。
/*
算法思想：采用非递归后序遍历，最后访问根结点，访问到值为x的结点时，栈中所有元素均为该结点的祖先，依次出栈打印即可。因为查找的过程就是后序遍历的过程，因此使用的栈的深度不超过树的深度。
*/
typedef struct{
BiTree t;
int tag; //tag=0表示左子女已被访问，tag=1表示右子女已被访问
}stack;
void Search(BiTree bt,int x)
{
stack s[]; //栈容量足够大
top = 0;
while(bt!=NULL || top>0)
{
while(bt!=NULL && bt->data !=x) //结点入栈
{
s[++top].t = bt;
s[top].tag = 0;
bt = bt->lchild; //沿左分支向下
}
if(bt->data ==x)
{
printf("所查结点的所有祖先结点的值为:\n"); //找到x
for(i=1;idata); //输出祖先值后结束
exit(1);
}
while(top!=0 && s[top].tag==1)
top--; //退栈（空遍历）
if(top!=0)
{
s[top].tag =1;
bt = s[top].t->rchild; //沿右分支向下遍历
}
}//while
}
4.1.11 二叉树中 p 和 q分别为指向该二叉树中任意两个结点的指针，试编写算法找到 p 和 q的最近公共祖先结点 r 。
/*
后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。
本题要找p和q的最近公共祖先结点r，不失一般性，设p在q的左边。
算法思想：采用后序非递归算法，栈中存放二又树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。先将栈复制到另一辅助栈中。继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p和q的最近公共祖先。
*/
typedef struct{
BiTree t;
int tag; //tag=0表示左子女已被访问，tag=1表示右子女已被访问
}stack;
stack s[],s1[]; //栈，容量足够大
BiTree Ancester(BiTree ROOT,BiTNode *p,BiTNode *q){
top = 0;
bt = ROOT;
while(bt!=NULL && bt!=p && bt!=q){ //结点入栈
while(bt != NULL){
S[++top].t = bt;
s[top].tag = 0;
bt= bt->lchild;
} //沿左分支向下
while(top!=0 && s[top].tag ==1){
//假定p在q的左侧，遇到p时，栈中元素均为p的祖先
if(s[top].t ==p){
for(i=1;i0;i--){ //将栈中元素的树结点到s1中去匹配
for(j=top1;j>0;j--)
if(s1[j].t == s[i].t)
return s[i].t; //p和q的最近公共祖先已找到
}
top--; //退栈
}//while
if(top!=0){
s[top].tag = 1;
bt = s[top].t->rchild;
} //沿右分支向下遍历
}//while
return NULL; //p和q无公共祖先
}
4.1.12 二叉树按二叉链表形式存储，试求非空二叉树b的宽度 (即具有结点数最多的那一层的结点个数)。
/*
采用层次遍历的方法求出所有结点的层次，并将所有结点和对应的层次放在一个队列中。然后通过扫描队列求出各层的结点总数，最大的层结点总数即为二又树的宽度。
注意:本题队列中的结点，在出队后仍需要保留在队列中，以便求二又树的宽度，所以设置的队列采用非环形队列，否则在出队后可能被其他结点覆盖，无法再求二又树的宽度。
*/
typedef struct（
BiTree data[MaxSize]; //i保存队列中的结点指针
int level[MaxSize]; //保存data中相同下标结点的层次
int front,rear;
}Qu;
int BTWidth(BiTree b){
BiTree p;
int k,max,i,n;
Qu.front=Qu.rear= -1; //队列为空
Qu.rear++;
Qu.data[Qu.rear]=b; //根结点指针入队
Qu.level[Qu.rear]=1; //根结点层次为1
while(Qu.frontlchild！=NULL){ //左孩子进队列
Qu.rear++;
Qu.data[Qu.rear]=p->lchild;
Qu.level[Qu.rear]=k+1;
}
if(p->rchild！=NULL){ //右孩子进队列
Qu.rear++;
Qu.data [Qu.rear]=p->rchild;
Qu.level[Qu.rear]=k+1;
}
}//while
max=0;i=0; //max保存同一层最多的结点个数
k = 1; //k表示从第一层开始查找
while(ilchild==NULL && bt->rchild==NULL)//叶结点
if(pre==NULL){
head=bt;
pre=bt;
} //处理第一个叶结点
else{
pre->rchild=bt;
pre=bt;
} //将叶结点链入链表
Inorder(bt->rchild); //中序遍历右子树
pre->rchi1d=NULL; //设置链表尾
return head;
}
4.1.15 判断两棵二叉树是否相似的算法，所谓二叉树T1和T2相似，指的是T1和T2都是空的二叉树或都只有一个根节点;或T1的左子树和T2的左子树是相似的，且T1的右子树和T2的右子树是相似的。
/*
本题采用递归的思想求解，若T1和T2都是空树，则相似;若有一个为空另一个不空则必然不相似;否则递归地比较它们的左、右子树是否相似。递归函数的定义如下:
1) 若T1=T2==NULL,则f(T1,T2) =1;
2) 若T1和T2之一为NULL,另一个不为NULL,则f(T1,T2) =0;。
3) 若T1和T2均不为NULL,则f(T1,T2) = f(T1->1child,T2->1child) && f(T1->rchild,T2->rchild);
*/
int similar(BiTree T1,BiTree T2){
//采用递归的算法判断两个二叉树是否相似
int leftS,rightS;
if(T1==NULL && T2==NULL)//两树皆空
return 1;
else if(T1==NULL||T2==NULL）//只有一树为空
return 0;
else{ //递归判断
leftS = similar(T1->lchild,T2->lchild);
rightS = similar(T1->rchild,T2->rchild);
return leftS && rightS;
}
}
4.1.16 写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法。
/*
算法思想：在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点p左、右子女均无，设其中序左线索指向某祖先结点f（p是f右子树中按中序遍历的第一个结点），若f有左子女，则其左子女是结点p在后序下的前驱;若f无左子女，则顺其前驱找双亲的双亲，一直找到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点，则结点p在中序和后序下均无前驱。
*/
BiThrTree InPostPre(BiThrTree t,BiThrTree p){
BiThrTree q;
if(p->rtag == 0) //若p有右子女，则右子女是其后序前驱
q = p->rchild;
else if(p->ltag ==0) //若p只有左子女，左子女是其后序前驱
q = p->lchild;
else if(p->lchild ==NULL)
q = NULL; //p是中序序列第一结点，无后序前驱
else //顺左线索向上找p的祖先，若存在，再找祖先的左子女
{
while(p->ltag ==1 && p->lchild!=NULL)
p = p->lchild;
if(p->ltag ==0)
q = p->lchild; //p结点的祖先的左子女是其后序前驱
else
q = NULL; //仅有单支树（p是叶子），已到根结点，p无后序前驱
}
return q;
}
(4.2) 二叉树的遍历--真题
4.2.1 二叉树按二叉链表形式存储，设计求二叉树T的WPL的算法
/*
(1) 给出算法的基本设计思想
(2) 给出二叉树结点的数据类型定义
(3) C++语言描述算法,关键之处给出注释
*/
/*
考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶结点的深度与权值之积的总和，可以使用先序遍历解决问题。
1）算法的基本设计思想。
基于先序递归遍历的算法思想是用一个static变量记录wpl，把每个结点的深度作为递归函数的一个参数传递。
算法步骤如下：
① 若该结点是叶结点，则变量wpl加上该结点的深度与权值之积。
② 若该结点是非叶结点，则左子树不为空时，对左子树调用递归算法，右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加1。
③最后返回计算出的wpl即可。
PS:当static关键字用于代码块内部的变量的声明时，用于修改变量的存储类型，即从自动变量修改为静态变量，但变量的链接属性和作用域不受影响。用这种方式声明的变量在程序执行之前创建，并在程序的整个执行期间一直存在，而不是每次在代码块开始执行时创建，在代码块执行完毕后销毁。也就是说，它保持局部变量内容的持久。静态局部变量的生存期虽然为整个源程序，但其作用域仍与局部变量相同，即只能在定义该变量的函数内使用该变量。退出该函数后，尽管该变量还继续存在，但不能使用它。
*/
// 二叉树结点的数据类型定义如下:
typedef struct BiTNode{
int weight;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int WPL(BiTree root){
return wpl_PreOrder(root，0);
}
int wpl_Preorder(BiTree root,int deep){
static int wpl=0; //定义一个static变量存储wp1
if(root->lchild==NULL && root->rchild==NULL) //若为叶结点，累积wp1
wpl += deep*root->weight;
if(root->lchild !=NULL) //若左子树不空，对左子树递归遍历
wp1_PreOrder(root->1child,deep+1);
if(root->rchild !=NULL) //若右子树不空，对右子树递归遍历
wp1_PreOrder(root->rchild,deep+1);
return wpl;
4.2.2 将给定的表达式(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出。
/*
题目给定条件：二叉树结点定义如下:
typedef struct node{
char data[10];
struct node *left,*right;
}
(1) 给出算法的基本设计思想
(2) C++语言描述算法,关键之处给出注释
*/
/*
1)算法的基本设计思想:
表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。
表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层（对应根结点）和操作数（对应叶结点）不需要添加括号。
2)算法实现:
将二又树的中序遍历递归算法稍加改造即可得本题的答案。除根结点和叶结点外，遍历到其他结点时在遍历其左子树之前加上左括号，遍历完右子树后加上右括号。
*/
void BtreeToE(BTree *root){
BtreeToExp(root，1); //根的高度为1
}
void BtreeToExp(BTree*root,int deep)
{
if(root==NULL) return; //空结点返回
else if(root->left==NULL && root->right==NULL) //若为叶结点
printf("%s",root->data);
else{
if(deep>1) printf("("); //输出操作数，不加括号
BtreeToExp(root->left,deep+1); //若有子表达式则加1层括号
printf("%s",root->data); //输出操作符
BtreeToExp(root->right,deep+1);
if(deep>1) printf(")"); //若有子表达式则加1层括号
}
}
(4.3) 树和二叉树
4.3.1 编程以孩子兄弟表示法存储的森林的叶子结点数
/*
当森林（树）以孩子兄弟表示法存储时，若结点没有孩(fch=nul1),则它必是叶子，总的叶子结点个数是孩子子树(fch)上的叶子数和兄弟子树(nsib)上的叶结点个数之和。
*/
typedef struct node
{
int data; //数据域
int node *fch,*nsib;//孩子与兄弟域
}*Tree;
int Leaves(Tree t){ //计算以孩子兄弟表示法存储的森林的叶子数
if(t==NULL)
return 0; //树空返回0
if(t->fch==NULL) //若结点无孩子，则该结点必是叶子
return 1+Leaves(t->nsib);//返回叶子结点和其兄弟子树中的叶子结点数
else //孩子子树和兄弟子树中叶子数之和
return Leaves(t->fch)+Leaves(t->nsib);
}
4.3.2 以孩子兄弟链表为存储结构，请设计递归算法求树的深度
/*
由孩子兄弟链表表示的树，求高度的算法思想如下:采用递归算法，若树为空，高度为零;否则,高度为第一子女树高度加1和兄弟子树高度的大者。其非递归算法使用队列,逐层遍历树,取得树的高度。
*/
int Height(CSTree bt){
//递归求以孩子兄弟链表表示的树的深度
int hc,hs;
if(bt==NULL)
return 0;
else{ //否则，高度取子女高度+1和兄弟子树高度的大者
hc = height(bt->firstchild); //第一子女树高
hs = height(bt->nextsibling); //兄弟树高
if(hc+1>hs)
return hc+1;
else
return hs;
}
}
4.3.3 已知一棵树的层次序列及每个结点的度，编写算法构造此时的孩子-兄弟链接
/*
本题与树的层次序列有关。可设立一个辅助数组pointer[]存储新建树的各结点的地址，再根据层次序列与每个结点的度，逐个链接结点。
*/
#define maxNodes 15
void createcSTree_Degree(Csfree&T,int e[],int degree[],int n){
//根据树结点的层次序列e[]和各结点的度degree[]构造树的孩子-兄弟链表
//参数n是树结点个数
CSNode *pointer = new CSNode[maxNodes];//判断pointer[i]为空的语句未写
int i，j，d，k=0;
for(i=0;idata=e[i];
pointer[i]->lchild=pointer[i]->rsibling=NULL;
}
for(i=0;i1child=pointer[k];//建立i与子女k间的链接
for(j=2;jrsibling = pointer[k];
}
}
T = pointer[0];
delete [] pointer;
}
(4.4) 树和二叉树的应用
4.4.1 判断给定的二叉树是否是二叉排序树
/*
对二叉排序树来说，其中序遍历序列为一个递增有序序列。因此，对给定的二叉树进行中序遍历，若始终能保持前一个值比后一个值小，则说明该二又树是一棵二又排序树。
*/
int predt=-32767;//predt为全局变量，保存当前结点中序前驱的值，初值为-无穷。
int JudgeBST(BiTree bt){
int b1,b2;
if(bt==NULL)//空树
return 1;
else{
b1=JudgeBST(bt->1child);//判断左子树是否是二又排序树
if(b1==0 || predt>=bt->data)//以若左子树返回值为0或前驱大于等于当前结点
return 0; //不是二叉排序树
predt=bt->data;//保存当前结点的关键字
b2=JudgeBST(bt->rchild);//判断右子树
return b2; //返回右子树的结果
}
}
4.4.2 设计一个算法，求出指定结点在给定二叉排序树中的层次
/*
算法思想：设二又树采用二又链表存储结构。在二叉排序树中，查找一次就下降一层。因此，查找该结点所用的次数就是该结点在二又排序树中的层次。采用二叉排序树非递归查找算法，用n保存查找层次，每查找一次，n就加1，直到找到相应的结点。
*/
int level(BiTree bt,BSTNode *p){
//本算法计算给定结点在二叉排序树中的层次
int n=0;//统计查找次数
BiTree t=bt;
if(bt!=NULL){
n++;
while(t->data!=p->data){
if(t->data < p->data)//在左子树中查找
t = t->lchild;
else //在右子树中查找
t = t->rchild;
n++;//层次加1
}
}
return n;
}
4.4.2 利用二叉树遍历的思想编写一个判断二叉树是否平衡二叉树的算法
/*
设置二叉树的平衡标记balance，标记返回二又树bt是否为平衡二叉树，若为平衡二叉树，
则返回1，否则返回0：h为二又树bt的高度。采用后序遍历的递归算法：
1）若bt为空，则高度为0，balance=1。
2）若bt仅有根结点，则高度为1，balance=1。
3）否则，对bt的左、右子树执行递归运算，返回左、右子树的高度和平衡标记，bt的高度
为最高子树的高度加1。若左、右子树的高度差大于1，则balance=0;若左、右子树的
高度差小于等于1，且左、右子树都平衡时，balance=1，否则balance=0。
*/
void Judge AVL（BiTree bt，int &balance，int sh）{
//本算法判断一个给定的二叉树是否为平衡二叉树
int b1=0，br=0，hl=0，hr=0;//左、右子树的平衡标记和高度
if（bt==NULL）{//空树，高度为0
h=0;
balance=1;
else if（bt->1child==NULL&6bt->xchild==NULL）{//仅有根结点，则高度为1
h=1;
balance=1;
}
Judge _AVL（bt->1child，bl，h1）;//递归判断左子树
Judge_AVL（bts>rchild，br，hr）;//递归判断右子树
h=（h1>hr？hl:hr）+1;
if（abs（hl-hr）lchild;
return bt->data;
}
int MaxKey(BSTNode *bt){
//求出二叉排序树中最大关键字结点
while(bt->rchild != NULL)
bt = bt->rchild;
return bt->data;
}
4.4.4 设计一个算法,从小到大输出二叉排序树中所有值小于 k 的关键字
/*
由二叉排序树的性质可知，右子树中所有的结点值均大于根结点值，左子树中所有的结点值均小于根结点值。为了从大到小输出，先遍历右子树，再访问根结点，后遍历左子树。
*/
void OutPut(BSTNode *bt, int k)
{
//本算法从大到小输出二叉排序树中所有值不小于k的关键字
if(bt==NULL)
return;
if(bt->rchild != NULL)
OutPut(bt->rchild,k); //递归输出右子树结点
if(bt->data >= k)
printf("%d",bt->data); //只输出大于等于k的结点值
if(bt->lchild !=NULL)
OutPut(bt->lchild,k);//递归输出左子树的结点
}
4.4.5 编写一个递归算法，在一棵有n个结点的、随机建立起来的二又排序树上查找第k (1lchild==NULL){
if(k==1) return;
else return Search_Small(t->rchild,k-1);
}
else{
if(t->lchild->count == k-1)
return t;
if(t->lchild->count > k-1)
return Search_Small(t->lchild,k);
if(t->lchild->count < k-1)
return Search_Small(t->rchild,k-(t->lchild->count+1));
}
五、图
(5.1) 图的存储结构和基本操作
5.1.1 写出从图的邻接表表示转换成邻接矩阵表示的算法
/*
算法的基本思想：设图的顶点分别存储在数组v[n]中。首先初始化邻接矩阵。遍历邻接表，在依次遍历顶点v[i]的边链表时，修改邻接矩阵的第i行的元素值。若链表边结点的值为，则置arcs[i][j]=1。遍历完邻接表时，整个转换过程结束。此算法对于无向图、有向图均适用。
*/
void Convert（ALGraph &G，int arcs[M][N]）{
//此算法将邻接表方式表示的图G转换为邻接矩阵arcs
for(i=0; iv[i]).firstarc; //取出顶点i的第一条出边
while(p!=NULL){ //遍历边链表
arcs[i][p->data]=1;
p=p->nextarc; //取下一条出边
}
}
}
(5.2) 图的遍历
5.2.1 写出从图的邻接表表示转换成邻接矩阵表示的算法
/*
算法的基本思想：设图的顶点分别存储在数组v[n]中。首先初始化邻接矩阵。遍历邻接表，在依次遍历顶点v[i]的边链表时，修改邻接矩阵的第i行的元素值。若链表边结点的值为，则置arcs[i][j]=1。遍历完邻接表时，整个转换过程结束。此算法对于无向图、有向图均适用。
*/
void Convert(ALGraph &G,int arcs[M][N]){
//此算法将邻接表方式表示的图G转换为邻接矩阵arcs
for(i=0; iv[i]).firstarc; //取出顶点i的第一条出边
while(p!=NULL){ //遍历边链表
arcs[i][p->data]=1;
p=p->nextarc; //取下一条出边
}
}
}
(5.2) 图的存储结构和基本操作
5.2.1 试设计一个算法，判断一个无向图G是否为一棵树。若是一棵树，则算法返回true，否则返回false。
/*
一个无向图G是一棵树的条件是，G必须是无回路的连通图或有n-1条边的连通图。这里采用后者作为判断条件。对连通的判定，可用能否遍历全部顶点来实现。可以采用深度优先搜索算法在遍历图的过程中统计可能访问到的顶点个数和边的条数，若一次遍历就能访问到n个顶点和n-1条边，则可断定此图是一棵树。
*/
bool isTree(Graph& G){
for(i=1;i=0;p=NextNeighbor(G,i,p)){
k = p.adjvex;
if(!visited[p] && Exist_Path_DFS(G,p,j))
return 1;
}//for
}//else
return 0;
}
//广度优先遍历算法的实现如下
int visited[MAXSI2E]={0}; //访问标记数组
int Exist_Path_BFS(ALGraph G,int i,int j){
//广度优先判断有同图G中顶点vi到顶点vj是否有路径，是则返回1，否则返回0
InitQueue(Q);
EnQueue(Q,i); //顶点i入队
while(!isEmpty(Q)){ //非空循环
DeQueue(Q,u); //队头顶点出队
visited[u]=1; //置访问标记
for(p=FirstNeighbor(G,i);p;p=NextNeighbor(G,i,p)){
//检查所有邻接点
k=p.adjvex;
if(k==j) //若k==j，则查找成功
return 1;
if(!visited[k]) //否则，顶点k入队
EnQueue(Q,k);
}//for
}//while
return 0;
}
5.2.4 假设图用邻接表表示，设计一个算法，输出从顶点 Vi 到顶点Vj 的所有简单路径。
/*
本题采用基于递归的深度优先遍历算法，从结点u出发，递归深度优先遍历图中结点，若访问到结点v，则输出该搜索路径上的结点。为此，设置一个path数组来存放路径上的结点(初始为空)，d表示路径长度(初始为-1)。
*/
void FindPath(AGraph *G,int u,int v,int path[],int d){
int w,i;
ArcNode *p;
d++; //路径长度增1
path[d]=u; //将当前顶点添加到路径中
visited[u]=1; //置已访问标记
if(u==V) //找到一条路径则输出
print(path[]); //输出路径上的结点
p=G->adjlist[u].firstarc;//p指向v的第一个相邻点
while(p!=NULL){
w=p->adjvex; //若顶点w未访问，递归访问它
if(visited[w]==0)
FindPath(G,w,V,path,d);
p = p->nextarc; //p指向v的下一个相邻点
}
visited[u] = 0; //恢复环境，使该顶点可重新使用
}
六、查找
(6.1) 顺序查找和折半查找
6.1.1 写出折半查找的递归算法。初始调用时，low为1，high为 ST.length。
/*
算法的基本思想：根据查找的起始位置和终止位置，将查找序列一分为二，判断所查找的关键字在哪一部分，然后用新的序列的起始位置和终止位置递归求解。
算法把规模为n的复杂问题经过多次递归调用转化为规模减半的子问题求解。时间复杂度为O(log2n),算法中用到了一个递归工作栈，其规模与递归深度有关，也是O(log2n)。
*/
typedef struct{ //查找表的数据结构
int *elem; //存储空间基址，建表时按实际长度分配，0号留空
int length; //表的长度
}SSTable;
int BinSearchRec(SSTable ST,int key,int low,int high){
//在有序表中递归折半查找其关键字为key的元素，返回其在表中序号
if(low>high)
return 0;
mid=(low+high)/2; //取中间位置
if(key>ST.elem[mid]) //向后半部分查找
Search(ST,key,mid+1,high);
else if(key |