设计算法返回二叉树T的先序序列的最后一个结点的指针 要求采用非递归形式 且不许用栈。【合肥工业
递归,结点,合肥
已帮助 人
设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式，且不许用栈。【合肥工业大学1999五、2(8分)】
请帮忙给出正确答案和分析，谢谢！
-
正确答案：二叉树先序序列最后一个结点的特征是：从根开始的任何结点若有右子树则是右子树中最右下的叶子结点；若无右子树仅有左子树则是左子树最右下的叶子结点。核心语句段如下： while(p) ／／设p是二叉树根结点的指针 f(p->rchild)p=p一>rchild； ／／若右子树不空沿右子树向下 else if(p一>1child)p=p一>lchild； ／／右子树空左子树不空沿左子树向下 else return(p)； ／／p即为所求
二叉树先序序列最后一个结点的特征是：从根开始的任何结点,若有右子树,则是右子树中最右下的叶子结点；若无右子树,仅有左子树,则是左子树最右下的叶子结点。核心语句段如下：while(p)／／设p是二叉树根结点的指针f(p->rchild)p=p一>rchild；／／若右子树不空,沿右子树向下elseif(p一>1child)p=p一>lchild；／／右子树空,左子树不空,沿左子树向下elsereturn(p)；／／p即为所求