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

﹏ヽ暗。殇╰゛Y 2022-08-25 09:00 134阅读 0赞

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

1.递归遍历

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

以下代码在vs2010 测试通过：

#include "stdafx.h"
    #include "stdio.h"
    #include "stdlib.h"
    
    #define TRUE 1
    #define FALSE 0
    
    typedef struct TreeNode{
    	int data;
    	struct TreeNode *lchild,*rchild;
    }TNode;
    
    typedef struct StackNode{
    	TNode *tree;
    	struct StackNode *next;
    }StackNodePro;
    typedef struct StackList{
    	StackNodePro* top;
    	int count;
    }StackListPro;
    
    
    //前序创建 一个二叉树(递归)
    int create_preorder_tree(TNode** Tree){
    	int em;
    
    	printf("请输入节点的值：");
    	scanf("%d",&em);
    
    	if(em == 0){
    		*Tree = NULL;
    		return TRUE;
    	}else{
    		*Tree =(TNode *)malloc(sizeof(TNode));
    		if(*Tree == NULL){
    			return FALSE;
    		}
    		(*Tree)->data = em;
    		create_preorder_tree(&((*Tree)->lchild));
    		create_preorder_tree(&((*Tree)->rchild));
    	}
    	return TRUE;
    }
    //前序遍历整个二叉树 （递归）
    void preorder_tree_recursive(TNode *Tree){
    
    	if(Tree != NULL){
    		printf("%d\t",Tree->data);
    		preorder_tree_recursive(Tree->lchild);
    		preorder_tree_recursive(Tree->rchild);
    	}
    }
    //建栈
    void stack_init(StackListPro *s){
    	s->top = NULL;
    	s->count = 0 ;
    }
    //入栈
    void stack_push(StackListPro* s,TNode *tree){
    	StackNodePro *snode ;
    	snode = (StackNodePro *)malloc(sizeof(StackNodePro));
    	if(snode != NULL){
    		snode->tree = tree ;
    		snode->next = s->top;
    
    		s->top = snode;
    		s->count++;
    	}
    }
    //出栈
    TNode* stack_pop(StackListPro* s){
    	if(s != NULL && s->count > 0){
    		StackNodePro *pop_node;
    		TNode *pop_tree_node ;
    		pop_node = s->top;
    		pop_tree_node = s->top->tree;
    		s->top = s->top->next;
    		s->count--;
    		free(pop_node);
    
    		return pop_tree_node;
    	}
    }
    int stack_is_empty(StackListPro *s){
    	if(s->top == NULL || s->count == 0){
    		return 0;
    	}
    	return 1;
    }
    //前序遍历整个二叉树 （非递归）
    void preorder_tree_unrecursive(TNode *Tree){
    	TNode *pop_tree;
    	pop_tree = Tree;
    	StackListPro stack;
    	stack_init(&stack);
    	while(pop_tree != NULL || stack_is_empty(&stack) != NULL){
    		while(pop_tree != NULL){
    			printf("%d\t",pop_tree->data);
    			stack_push(&stack,pop_tree);
    			pop_tree = pop_tree->lchild;
    		}
    		pop_tree = stack_pop(&stack);
    		pop_tree = pop_tree->rchild;
    	}
    }
    
    int _tmain(int argc, _TCHAR* argv[]){
    	TNode* Tree = NULL;
    
    	create_preorder_tree(&Tree);
    	
    	printf("\n递归法 前序遍历二叉树：\n");
    	preorder_tree_recursive(Tree);
    	printf("\n非递归法 前序遍历二叉树：\n");
    	preorder_tree_unrecursive(Tree);
    	printf("\n");
    	system("pause");
    	return TRUE;
    }

运行结果：

![SouthEast][]

[SouthEast]: /images/20220824/7461f102d0d74c17b4e6db15617812bb.png