【正确答案】正确答案：算法的基本设计思想：采用后序遍历，最后访问根结点，当访问到值为X的结点时，栈中所有元素均为该结点的祖先。算法的代码： typedef struct { BiTree bt; int tag; lstack； ／／tag=0表示左子女被访问，tag=1表示右子女被访问 void Search(BiTree bt，ElemType x){ ／／在二叉树bt中，查找值为X的结点，并打印其所有祖先 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一>ichild； ／／沿左分支向下 } if(bt一>data==x) { printf(“所查结点的所有祖先结点的值为：＼n”);／／找到X for(i：1；i<=top；i++) printf(”％d”，s[i]．t->data)； ／／输出祖先值后结束 exit(1); } while(top!=O＆＆s[top]．tag==1) top一一； ／／退栈(空遍历) if(top!=0) { s[top]．tag=1； bt=s[top]．t一>rchild；／／沿右分支向下遍历 } }／／while(bt!=NULL ｜｜ top>0) }// search 因为查找的过程就是后序遍历的过程，使用的栈的深度不超过树的深度，算法复杂度为0(10gn)。