题目内容
（请给出正确答案）
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
参考答案
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
网友提供的答案
更多“设二叉树采用二叉链表方式存储，root指向根结点，r所指结点为二叉树中任一给定的结点。则可以通过改写（）算法，求出从根结点到结点r之间的路径。”相关的问题
阅读以下说明、C函数和问题，将解答填入答题纸的对应栏内。
【说明】
二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：
●若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值;
●若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值;
●左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：
typedefstructBiTnode{
intkey_value;/*结点的键值，为非负整数*/
structBiTnode*left,*right;/*结点的左、右子树指针*/
}*BSTree;
函数find_key(root,key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到，则返回空指针。
【函数】
BSTreefind_key(BSTreeroot,intkey)
{
if((1))
returnNULL;
else
if(key==root->key_value)
return(2);
elseif(keykey_value)
return(3);
else
return(4);
}
【问题1】
请将函数find_key中应填入(1)~(4)处的字句写在答题纸的对应栏内。
【问题2】
若某二叉查找树中有n个结点，则查找一个给定关键字时，需要比较的结点个数取决于(5).
[说明] 假设二叉树采用连接存储结构进行存储，root 指向根接点，p 所指结点为任一给定的结点，编写一个求从根结点到p所指结点之间路径的函数。
void path (root, p)
btree * root, * p;
{
Btree *stack[m0], *s;
int tag[m0], top =0, i, find =0;
s =root;
do
{
while (s ! = NULL)
{
stack [top] = s;
tag[top] =0;
((1))
}
if (top ＞0)
{
((2))
if (tag[top] = =1)
{
if((3))
{
for (i=1; i＜ =top; i+ + printf ("%d" ,stack[i]- ＞data);
find=1;
}
else top - -;
}
if((4))
{
p=p- ＞right;
((5))
}
}
} while (find ｜｜ (s! = NULL && top ! =0));
}
阅读下列程序说明和C程序，将应填入程序中(n)处的字句，写在答卷纸的对应栏内。
【程序说明】
本程序先从文件读入各考生的准考证号(设为整型数)及成绩，并将其存放在一棵检索二叉树上，二叉树结点的健值是成绩，每个结点带一链表，链表结点存放取得该成绩的考生的准考证号。然后，程序按中序遍历检索二叉树，从高分到低分输出结果，使每行输出成绩及其取得成绩的考生的准考证号。
【程序】
＃include
typedef struct idnode {
int id;
struct idnode * next;
} IdNode;
typedef struct marknode {
int mark;
IdNode *head;
struct marknode *left, *right;
} MarkNode;
char fname ［ ］="sp07.dat";
main()
{ int id, mark;
MarkNode *root=null;
FILE *fp=fopen(fname,"r");
if(!fp) {
printf("file%s open error.＼n", fname);
exit(0);
}
while (!feop(fp)) {
fscanf(fp,"%d%d", &id, &mark);
btree(&root, id, mark);
}
fclose(fp);
print(root);
}
btree(MarkNod**mpptr, int id, int mark)
{ IdNode *ip;
MarkNode *mp=*mpptr;
if (1) {
if (mark==p->mark) addIdNODE ((2) , id);
else if (mark>mp->mark) btree (&mp->left, id, mark);
else btree(&mp->right, id, mark);
}else
{ mp=(marknode *) malloc(sizeo (marknode));
mp->mark=mark;
mp->left=mp->right=NULL;
(3)
addIdNode(&mp->head, id);
(4) ;
}
}
addIdNode(IdNode **ipp, int id)
{IdNode *ip=*ipp;
if ((5) )addIdNode ((6) ), id;
else{
ip=(IdNode *)malloc(sizeof(IdNode));
sp->id=id;
ip->next=NULL;
(7)
}
}
print(MarkNode *mp)
{ IdNode *ip, *ip0;
if (mp){
print (mp->left);
printf("%6d:＼t",mp->mark);
ip=mp->head;
while(ip){
printf("%6d",ip->id);
ip0=ip;
ip=ip->next;
free(ip0);
}
printf("＼n");printf(mp->right);free(mp);
}
}
void Inorder(BinTree T，void(*Visit)(Datatype x))
{ if(T)
{Inorder(T-＞lchild，Visit); /*遍历左子树*/
Visit(T-＞data)； /*通过函数指针调用它所指的函数来访问结点*/
Inorder(T-＞rchild，Visit)； /*遍历右子树*/
}
}
其中Visit是一个函数指针，它指向形如void f(DdataType x)的函数。因此我们可以将访问结点的操作写在雨数f中，通过调用语句Inorder(root，f)将f的地址传递给Visit，来执行遍历操作。请写一个打印结点的数据的函数，通过调用上述算法来完成中序遍历。
【程序说明】
本程序先从文件读人各考生的准考证号(设为整型数)及成绩，并将其存放在一棵检索二叉树上，二叉树结点的健值是成绩，每个结点带一链表，链表结点存放取得该成绩的考生的准考证号。然后，程序按中序遍历检索二叉树，从高分到低分输出结果，使每行输出成绩及其取得成绩的考生的准考证号。
【程序】
include ＜ stdio. h ＞
typedef struet idnode {
int id;
struct idnode * next;
} ldNode;
typedef struct marknode I
int mark;
ldNode * head;
struct marknode * left, * right;
} MarkNode;
char fname [ ] = "sp07.dat";
main()
{ int id, mark;
MarkNode * root = null;
FILE * fp = fopen(fname," r" );
if(!fp) {
printf("file%s open error, \n" , fname);
exit(0);
}
while (!feop(fp)) {
fscanf(fp," %d%d", &id, &mark);
btree(&root, id, mark);
}
fclose(fp);
print(root);
}
btree(MarkNod * * mpptr, int id, int mark)
{ ldNode * ip;
MarkNode *mp = * mpptr;
if (1) {
if (mark==p-＞mark) addldNODE ((2), id);
else if (mark ＞mp -＞ mark) btree (&top -＞ left, id, mark);
else btree(&mp-＞ right, id, mark);
} else
Imp = (marknode * ) malloc(sizeo (marknode) );
mp -＞ mark = mark;
mp -＞ left =mp -＞ right = NULL;
(3)
addldNode(&mp -＞ head, id);
(4);
}
}
addldNode(ldNode * * ipp, int id)
{ ldNode * ip = * ipp;
if ((5))addldNode ((6)), id;
else {
ip = (ldNode * )malloc(sizeof(ldNode) );
sp - ＞ id = id;
ip -＞ next = NULL;
(7)
}
}
print(MarkNode * rap)
{ ldNode *ip, *ip0;
if (mp) {
print (mp -＞ left);
printf(" %6d: \t" ,mp -＞ mark);
ip = mp -＞ head;
while(ip) {
printf(" %6d" ,ip -＞ id);
ip0 =ip;
ip = ip -＞ next;
free (ip0);
}
printf(" \n" ); printf(mp -＞ right); free(mp);
}
}
警告：系统检测到您的账号存在安全风险
为了保护您的账号安全，请在“简答题”公众号进行验证，点击“官网服务”-“账号验证”后输入验证码“”完成验证，验证成功后方可继续查看答案！
