数据结构:打印值为x的结点的所有祖先
添加时间: 2007-4-9 0:55:28 作者: 程序员认证参考 阅读次数:86 来源: http://www.d9soft.com
【题目】在二叉树中查找值为x的结点，试编写算法打印值为x的结点的所有祖先，假设值为x的结点不多于一个。分析算法的时间复杂度(不加分析直接写出结果得零分）。
【来源】上海交通大学98年第五题（15')
【解答】proc searchx(p:bitree)
setnull(s);found:=false;
count:=0;
lflag[1..n]:=0;{lflag、rflag分别保存结点p的左右孩子是否已访问}
rflag[1..n]:=0;{初始状态为未被访问}
while not found and count<=n do
【if p↑.data=x then found:=true;{退出}
if lflag[p]=0 and p↑.left<>nil then
【push(s,p);count:=count+1;lflag[p]=1;p:=p↑.left;】
else
【if rflag[p]=0 and p↑.right<>nil then
【push(s,p);count:=count+1;rflag[p]=1;p:=p↑.right;】
else pop(s,p)
】
】
if found then
【while not empty(s) do【pop(s,p);write(p↑.data)】{打印祖先结点}】
else
write("error")
endp;
【时间复杂度分析】本题实际上是先序遍历的一个应用，因此算法的复杂度和先序遍历相同，为O(n).
上一篇文章: 变态级JAVA程序员面试32问(附答案) 下一篇文章: 数据结构：快速排序算法(新)
相关文章: