设二叉树以二叉链表为存储结构，编写一个后序遍历二叉树的非递归算法（要求先用文字写出实现的基本

归算法。要求定义所用结构。设栈已经定义：inits(S)，empty(S)，push(S，P)，pop(S)，top(S)分别为栈初始化，判栈空，入栈，出栈，看栈顶等操作。【北京工业大学1997二、1(10分)】

”。由“严格二叉树”的前序序列和后序序列可以唯一确定该二叉树。设“严格二叉树”BT的前序遍历序列为：ABDECFHIGJKLM，后序遍历序列为：DEBHIFJLMKGCA (1)试画出该二叉树；(6分) (2)写出根据这种二叉树的前序序列和后序序列确定该二叉树的递归算法。(9分)

Tree(Bitree t)，判断二叉树是否为正则二叉树。【北京理工大学2005四、2(5分)】

十(15分)】

交换。【东北大学1996五(14分)】

结点的左、右子树相互交换。【福州大学1998四、2(10分)】

的地址。【东北大学1999四(1 3分)】

(c)中序序列和后序序列相同。(2)已知非空二叉树的结点结构为(1child，data，rchild)，设计算法：从右向左依次将所有叶子的数据值放到a向量(假定向量的空间大干叶子的总个数)中。【厦门大学2005二(1 5分)】

1chi ld， rchi 1d：bitrept．r END; 编写一个递归算法，利用叶结点中空的右链指针域rchild，将所有叶结点自左至右链接成一个单链表，算法返回最左叶结点的地址(链头)。【清华大学1997三(10分)】