【说明】 下面的程序构造一棵以二叉链表为存储结构的二叉树。 【函数】 BitTree *createbt(BitTree *bt) { BitTree *q; struct node *s[30]; int j,i; char x; printf("i,x="); scant("%d,%c",&i,&x); while(i!=0 && x!=’$’) { q=(BitTree *}malloc(sizeof(BitTree));//生成一个结点 (1) ; q-＞lchild=NULL; q-＞rchild=NULL; (2) ; if ( (3) ) { j=i/2; // j为i的双亲结点 if(i%2==0) (4) ; //i为j的左孩子 else (5) ; //i为j的右孩子} printf("i,x="); scanf("%d,%c",&i,&x); } return s[i]; }
参考答案：
解析：(1)q-＞data=x (2)s[i]=q (3)i!=1
(4)s[j]-＞lchild=q (5)s[j]->rchild=q
[分析]：
本题考查二叉树的构造。
题目要求构造一棵二叉树，而二叉树的性质如下：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第[log2n]+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：
(1)如果i=1，则结点i无双亲，是二叉树的根；如果i＞1，则其双亲是结点[i/2]。
(2)如果2i＞n，则结点i为叶子结点，无左孩子：否则，其左孩子是结点2i。
(3)如果2i+1＞n，则结点i无右孩子；否则，其右孩子是结点2i+1。
下面我们来看程序。程序中声明了一个结点指针数组，用来保存生成的树中结点。用从键盘输入的方式来确定要插入的字符x和此结点在二叉树中的位置i(这个位置是指在完全二叉树中编号的位置)。
第(1)空是在生成一个新结点后的操作，生成了一个新结点后，自然要将从键盘输入的字符x值存放进来，以及修改结点的两个指针域。程序中指针域都赋了空，因此，第(1)空的任务应该是将字符x写进来，因此，此空答案为q-＞data=x。
第(2)空是在对结点完成操作后的操作，根据题目意思，生成的结点应该要保存到数组s中，此数组是一个指针数组，保存结点时，是将结点的地址保存进数组中相应的位置，因此，此空答案为s[il=q。
第(3)空是条件判断语句的条件，结合下面的程序可以知道，此条件语句用来判断当前结点是不是根结点，如果不是，才执行条件语句中的内容。根据上面的分析，如果i=1，则结点i无双亲，是二叉树的根，因此，此空的答案为i!=1。
第(4)空处后面有注释，说明i是j的左孩子结点，这个时候我们应该让j结点的左孩子指针指向结点i，此空就是要实现这一功能。而结点，j被存放在数组s中的第j个位置，因此，此空答案为s[i]-＞lchild=q。
从程序中很容易看出，第(5)空与第(4)空功能相似，只是说i是j的右孩子结点，因此，让j结点的右孩子指针指向结点乙此空答案为s[j]-＞rchild=q。