[说明]
函数print (BinTreeNode *t; DateType ＆x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。
[函数]
void print (BinTreeNode * t; DateType ＆x)
stack ST;int i,top;top=0; //置空栈
while (t ! =NULL ＆＆ t-＞data ! =x || top ! =0)
while (t!=NULL ＆＆ t-＞data !=x)
//寻找值为x的结点
(1) ;
ST [top].ptr=t;
ST[top].tag=0;
(2) ;
if(t!=Null ＆＆ t-＞data==x) //找到值为x的结点
for(i=1; (3) ; i++)
printf("%d", ST [top].ptr-＞data);
else
while( (4) )
top--;
if(top＞0)
ST [top] .tag=1;
(5) ;
参考答案：t=ST[top].ptr-＞rightChild
解析： 这个程序是一个典型二叉树后序遍历非递归算法的应用。
算法的实现思路是：先扫描根结点的所有左结点并入栈; 当找到一个结点的值为x时，则输入出栈里存放的数据，这些数据就是该结点所有祖先结点; 然后判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，该子树已经全部后序遍历过，如果不是，则对栈顶结点的右子树进行后序遍历，此时应把栈顶结点的右子树的相应结点放入栈中。再重复上述过程，直至遍历过树中所有结点。空(1)和空(2)所在循环就是扫描根结点的所有左结点并入栈，根据程序中的栈的定义，栈空时top=0，因此在入栈时，先将栈顶指针加1，因此空(1)处应填写“top++”或其等价形式，空(2)是取当前结点的左子树的根结点，因此应填写“t=t-＞leftChild”。空(3)所在循环是处理找到值为x的结点，那么该结点的所有祖先结点都存放在栈中，栈中的栈底是二叉树的根，而栈顶元素是该结点的父结点，因此，空(3)处应填写“i=top”。空(4)所在循环是判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，这里要填写判断条件。tag=0表示左子树，tag=1表示右子树，因此，空(4)处应填写“top＞0 ＆＆ ST[top].tag=1”。空(5)所在语句块是处理栈顶元素的右子树没有被后序遍历的情况，则将右子树入栈，因此空(5)处应填写“t=ST[top].ptr-＞rightChild”。