[題目分析]後序遍歷最後訪問根結點當訪問到值為x的結點時棧中所有元素均為該結點的祖先
void Search(BiTree btElemType x) //在二叉樹bt中查找值為x的結點並打印其所有祖先
{typedef struct
{BiTree t; int tag; }stack;//tag=表示左子女被訪問tag=表示右子女被訪問
stack s[]; //棧容量足夠大
top=;
while(bt!=null||top>)
{while(bt!=null && bt>data!=x) //結點入棧
{s[++top]t=bt; s[top]tag=; bt=bt>lchild;} //沿左分枝向下
if(bt>data==x){ printf(所查結點的所有祖先結點的值為:\n); //找到x
for(i=;i<=top;i++) printf(s[i]t>data); return; } //輸出祖先值後結束
while(top!= && s[top]tag==) top; //退棧（空遍歷）
if(top!=) {s[top]tag=;bt=s[top]t>rchild;} //沿右分枝向下遍歷
}// while(bt!=null||top>)
}結束search
因為查找的過程就是後序遍歷的過程使用的棧的深度不超過樹的深度算法復雜度為O(logn)
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23730.html
