已知一棵二叉树用二叉链表存储,t指向根节点,P指向树中任一节点。下列算法为输出从t到P之问路径上

已知一棵二叉树用二叉链表存储，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*/

do{while(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(1)top++ (2) q=q-＞lchild (3) while(top＞0) (4) stackl[topl]=q (5) topl＞0 解析：本题本质上是对二叉树的先序遍历进行考核，但不是简单地进行先序遍历，而是仅遍历从根节点到给定的节点p为止。本题采用非递归算法来实现，其主要思想是：①初始化栈；②根节点进栈，栈不空则