.有一个单链表L（至少有一个结点），其头结点指针为head，试给出该单链表的类C语言描述，并编写一个算法将

Question

五．应用题
1. 设一棵二叉树的先序、中序遍历序列分别是：ABDFCEGH 、BFDAGEHC，
（1）画出这棵二叉树；
（2）写这棵二叉树的后序遍历；
2. 有序表r的类型定义：
#define MAXSIZE 100 /*有序表中元素的最大个数*/
typedef struct list
{ KeyType key;
InfoType OtherInfo;
}RecordType;
typedef struct {
RecordType r[MAXSIZE+1]; /* 0位空置不用*/
int length; /*有序表中元素的实际个数*/
}SeqTable;
下列算法利用二分查找方法在有序表t中插入元素x，并保持表t的有序性。请在空缺处填入合适的语句，使其成为一个完整的算法。
void BinInsert (SeqTable t, RecordType x)
{ low = 1；
high =t.length;
while ( )
{ mid = ;
if (x.key<t.r[mid].key) high=mid-1;
else ;
}
for (i = t.length; ; i--)
t.r[i+1] = t.r[i];
;
n++;
}
3.有一个单链表L（至少有一个结点），其头结点指针为head，试给出该单链表的类C语言描述，并编写一个算法将其逆置，即将最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点。
要正确标准答案，我考试用的

Answer 1

楼主你好，这几个问题我来回答你吧，这些都是数据结构里面的基本问题，难度并不太大，可能你没有理解清楚，授人鱼不如授之以渔，除了解答，我还说说解决这些问题的思路，希望你有所启发和感悟。

第1题

碰到这些问题，什么是先序呢？就是先访问根结点，在访问左子树，再访问右子树。中序就是先访问左子树，再访问根节点，再访问右子树。后序不用我说聪明的楼主应该知道了吧。那么根据这个规律，我们可以得出，先序遍历定根结点，中序分左右子树的规律。这个结论有些抽象，下面我们根据这个题目详细说。

先序的第一个是A，那么我们去看中序遍历A的位置，在第4个，这个时候我们就可以得出根节点一定是A，并且A的左子树有BFD，右子树有GEHC，那么到底是什么顺序呢？不急我们一个个看，先看左子树。这个时候我们再回过头去看先序遍历，A的下一个是B，我们在中序遍历中找B，是第一个，那么我们可以肯定的是B一定没有左子树了，B的右子树一定是DF，在根据先序中的顺序可以肯定整棵树的左边如下：
A
/ \
B
\
D
/
F
根据同样的方法可以确定右子树，这个就留给你自己做练习啦。呵呵第一题搞定。

第2题

这个问题的本质其实就是考察2分法是否掌握了。
很明显while( )循环中的条件肯定是low<=high，只要他们没有交错就要继续查找下去。接下来mid=(low+high)/2，这是显然的。下面for循环中的条件当然是x>=t.r[i]，这从i--可以看出来是每次从链表位开始依次后移一个位置以便插入x。最后for循环体中有一个空，这个就是把x插入进去，很显然是t.r[i]=x;那么这道题也结束啦。

第3题

有了第2题的基础，我不准备给你写完整的算法，我只说说思路咯。思路是，要完成逆转，你可以新建一个链表，然后对于原来的链表尾开始，依次插进新的链表中，当然啦，是头插法了，而第2题中你已经学会了倒过来查找链表，那么这道题是不是也迎刃而解了呢？

最后希望你进步哦~

Answer 2

楼主要答案吗，这是标准答案，原理都在数据结构课本上，就不解释了：
第一题答案：
A
/ \
B C
\ /
D E
/ / \
F G H
后序遍历：FDBGHECA

第二题答案：
void BinInsert (SeqTable t, RecordType x)
{ low = 1；
high =t.length;
while ( low<=high )
{ mid = (low+high)/2;
if (x.key<t.r[mid].key) high=mid-1;
else low=mid+1;
}
for (i = t.length;i>=high; i--)
t.r[i+1] = t.r[i];
t.r[i]=x;
n++;
}
第三题答案：（利用原来的链表空间）
int tackal(linklist &L)
{
linknode *head=L,*p=head->next->next,*q=p;
head->next=NULL;
while(q->next)
{q=q->next;
p->next=head->next;
head->next=p;
p=q;
}
return 0;
}本回答被提问者采纳