數據結構考研分類復習真題 第六章 答案 (四)[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的祖先

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/22641.html