[简答题]以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。

[简答题]设有一棵二叉树以二叉链表作为存储结构，结点结构为lchild|data|rchild，其中data域中存放一个字符，设计一个算法按前根遍历顺序仅打印出data域为数字的字符（即’0’＜=data＜=’9’）。

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

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

[填空题] 假设以二叉链表作为二叉树的存储结构，其类型定义如下：
typedef struct node{
char data;
struct node*lchild,*rchild; //左右孩子指针
}BinTNode,*BinTree;
阅读下列算法f33，并回答问题：
(1)已知如图所示的二叉树以T为指向根结点的指针，画出执行f33(T)后的二叉树；
(2)简述算法f 33的功能。
void f 33(BinTtee T){
if(T){
f 33(T—＞lchild);
f 33(T—＞rchild);
if((!T—＞lchild)&&L T—＞rchild){
T—＞lchild=T—＞rchild;
T—＞rchild=NULL;
}
}
} （1）

[简答题]二叉链表为存储结构，写出二叉树宽度的算法。所谓宽度，是指二叉树的各层上，具有结点数最多的那一层上的结点总数。

[简答题]

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

[简答题][说明] 二叉树的二叉链表存储结构描述如下： 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

[简答题][说明]
二叉树的二叉链表存储结构描述如下：
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)