问答题
已知一棵二叉树,该二叉树中结点的形式为(data,left,right)。其中data域为结点的数据域,且它的数据类型为int;left域和fight域分别给出本结点的左孩子和右孩子的地址,又已知该排序二叉树的根结点地址为root。请设计一个非递归的函数,给出该二叉树的前序遍历序列的最后一个结点的地址,另外要求所使用的额外空间必须为O(1)。【上海交通大学2006】
【正确答案】正确答案:前序遍历的最后一个结点是最右边的叶子结点。 核心语句是: p=root; while(p) if(p一>right)p=p一>right; else if(p一>left)p=p一>left; else return P;
【答案解析】