数据结构考研分类复习真题 第六章 答案 (五)[14]

[题目分析]后序遍历最后访问根结点当访问到值为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)

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []