【正确答案】正确答案：本题到22题是在以二叉链表存储的二叉树上找某结点的所有祖先，某两个结点的最近公共祖先，从根结点到某结点的路径，根结点到每个叶子结点以及最远叶子的路径等。均应采取后序非递归遍历。因为后序遍历最后访问根结点，当访问到某结点时，栈中所有元素均为该结点的祖先。这里只对16题进行分析。找p和q的最近共同祖先结点r，不失一般性，设P在q的左边。后序遍历必然先遍历到结点P，栈中元素均为P的祖先。将栈复制到另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配(即相等)的元素就是结点p和q的最近公共祖先。其核心语句段如下： while(bt!=null ｜｜ top>0) {while(bt!=null＆＆bt!=p＆&bt!=q) ／／结点入栈 {S[++top].t=bt ； s[top]．tag=0；bt=bt一>ichild；} ／／沿左分支向下 if(bt==p)／／假定P在q的左侧，遇结点P时，栈中元素均为P的祖先结点 for(i=1；i<=top； i++)sl[i]=S[i]；topl=top； ／／栈S元素转入辅助栈s1 if(bt==q) ／／找到q结点 for(i：top； i>0 ； i一) ／／将栈中元素到sl去匹配 {pp=s[i]．t； for(j=topl；j>0；j—-) if(sl[j]．t==pp){cout<<”共同的祖先已找到”；return(pp)；} } while(top!=0&&s[top]．tag==1)top—； ／／退栈 if(top!=0){S[top]．tag=1；bt=s[top]．t一>rchild；} ／／沿右分支向下遍历 }／／结束while(bt!=null｜｜ top>0) return(null)；／／q、p无公共祖先