数据结构考研分类复习真题 第六章 答案 (五)[21]

TYPE bitreptr=^binode;

binode=RECORD data:ElemType; lchildrchlid:bitreptr END;

PROC PreOrder(bt:bitreptr); //非递归前序遍列二叉树

VAR S:ARRAY[max] OF bitreptr; //max是栈容量足够大

inits(S);//栈初始化

WHILE (bt<>NIL) OR (NOT empty(S)) DO

[WHILE (bt<>NIL )DO

[write(bt↑data); push(Sbt>rchild); bt:=bt↑lchild;]//访问结点右子女进栈

WHILE (NOT empty(S) AND top(S)=NIL) bt:=pop(S);// 退栈

IF NOT empty(S) THEN bt:=pop(S);

] ENDP;

[算法讨论]若不要求使用top(S)以上算法还可简化

[题目分析]二叉树采取顺序结构存储是按完全二叉树格式存储的对非完全二叉树要补上虚结点由于不是完全二叉树在顺序结构存储中对叶子结点的判定是根据其左右子女为叶子和双亲结点下标间的关系满足完全二叉树的性质

int Leaves(int h) //求深度为h以顺序结构存储的二叉树的叶子结点数

{int BT[]; int len=h count=; //BT是二叉树结点值一维数组容量为h

for (i=;i<=len;i++) //数组元素从下标开始存放

if (BT[i]!=) //假定二叉树结点值是整数虚结点用填充

if(i*)>len) count++; //第i个结点没子女肯定是叶子

else if(BT[*i]== && *i+<=len && BT[*i+]==) count++; //无左右子女的结点是叶子

return (count)

} //结束Leaves

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