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

数据结构考研分类复习真题 第六章 答案 (四)[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 的祖先