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

你的名字 2022-08-25 09:15 160阅读 0赞

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

1.递归遍历

2.利用链栈 实现非递归遍历

以下代码在vs2010 测试通过：

#include "stdafx.h"
    #include "stdio.h"
    #include "stdlib.h"
    
    typedef struct TreeNode{
    	int data;
    	struct TreeNode *lchild;
    	struct TreeNode *rchild;
    }TreeNodePro;
    typedef struct StackNode{
    	TreeNodePro *stacktree;
    	struct StackNode *next;
    }StackNodePro;
    typedef struct StackList{
    	StackNodePro *top;
    	int count;
    }StackListPro;
    
    //递归 新建二叉树
    void create_midorder_tree(TreeNodePro **tree){
    	//TreeNodePro *ptree;
    	int em;
    	int result = 0;
    
    	printf("请输入二叉树的节点的数值：");
    	result = scanf("%d",&em);
    	if(result != 0 ){
    		if( em != 0){
    
    			//ptree = *tree;
    			*tree = (TreeNodePro *)malloc(sizeof(TreeNodePro));
    			if(*tree != NULL){
    				(*tree)->data = em ;
    				create_midorder_tree((&(*tree)->lchild));
    				create_midorder_tree(&((*tree)->rchild));
    			}
    		}else{
    			*tree = NULL;
    		}
    	}
    }
    
    //递归遍历二叉树
    void recursive_midorder_tree(TreeNodePro *tree){
    	if(tree != NULL){
    		recursive_midorder_tree(tree->lchild);
    		printf("%d\t",tree->data);
    		recursive_midorder_tree(tree->rchild);
    	}
    }
    //新建栈
    void stack_init(StackListPro **stack){
    	*stack = (StackListPro *)malloc(sizeof(StackListPro));
    	if(*stack != NULL){
    		(*stack)->top = NULL;
    		(*stack)->count = 0 ;
    	}
    }
    //入栈
    void stack_push(StackListPro *s,TreeNodePro *tree){
    	StackNodePro *snode;
    	snode = (StackNodePro *)malloc(sizeof(StackNodePro));
    	if(snode != NULL){
    		//StackNodePro *tmp_snode;
    		snode->stacktree = tree;
    		//tmp_snode = s->top;
    		snode->next = s->top ;
    
    		s->top = snode;
    		s->count++;
    	}
    }
    //出栈
    TreeNodePro* stack_pop(StackListPro *stack){
    	if(stack != NULL && stack->count > 0 ){
    		StackNodePro *slnode ;
    		TreeNodePro *stree;
    
    		stree = stack->top->stacktree;
    		slnode = stack->top;
    		stack->top = stack->top->next;
    		stack->count--;
    		free(slnode);
    		return stree;
    	}
    }
    //非递归（利用链栈）遍历二叉树
    void unrecursive_midorder_tree(TreeNodePro *tree){
    	StackListPro *lstack;
    	//建栈
    	stack_init(&lstack);
    	TreeNodePro *ptree;
    	ptree = tree;
    	while(ptree != NULL || lstack->count > 0){
    		while(ptree != NULL){
    			stack_push(lstack,ptree);	
    			ptree = ptree->lchild;
    		}
    		ptree = stack_pop(lstack);
    		printf("%d\t",ptree->data);
    		ptree = ptree->rchild;
    	}
    }
    
    int _tmain(int argc, _TCHAR* argv[]){
    	//中序递归创建 二叉树
    	TreeNodePro *tree ;
    	create_midorder_tree(&tree);
    	//二叉树中序 递归遍历
    	printf("递归中序遍历二叉树的结果为：\n");
    	recursive_midorder_tree(tree);
    	//二叉树中序 非递归遍历
    	printf("\n非递归中序遍历二叉树的结果为：\n");
    	unrecursive_midorder_tree(tree);
    	printf("\n");
    	system("pause");
    	return 0;
    }

输入测试数据，运行结果：

![SouthEast][]

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