给定一棵用二叉链表表示的二叉树，其根指针为root,试写出求二叉树结点的数目的算法。

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

阅读以下说明、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).

B．n

C．n+1

D．n+2

A．s指向二叉树的最右下方的结点 B．s指向二叉树最左下方的结点

C．s指向根结点  D．s为NULL

A、n-1

B、n+1

C、n(n-1)/2

D、n(n+1)/2

typedef char DataType;

typedef struct node{

DataType data;

struct node*lchild,*rchild; //左右孩子指针

struct node*parent; //指向双亲的指针

}BinTNode;

typedef BinTNode*BinTree;

若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。

1. 就后继的不同情况，简要叙述实现求后继操作的方法；