填空题
[说明] 假设二叉树采用连接存储结构进行存储，root 指向根接点，p 所指结点为任一给定的结点，编写一个求从根结点到p所指结点之间路径的函数。
void path (root, p)
btree * root, * p;
{
Btree *stack[m0], *s;
int tag[m0], top =0, i, find =0;
s =root;
do
{
while (s ! = NULL)
{
stack [top] = s;
tag[top] =0;
({{U}} (1) {{/U}})
}
if (top ＞0)
{
({{U}} (2) {{/U}})
if (tag[top] = =1)
{
if({{U}} (3) {{/U}})
{
for (i=1; i＜ =top; i+ + printf ("%d" ,stack[i]- ＞data);
find=1;
}
else top - -;
}
if({{U}} (4) {{/U}})
{
p=p- ＞right;
({{U}} (5) {{/U}})
}
}
} while (find ｜｜ (s! = NULL && top ! =0));
}
【正确答案】
1、s=s->left；
【答案解析】(2)s=stack [top]；
(3)(s==p)
(4)(top>0 && ! find)
(5)tag [top]=1
试题三
[解答要点] 本题采用非递归后序遍历数root，当后序遍历访问到p所指结点时，此时stack中所有的结点均为P所指结点的祖先，由这些祖先便构成了一条从根结点到p所指结点之间的路径。