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

（）略 () 根据中序和后序序列建立二叉树的递归算法见上面第题非递归算法见第题

[题目分析]采用后序非递归遍历二叉树栈中保留从根结点到当前结点的路径上的所有结点

void PrintPath(BiTree btp) //打印从根结点bt到结点p之间路径上的所有结点

{BiTree q=bts[]; //s是元素为二叉树结点指针的栈容量足够大

int top=; tag[];//tag是数组元素值为或访问左右子树的标志tag和s同步

if (q==p) {printf(q>data); return;} //根结点就是所找结点

while(q!=null || top>)

{while(q!=null) //左子女入栈并置标记

if（q==p） //找到结点p栈中元素均为结点p 的祖先

{printf(从根结点到p结点的路径为\n);

for(i=;i<=top;i++) printf(s[i]>data); printf(q>data); return;

}

else {s[++top]=q; tag[top]=; q=q>lchild;} //沿左分支向下

while(top> && tag[top]==)) top//本题不要求输出遍历序列这里只退栈

if (top>) {q=s[top]; q=q>rchild; tag[top]=; } //沿右分支向下

}//while(q!=null || top>)

}//结束算法PrintPath

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