参考答案

正确答案：void Search(BiTree btElemType x)／／在二叉树bt中查找值为x的结点并打印其所有祖先{typedef struct{BiTree t；int tag；}stack；／／tag标志stack S[]；／／栈容量足够大top=0；while(bt!=null ‖ top＞0){while(bt!=null&&bt->data!=X){S[++top]．t=bt；S[top]．tag=0；bt=bt->lchild；}／／结点入栈沿左分支向下if(bt一>data==x){printf(”所查结点的所有祖先结点的值为：＼n”)；／／找到xfor(i=1；i<=top；i++)printf(S[i]．t一>data)；return；}／／输出祖先值后结束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)}结束Search因为查找的过程就是后序遍历的过程使用的栈的深度不超过树的深度算法复杂度为O(log₂n)。
此问题考查的知识点是后序遍历的思想。后序遍历最后访问根结点，当访问到值为x的结点时，栈中所有元素均为该结点的祖先。