[说明]
已知一棵二叉树用二叉链表存储，t指向根节点，P指向树中任一节点。下列算法为输出从t到P之问路径上的节点。
[C程序]
#define MaxSize 1000
typedef struct node
TelemType data ;
struct node *ichiid，*rchiid；
BiNode，*BiTree；
void Path(BiTree t，BiNode *P)
BiTree *stack[Maxsize]，*stackl[Maxsize],*q；
int tag[Maxsize]，top=0，topl；
q=t；
/*通过先序遍历发现P*/
dowhile(q!=NULL ＆＆q!=p)
/*扫描左孩子，_日．相应的节点不为P*/
(1) ；
stack[top]=q；
tag[top]=0；
(2) ；
if(top＞0)
if(stack[top]=P) break； /*找到P，栈底到栈顶为t到P*/
if(tag[top]==1)top--;
else q=stack[top]；
q=q-＞rchiid;
tag[top]=1;
(3) ；
top--；topl=0；
while(top＞0)
q=stack[top]； /*反向打印准备*/
topl++；
(4) ；
top--;
while( (5) ) /*打印栈的内容*/
q=stackl[topl]j
printf(q-＞data)；
topl--；
参考答案：(1)top++ (2) q=q-＞lchild (3) while(top＞0) (4) stackl[topl]=q (5) topl＞0
解析： 本题本质上是对二叉树的先序遍历进行考核，但不是简单地进行先序遍历，而是仅遍历从根节点到给定的节点p为止。本题采用非递归算法来实现，其主要思想是：①初始化栈；②根节点进栈，栈不空则循环执行以下步骤直到发现节点p；③当前节点不为空且不为P进栈；④栈顶为p，则结束，否则转③；⑤若右子树访问过，则栈顶的右孩子为当前节点，转③。
扫描左孩子，．当相应的节点不为P时进栈，所以(1)填“top++”，(2)填“q=q-＞lchild”。在栈不为空时则一直在do while循环中查找，因此(3)填“while(top＞0)”。在进行反向打印准备时，读取stack[top]的信息放到stackl[topl]中，即(4)填“stackl[top1]=q”。打印栈中所有内容，所以(5)填“topl＞0”。