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

．①二叉树用来表示表达式因为需要保存各子树的值修改二叉树的结点结构为(LchildDataValRchild)其中LchildRchild的意义同前Val用来存放以该结点为根的子树的值值的类型依具体情况而定为了简便起见算法假定所考虑的表达式只有+*/ 四种二目运算且已表示成相应的二叉树算法所计算的表达式值放在根结点的Val域中

PROC Postordereval(t:ptrType)

BEGIN IF (t!=NULL)

BEGIN ()_______; ()_______;

CASE t^data:

+: t^Val:=t^ Lchild^ Val + t^ Rchild ^ Val; BREAK;

: t^Val:=t^ Lchild^ Val t^ Rchild ^ Val; BREAK;

*: t^Val:=t^ Lchild^ Val * t^ Rchild ^ Val; BREAK;

/: t^Val:=t^ Lchild^ Val / t^ Rchild ^ Val; BREAK;

otherwise: ()_____; BREAK;

ENDCASE END

END;

②PROC Delete(x:datatypeA:tree)

BEGIN tempA:= ()_____;

WHILE (tempA^Item!=x) AND (tempA!=NULL) DO

IF (x<tempA^item) BEGIN r:=tempA; tempA:= ()_____; END

ELSE BEGIN r:=tempA;tempA:=tempA^Rchild;END;//tempA为要删结点r为tempA的父亲

IF ()_____ return(x);

IF (tempA^Lchild!=NULL) AND (tempA^rchild!=NULL)

BEGIN t:=tempA; q:=tempA^Rchild;

WHILE (q^Lchild!=NULL) DO BEGIN t:=q; q:=q^Lchild; END;

t^Lchild:= ()_____; //删去q

q^Lchild :=tempA^Lchild; q^Rchild:=tempA^Rchild;

IF (tempA^item< r^item) r^Lchild := ()______ ELSE r^Rchild:=q //用q代替 tempA

END;

ELSE IF(tempA^Lchild!=NULL) IF(tempA^item<r^item) r^Lchild:=tempA^Lchild

ELSE r^Rchild:=tempA^Lchild

ELSE IF(tempA^Rchild!=NULL) IF(tempA^item<r^item) r^Rchild:= ()_____

ELSE r^Lchild:=tempA^Rchild

ELSE //tempA为树叶

IF()_ r^Lchild:=NULL ELSE r^Rchild:=NULL

END; 【中山大学 四 (分)】

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