更多"[说明] 二叉树的二叉链表存储结构描述如下：lypedef stru"的相关试题:
[简答题][说明]
二叉树的二叉链表存储结构描述如下：
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
[填空题]一棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有_________个。
[单项选择]
一个具有m 个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left 和right 表示)中的空指针总数必定为 (57) 个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p 的左孩子指针为空，则将该左指针改为指向p 在中序(先序、后序) 遍历序列的前驱结点;若 p 的右孩子指针为空，则将该右指针改为指向p 在中序(先序、后序)遍历序列的后继结点。假设指针s 指向中序(先序、后序)线索二叉树中的某结点，则 (58)。
（57）处填（）。
A. m+2
B. m+1
C. m
D. m-1
[单项选择]
一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为 (57) 个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点，则 (58) 。
（57）处填（）。
A. m+2
B. m+1
C. m
D. m-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) ;
}
}
}
[简答题][说明]
二叉树的二叉链表存储结构描述如下：
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) ;
[简答题]要求二叉树按二叉链表形式存储，并且：
(1)写一个建立二叉树的算法。
(2)写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。
[简答题]设有一棵二叉树以二叉链表作为存储结构，结点结构为lchild|data|rchild，其中data域中存放一个字符，设计一个算法按前根遍历顺序仅打印出data域为数字的字符（即’0’＜=data＜=’9’）。
[多项选择]假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上个结点的值。
[填空题][说明]
已知一棵二叉树用二叉链表存储，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--;
