在二叉树中查找值为x的结点 试编写算法（用C语言)打印值为x的结点的所有祖先 假设值为x的结点不多
结点,算法,祖先
已帮助 人
在二叉树中查找值为x的结点，试编写算法(用C语言)打印值为x的结点的所有祖先，假设值为x的结点不多于一个，最后试分析该算法的时间复杂度。
请帮忙给出正确答案和分析，谢谢！
-
正确答案：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”)；／／找到x for(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(log2n)。
此问题考查的知识点是后序遍历的思想。后序遍历最后访问根结点，当访问到值为x的结点时，栈中所有元素均为该结点的祖先。