数据结构1800例题与答案之树和二叉树(4)

ElemType data; BinTreeNode *leftchild,*rightchild; } 现采用输入广义表表示建立二叉树。具体规定如下： （1）树的根结点作为由子树构成的表的表名放在表的 最前面；

（2）每个结点的左子树和右子树用逗号隔开。若仅有 右子树没有左子树，逗号不能省略。

（3）在整个广义表输入的结尾加上一个特殊的符号 （例如“#”）表示输入结束。

例如，对于如右图所示的二叉树，其广义表表示为A（B（D，E（G）），C（，F））。 此算法的基本思路是：依次从保存广义表的字符串ls中输入每个字符。若遇到的是字母（假设以字母作为结点的值），则表示是结点的值，应为它建立一个新的结点，并把该结点作为左子女（当k=1）或右子女（当k=2）链接到其双亲结点上。若遇到的是左括号“（”，则表明子表的开始，将k置为1；若遇到的是右括号“）”，则表明子表结束。若遇到的是逗号“，”，则表示以左子女为根的子树处理完毕，接着处理以右子女为根的子树，将K置为2。在算法中使用了一个栈s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。相关的栈操作如下：

MakeEmpty(s) 置空栈 Push(s,p) 元素p入栈

Pop(s) 退栈 Top(s) 存取栈顶元素的函数

下面给出了建立二叉树的算法，其中有5个语句缺失，请阅读此算法并把缺失的语句补上。（每空3分）

void CreatBinTree(BinTreeNode *&BT,char ls){

Stacks; MakeEmpty(s); BT=NULL; //置空二叉树 BinTreeNode *p;

int k; istream ins(ls)； //把串ls定义为输入字符串流对象ins ; char ch; ins>>ch; //从ins顺序读入一个字符

while (ch != ‘#’){ //逐个字符处理，直到遇到‘#’为止 switch(ch){

case ‘(’: (1)___；k=1; break; case ‘)’: pop(s); break; case’,’ : (2)___； break; default :p=new BinTreeNode; (3)____;p->leftChild=NULL;p->rightChild=NULL;

if(BT==NULL) (4)___；else if (k==1) top(s)->leftChild=p;

else top(s)->rightChild=p;

}

(5)____; } } 【清华大学 2001 六、 (15分)】

67. 判断带头结点的双向循环链表L是否对称相等的算法如下所示，请在划线处填上正确的语句

FUNCTION equal(l:pointer) :boolean; VAR p,q:pointer; result: Boolean;

BEGIN result =true ; p:= l^.link; q:=l^.pre ; WHILE (p<>q) AND ((1)_______)DO

IF p^.data=q^.data THEN BEGIN (2)___; (3)____; END； ELSE result=false ; return(result);

END; 【华南师范大学 2000年 五、1 ( 9分)】

68．下列是先序遍历二叉树的非递归子程序，请阅读子程序（C语言与PASCAL语言过程功

能完全相同，任选其一），填充空格，使其成为完整的算法。

C语言函数： PASCAL语言过程 void example(b) PROCEDURE example(b:btree); btree *b; VAR stack:ARRAY[1..20] OF btree; { btree *stack[20], *p； top:integer; p:btree; int top; BEGIN if (b!=null) IF b<>NIL THEN { top=1; stack[top]=b; BEGIN top:=1; while (top>0) stack[top]:=b; { p=stack[top]; top--; WHILE top>0 DO printf(“%d”,p->data); BEGIN if (p->rchild!=null) p:=stack[top];top:=top-1; {(1)___; (2)___; write(p^.data); } IF p^.rchild<>NIL if (p->lchild!=null) THEN BEGIN (3)___; (4)__; (1)__;(2)_; }}}} END; IF p^,lchild<>NIL THEN BEGIN (3)__; 4)__; END END END END; 【同济大学 2001 三、 (10分)】

69．下述是一个由二叉树的前序序列和中序序列构造该二叉树的算法，其中，数组A[1..n]存放前序序列，数组B[1..n]存放中序序列，s为根结点指针，i,j为树s的前序序列在A[1..n]中的开始位置和结束位置，x,y为树s的中序序列在B[1..n]中的开始位置和结束位置。所生成的二叉树采用二叉链表存储结构，其结点的形式为（lchild,data,rchild）。请在算法的空框中填入适当语句，使其成为一个完整的算法。

PROCEDURE creatBT(i,j,x,y: integer; VAR s: link); VAR k,L: integer; BEGIN s:= NIL; IF(1)__THEN

BEGIN new (s); s^.data:=a[i]; k:=x; WHILE(2)_______DO k:=k+1; L:= (3)____;

IF k=x THEN s^.lchild:=NIL; ELSE(4)_______; IF k=y THEN s^.rchild:=NIL; ELSE(5)_______； END

END; 【西安交通大学 1996 五、1 (9分)】

70．已知中序遍历bt所指二叉树算法如下，s为存储二叉树结点指针的工作栈，请在划线

处填入一条所缺语句。

PROC inorder (bt:bitreptr); inistack(s); (1)_______; WHILE NOT empty(s) DO

[WHILE gettop(s)<>NIL DO push(s,gettop(s)↑.lchild); (2)_______;

IF NOT empty(s) THEN [visit (gettop(s)^); p:=pop(s); (3)_______ ] ]

ENDP;{inorder} 【北京轻工业学院 1999 一、 (9分)】

71．以下程序是二叉链表树中序遍历的非递归算法，请填空使之完善。二叉树链表的结点类型的定义如下：

typedef struct node /*C语言/

{char data; struct node *lchild,*rchild;}*bitree;

void vst(bitree bt) /*bt为根结点的指针*/ { bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/

while(p || !empty(s)) /*栈s不为空*/ if(p) { push (s,p); (1)___; } /*P入栈*/

else { p=pop(s); printf(“%c”,p->data); (2)____; } /*栈顶元素出栈*/ } 【西南交通大学 2000 一、10】

72．二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。

int depth(bitree bt) /*bt为根结点的指针*/ {int hl,hr;

if (bt==NULL) return((1)___);

hl=depth(bt->lchild); hr=depth(bt->rchild); if((2)___) (3)_____； return(hr+1);

} 【西南交通大学 2000 一、11】

73．n个结点的完全二叉树存储在数组a中，下面为非递归的先序遍历算法。

PROC preorder(a); BEGIN top:=0; t:=1;

WHILE (t<=n) OR (1)__ _DO

BEGIN WHILE t<=n DO BEGIN write(a[t]); top:=top+1; s[top]:=t; t:= (2)_;END;

IF top>0 THEN BEGIN t:=s[top]*2+1; top:= (3)__; END; END;

END; 【中山大学 1998 四、3 （6分）】

74．后序遍历二叉树的非递归算法，bt是二叉树的根，S是一个栈，maxsize是栈的最大容量。

TYPE bitreptr=^bnodetp;

bnodetp=RECORD data:datatype; lchild,rchild:bitreptr END; TYPE stacktyp=RECORD data:ARRAY[1..maxsize] OF bitreptr；top：0..maxsize；END； PROCEDURE posterorder（bt：bitreptr）； BEGIN S.top:=0；p:=bt； …… 此处隐藏：4939字，全部文档内容请下载后查看。喜欢就下载吧 ……