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

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

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

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

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

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