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

．已知一二叉树中结点的左右孩子为left和rightp指向二叉树的某一结点请用C或PASCAL编一个非递归函数postfirst(p)求p所对应子树的第一个后序遍历结点【浙江大学 六(分)】

．已知二叉树T的结点在先根次序下的排列为A[]A[]…A[n]在中根次序下的排列为B[]B[]…B[n]其中A和B是一维数组数组元素的值为T中相应的结点的INFO字段的值并假定二叉树T中结点的INFO字段的值互不相同n>=试解答

()证明由A[n]和B[n]能唯一的确定二叉树T的结构

()给出建造二叉树T的算法要求所建造的二叉树以LLINK/RLINK链接结构表示且该算法是非递归算法

() 分析你所给算法的时间复杂性该过程包括如何确定基本运算如何推导出期望复杂性和最坏复杂性【吉林大学 四 (分) 二】

．已知一具有n个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组IN[n]和POST[n]中(设该二叉树各结点的数据值均不相同)请写一建立该二叉树的二叉链表结构的非递归算法该二叉链表的链结点结构为(lchilddatarchild)其中data为数据域lchild与rhild分别为指向该结点左右孩子的指针域(当孩子结点不存在时相应指针域为空用nil表示)【北京航空航天大学 六 (分)】

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