数据结构考研分类复习真题 第六章 树和二叉树 (三)[9]

．下面的类PASCAL语言递归算法的功能是判断一棵二叉树(采用二叉链表存贮结构)是否为完全二叉树请把空缺的两部分补写完整(提示利用完全二叉树结点序号性质)

TYPE link=^node;

node=RECORD key:keytype; lr:link; END;

VAR all:boolean; n:integer; root:link;

FUNC num(t:link):integer;

BEGIN ()______END;

PROC chk(t:link;m{t 所指结点应有序号}:integer)

BEGIN ()_______END;

BEGIN {建二叉树其根由root指出 }

n:=num(root);{求结点数} all:=true; chk(root);

IF all THEN writeln(该树为完全二叉树！)ELSE writeln (该树非完全二叉树！)

END【北京工业大学 二 (分)】

．将二叉树bt中每一个结点的左右子树互换的C语言算法如下其中ADDQ(Qbt)DELQ(Q)EMPTY(Q)分别为进队出队和判别队列是否为空的函数请填写算法中得空白处完成其功能

typedef struct node

{int data ; struct node *lchild *rchild; }btnode;

void EXCHANGE(btnode *bt)

{btnode *p *q;

if (bt){ADDQ(Qbt);

while(!EMPTY(Q))

{p=DELQ(Q); q=()______; p>rchild=()______; ()______=q;

if(p>lchild) ()______; if(p>rchild) ()______;

}

}

}//【北京科技大学 二(分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []