数据结构 -- 二叉树后序遍历

二叉树 后序遍历 的两种方法：

1.递归 后序遍历二叉树；

2.利用链栈 非递归 后序遍历二叉树

以下代码 在 vs2010 测试通过：

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"

typedef struct TreeNode{
	int data;
	struct TreeNode *lchild,*rchild;
}TreeNodePro;
typedef struct StackNode{
	TreeNodePro *treenode;
	struct StackNode *next;
}StackNodePro;
typedef struct StackList{
	int count;
	StackNodePro *top;
}StackListPro;
//递归 建立二叉树
void create_behorder_tree(TreeNodePro **tree){
	int em ;
	int result;
	printf("请输入二叉树节点的数值：");
	result = scanf("%d",&em);
	if(result != 0 ){
		if(em == 0){
			*tree = NULL;
		}else{
			*tree = (TreeNodePro *)malloc(sizeof(TreeNodePro));
			if(*tree != NULL){
				(*tree)->data = em;
				create_behorder_tree((&(*tree)->lchild));
				create_behorder_tree((&(*tree)->rchild));
			}	
		}	
	}	
}
//递归 后序遍历二叉树
void recursive_behorder_tree(TreeNodePro *tree){
	if(tree != NULL){
		recursive_behorder_tree(tree->lchild);
		recursive_behorder_tree(tree->rchild);
		printf("%d\t",tree->data);
	}
	
}
//新建一个栈
void stack_init(StackListPro **stack){
	*stack = (StackListPro *)malloc(sizeof(StackListPro));
	if(stack != NULL){
		(*stack)->top = NULL;
		(*stack)->count = 0 ;
	}
}
//入栈
void stack_push(StackListPro *stack,TreeNodePro *tree){
	StackNodePro *snode;
	snode = (StackNodePro *)malloc(sizeof(StackNodePro));
	if(snode != NULL){
		snode->treenode = tree;

		snode->next = stack->top;

		stack->top = snode;
		stack->count++;
	}
}
//出栈
TreeNodePro * stack_pop(StackListPro *stack){
	if(stack != NULL && stack->top > 0){
		StackNodePro *pstack;
		TreeNodePro *ptree;

		pstack = stack->top;
		ptree = stack->top->treenode;

		stack->top = stack->top->next;
		stack->count--;
		free(pstack);
		return ptree;
	}
}
//获取栈顶元素
TreeNodePro* get_stack_top(StackListPro *stack){
	if(stack->top != NULL && stack->count > 0){
		return stack->top->treenode;
	}
	return NULL;
}
/*
* 利用链栈 非递归 后序遍历二叉树
* 解题思路：
*	1.依次遍历二叉树，若存在做孩子则将该节点入栈，直至遍历的节点左孩子为空
*   2.获得栈顶节点，然后将栈顶节点作为新的父节点，继续遍历二叉树，若存在做孩子则入栈
*	3.如不存在左孩子，存在右孩子，则重复 2 的步骤
*	4.如不存在左孩子，也不存在右孩子，则打印出该节点的值
*/
void unrecursive_behorder_tree(TreeNodePro *tree){
	//建栈
	StackListPro *stack;
	stack_init(&stack);

	TreeNodePro *ptree;
	TreeNodePro *tmptree = NULL;

	ptree = tree;
	while(ptree != NULL || stack->count > 0){
		while(ptree != NULL){
			stack_push(stack,ptree);
			ptree = ptree->lchild;
		}
		
		ptree = get_stack_top(stack); //获取栈顶元素
		if(ptree->rchild == NULL || ptree->rchild == tmptree ){ //判断该节点的右孩子是否已被访问
			ptree = stack_pop(stack);
			printf("%d\t",ptree->data);
			tmptree = ptree;
			ptree = NULL;
		}else{
			ptree = ptree->rchild;
		}
	}
}
int _tmain(int argc, _TCHAR* argv[]){
	//递归 建立二叉树
	TreeNodePro *tree = NULL;
	create_behorder_tree(&tree);
	//递归 后序遍历二叉树
	printf("\n递归法后序遍历二叉数：\n");
	recursive_behorder_tree(tree);
	//非递归 后序遍历二叉树
	printf("\n非递归法后序遍历二叉树：\n");
	unrecursive_behorder_tree(tree);
	printf("\n");
	system("pause");
	return 0;
}

运行结果：

数据结构 -- 二叉树后序遍历,布布扣,bubuko.com

数据结构 -- 二叉树后序遍历

原文：http://blog.csdn.net/lofter_h/article/details/20227411