【说明】 函数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”。