【说明】
函数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) ;
参考答案：(1)top++ (2)t=t-＞leftChild (3)i=top
(4)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”。
