【说明】 本程序利用非递归算法实现二叉树后序遍历。 【函数】 #include＜stdio.h＞ #include＜stdlib.h＞ typedef struct node{/*二叉树的结点数据结构类型*/ char data; struct node *left; struct node *right; }BTREE; void SortTreelnsert(BTREE **tree, BTREE *s) { if(*tree==NULL)*tree=s; else if(s-＞data＜(*tree)-＞data) SortTreelnsert( (1) ,s); else if(s-＞data＞=(*tree)-＞data) SortTreelnsert( (2) ,s); } void TraversalTree(BTREE *tree) { BTREE *stack[1 000],*p; int tag[1000],top=0; p=tree; do{ while(p !=NULL) { stack[++top]=p; (3) ; tag[top]=0; /*标记栈顶结点的左子树已进行过后序遍历*/ } while(top＞0&& (4) )/*栈顶结点的右子树是否被后序遍历过*/ { p=stack[top--]; putchar(p-＞data); } if(top＞0)/*对栈顶结点的右子树进行后序遍历*/ { (5) ; tag[top]=1; } }while(top＞0); } void PrintSortTree(BTREE *tree) { if(tree !=NULL) { printSortTree(tree-＞left); putchar(tree-＞data); pdntSortTree(tree-＞right); } } main() { BTREE *root=NULL, *node; char ch; ch=getchar(); while(ch !=’#’) { node=(BTREE*)malloc(sizeof(BTREE)); node-＞data=ch; node-＞left=node-＞right=NULL; SortTreelnsert(&root, node); ch=getchar(); } PrintSortTree(root); putchar(’\n’); TraversalTree(root); }
参考答案：
解析：(1)&(*tree)-＞left (2)&(*tree)-＞right (3)p=p-＞left (4)tag[top]==1 (5)p=stack[top]-＞right
[分析]： 本题考查二叉树后序遍历的非递归实现。 二叉树后序遍历的特点是首先按后序遍历根结点的左子树，然后按后序遍历根结点的右子树，再访问根结点。后序遍历得到的序列根结点总在最后，我们可以用栈结构来实现后序遍历。下面来具体
[分析]：程序。 第(1)空很明显是函数SortTreeInsert()的第一个参数，此函数的功能是建立一棵排序二叉树，此空在条件判断语句下面，如果条件成立，说明待插入结点的值小于当前结点的值，根据排序二叉树的生成原理，应该把待插入结点插入到当前结点的左子树中，因此，此空的参数是指向当前结点左子树的地址。这里需要注意的是，这个参数是一个二重指针，需要在一重指针前加一个取地址操作符“&”。所以，此空答案为&(*tree)-＞left。 第(2)空也是函数SortTreeInsert()的第一个参数，但调用这个函数的条件与上面不一样，此空是在待插入结点的值大于等于当前结点的值的时候调用函数，根据排序二叉树的生成原理，此时应该把待插入结点插入到当前结点的右子树中，因此，此空答案为&(*tree)-＞right。 第(3)空在函数TraversalTree()中，此函数用来对树进行后序遍历，此空在一个循环体中，从程序中可以看出这个循环体的功能是将排序二叉树的所有左子树结点入栈，因此，在当前结点入栈后，接下来是它的孩子结点入栈，所以，此空答案为p=p-＞left。 第(4)空是循环的判断条件，其作用在注释中已经给出，是判断栈顶结点的右子树是否被后序遍历过。从上面程序tag[top]=0表示栈顶结点的左子树已进行过后序遍历可以推断出，tag[top]的值是用来标记栈顶结点的左右子树已进行过后序遍历，因此，此空答案为tag[top]==1。 第(5)空在条件判断语句下面，而条件判断语句为真表明要对栈顶结点的右子树进行后序遍历，那么就应该让当前需处理结点的指针指向栈顶结点的右孩子，而指向当前需要处理结点的指针变量是p，因此，此空答案为p=stack[top]-＞right。