[填空题]一棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有_________个。

[填空题]对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中______个用于链接孩子结点。

[单项选择]用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为 ( )
A. n-1
B. n
C. n+1
D. 2n

[填空题]【说明】 下面的程序构造一棵以二叉链表为存储结构的二叉树算法。 【函数】 BTCHINALR *createbt ( BTCHINALR *bt ) { BTCHINALR *q; struct node1 *s [30]; int j,i; char x; printf ( "i,x =" ); scanf ( "%d,%c",&i,&x ); while (i!=0 && x!=’$’) { q = ( BTCHINALR* malloc ( sizeof ( BTCHINALR )); //生成一个结点 (1) ; q-＞1child = 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[1] }

[简答题]【说明】
下面的程序构造一棵以二叉链表为存储结构的二叉树。
【函数】
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];

[填空题][说明]
已知一棵二叉树用二叉链表存储，t指向根结点，p指向树中任一结点。下列算法为输出从t到p之间路径上的结点。
[函数]
#define MaxSize 1000
typedef struct node
TelemType data;
struct node *lchild,*rchild;
BiNode, *BiTree;
void Path(BiTree t， BiNode *p)
BiTree *stack EMaxsize], *stack1 [maxsize], *q;
int tag[Maxsizel, top=0, top1;
q=t;
/*通过前序遍历发现P*/
do while (q!=NULL＆＆q! =p)
/*扫描左孩子，且相应的结点不为p*/
(1) ;
stack [top] =q;
tag [top] =0;
(2) ;

if (top＞0)
if (stack [top]==P) break; /*找到p，栈底到栈顶为t到p*/
if(tag[top]==1) top--;
else q=stack[top];
q=q-＞rchild;
tag [top] =1;


(3) ;
top--; top1=0;
while(top＞0)
q=stack [top]; /*反向打印准备*/
top1++;
(4) ;
top--;

while( (5) ) /*打印栈的内容*/
q=stack1[top1];
printf (q-＞data);
top1--;

[填空题][说明]
已知一棵二叉树用二叉链表存储，t指向根节点，P指向树中任一节点。下列算法为输出从t到P之问路径上的节点。
[C程序]
#define MaxSize 1000
typedef struct node
TelemType data ;
struct node *ichiid，*rchiid；
BiNode，*BiTree；
void Path(BiTree t，BiNode *P)
BiTree *stack[Maxsize]，*stackl[Maxsize],*q；
int tag[Maxsize]，top=0，topl；
q=t；
/*通过先序遍历发现P*/
dowhile(q!=NULL ＆＆q!=p)
/*扫描左孩子，_日．相应的节点不为P*/
(1) ；
stack[top]=q；
tag[top]=0；
(2) ；

if(top＞0)
if(stack[top]=P) break； /*找到P，栈底到栈顶为t到P*/
if(tag[top]==1)top--;
else q=stack[top]；
q=q-＞rchiid;
tag[top]=1;


(3) ；
top--；topl=0；
while(top＞0)
q=stack[top]； /*反向打印准备*/
topl++；
(4) ；
top--;

while( (5) ) /*打印栈的内容*/
q=stackl[topl]j
printf(q-＞data)；
topl--；

[简答题][说明] 二叉树的二叉链表存储结构描述如下： typedef struct BiTNode { datatype data; struct BiTNode *lchild, * rchild; /*左右孩子指针*/ }BiTNode,* BiTree; 对二叉树进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队首取出一个元素，执行下面两个操作： (1) 访问该元素所指结点； (2) 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。 此过程不断进行，当队列为空时，二叉树的层次遍历结束。 下面的函数实现了这一遍历算法，其中Visit(datatype a)函数实现了对结点数据域的访问，数组queue[MAXNODE]用以实现队列的功能，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。 [函数] void LevelOrder(BiTree bt) /*层次遍历二叉树bt*/ { BiTree Queue[MAXNODE]; int front,rear; if(bt= =NULL)return; front=-1; rear=0; queue[rear]= (1) ; while(front (2) ){ (3) ; Visit(queue[front]-＞data); /*访问队首结点的数据域*/ if(queue[front]—＞lchild!：NULL) { rear++; queue[rear]= (4) ; } if(queue[front]-＞rchild! =NULL) { rear++; queue[rear]= (5) ; } } }

[简答题][说明] 二叉树的二叉链表存储结构描述如下： lypedef struct BiTNode { datatype data; street BiTNode *lchiht, *rchild; /*左右孩子指针*/ } BiTNode, *BiTree; 下列函数基于上述存储结构，实现了二叉树的几项基本操作： (1) BiTree Creale(elemtype x, BiTree lbt, BiTree rbt)：建立并返回生成一棵以x为根结点的数据域值，以lbt和rbt为左右子树的二叉树； (2) BiTree InsertL(BiTree bt, elemtype x, BiTree parent)：在二叉树bt中结点parent的左子树插入结点数据元素x； (3) BiTree DeleteL(BiTree bt, BiTree parent)：在二叉树bt中删除结点parent的左子树，删除成功时返回根结点指针，否则返回空指针； (4) frceAll(BiTree p)：释放二叉树全体结点空间。 [函数] BiTree Create(elemtype x, BiTree lbt, BiTree rbt) { BiTree p; if ((p = (BiTNode *)malloc(sizeof(BiTNode)))= =NULL) return NULL; p-＞data=x; p-＞lchild=lbt; p-＞rchild=rbt; (1) ; } BiTree InsertL(BiTree bt, elemtype x,BiTree parent) { BiTree p; if (parent= =NULL) return NULL; if ((p=(BiTNode *)malloc(sizeof(BiTNode)))= =NULL) return NULL; p-＞data=x; p-＞lchild= (2) ; p-＞rchild= (2) ; if(parent-＞lchild= =NULL) (3) ; else{ p-＞lchild= (4) ; par

[简答题][说明]
二叉树的二叉链表存储结构描述如下：
lypedef struct BiTNode
datatype data;
street BiTNode *lchiht, *rchild; /*左右孩子指针*/ BiTNode, *BiTree;
下列函数基于上述存储结构，实现了二叉树的几项基本操作：
(1) BiTree Creale(elemtype x, BiTree lbt, BiTree rbt)：建立并返回生成一棵以x为根结点的数据域值，以lbt和rbt为左右子树的二叉树；
(2) BiTree InsertL(BiTree bt, elemtype x, BiTree parent)：在二叉树bt中结点parent的左子树插入结点数据元素x；
(3) BiTree DeleteL(BiTree bt, BiTree parent)：在二叉树bt中删除结点parent的左子树，删除成功时返回根结点指针，否则返回空指针；
(4) frceAll(BiTree p)：释放二叉树全体结点空间。
[函数]
BiTree Create(elemtype x, BiTree lbt, BiTree rbt) BiTree p;
if ((p = (BiTNode *)malloc(sizeof(BiTNode)))= =NULL) return NULL;
p-＞data=x;
p-＞lchild=lbt;
p-＞rchild=rbt;
(1) ;BiTree InsertL(BiTree bt, elemtype x,BiTree parent)
BiTree p;
if (parent= =NULL) return NULL;
if ((p=(BiTNode *)malloc(sizeof(BiTNode)))= =NULL) return NULL;
p-＞data=x;
p-＞lchild= (2) ;
p-＞rchild= (2) ;
if(parent-＞lchild= =NULL)