【说明】 本程序利用非递归算法实现二叉树后序遍历。 【函数】 #include

题目：

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