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

淡淡的烟草味﹌ 2022-08-25 09:27 182阅读 0赞

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

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;
    }

运行结果：

![SouthEast][]

[SouthEast]: /images/20220824/a7f4d126a3ac4831b4987f92d0cd8768.png