【说明】 本程序利用非递归算法实现二叉树后序遍历。 【函数】 #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); }
