问题描述

从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行后序遍历，然后将遍历结果打印输出。要求采用非递归方法实现。

解题思路

Push根结点到第一个栈stack1中

从第一个栈stack1中Pop出一个结点，并将其Push到第二个栈stack2中

然后Push结点的左孩子和右孩子到第一个栈stack1中

重复过程2和3直到栈stack1为空

完成后，所有结点已经Push到栈stack2中，且按照后序遍历的顺序存放，直接全部Pop出来即是二叉树后序遍历结果

程序实现

#include 
    
     #include 
     
      #define FALSE 0#define TRUE 1typedef char Datatype;/*二叉树*/typedef struct Node {	Datatype data;	struct Node *LChild;	struct Node *RChild;} BiTNode, *BiTree;/*链栈*/typedef struct Stack {	struct Node *node;	struct Stack *next;} Stack, *SeqStack;typedef struct {	SeqStack top;	int count;} LinkStack;/*栈操作*/int initStack(LinkStack *stack);int emptyStack(LinkStack *stack);int push(LinkStack *stack, BiTree tree);BiTree pop(LinkStack *stack);void createBiTree(BiTree *tree);void traverseTree(BiTree tree, LinkStack *stack1, LinkStack *stack2);int main(int argc, char *argv[]) {	BiTree tree;	printf("按先序遍历序列建立二叉树:\n");	createBiTree(&tree);	LinkStack stack1, stack2;	initStack(&stack1);	initStack(&stack2);	printf("使用栈后序输出二叉树:\n");	traverseTree(tree, &stack1, &stack2);	return 0;}/** *  初始化一个空栈 */int initStack(LinkStack *stack) {	stack->top = (SeqStack)malloc(sizeof(Stack));	if(!stack->top) {		return FALSE;	}	stack->top = NULL;	stack->count = 0;	return TRUE;}/** * 判断栈是否为空 */int emptyStack(LinkStack *stack) {	int result = 0;	if (stack->count == 0) {		result = 1;	}	return result;}/** * 入栈操作 */int push(LinkStack *stack, BiTree tree) {	SeqStack s = (SeqStack)malloc(sizeof(Stack));	s->node = tree;	s->next = stack->top;	/* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */	stack->top = s;         /* 将新的结点s赋值给栈顶指针，见图中② */	stack->count++;	return 1;}/** * 出栈操作 */BiTree pop(LinkStack *stack) {	BiTree tree;	SeqStack p;	if (emptyStack(stack)) {		return FALSE;	}	tree = stack->top->node;	/*将栈顶结点赋值给p*/	p = stack->top;	/*使得栈顶指针下移一位，指向后一结点*/	stack->top = stack->top->next;	/* 释放结点p */	free(p);	stack->count--;	return tree;}void createBiTree(BiTree *tree) {	char ch;	ch = getchar();	if(ch == ' ') {		*tree = NULL;	} else {		//生成一个新结点		*tree = (BiTree)malloc(sizeof(BiTNode));		(*tree)->data = ch;		//生成左子树		createBiTree(&((*tree)->LChild));		//生成右子树		createBiTree(&((*tree)->RChild));	}}/**遍历树的结点*//*定义了两个栈接受后序遍历的结果*/ void traverseTree(BiTree tree, LinkStack *stack1, LinkStack *stack2) {	if(tree == NULL) {		return;	}	BiTree root = tree;	push(stack1, root);	while (!emptyStack(stack1)) {		BiTree t = stack1->top->node;		push(stack2, t);		pop(stack1);		if (t->LChild != NULL) {			push(stack1, t->LChild);		}		if (t->RChild != NULL) {			push(stack1, t->RChild);		}	}	root = pop(stack2);	printf("%c ", root->data);	while (!emptyStack(stack2)) {		root = pop(stack2);		printf("%c ", root->data);	}}