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