数据结构考研分类复习真题 第六章 答案 (四)[20]

．

．后序遍历的顺序是左子树右子树根结点因此二叉树最左下的叶子结点是遍历的第一个结点下面的语句段说明了这一过程（设p是二叉树根结点的指针）

if(p!=null)

{while (p>lchild!=null || p>rchild!=null)

{while(p>lchild!=null) p=p>lchild;

if(p>rchild!=null) p=p>rchild; } }

return(p); //返回后序序列第一个结点的指针

采用前序和后序两个序列来判断二叉树上结点n必定是结点n的祖先

在前序序列中某结点的祖先都排在其前若结点n是n的祖先则n必定在n之前而在后序序列中某结点的祖先排在其后即若结点n是n的祖先则n必在n之后根据这条规则来判断若结点n在前序序列中在n之前在后序序列中又在n之后则它必是结点n的祖先

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