创建、前序、中序、后序递归遍历二叉树

代码简介

创建、前序、中序、后序递归遍历二叉树
VS2010编译通过

代码片段

/*
	关于非线性的数据结构当然树形结构最重要，而树里面又属二叉树最重要，
	所以在后面将列出二叉树的各种使用方法，包括基本的遍历，和我在一些
	资料上看到的关于二叉树的面试题型。至于一些很高级的树形结构，如平
	衡树，还有线索树等，就暂时不写出来，先完成最基本的，再一点点的加
*/

#include <stdio.h>
#include <stdlib.h>
//typedef void * ElemType;
typedef int ElemType;

struct BinaryTreeNode
{
	ElemType m_nValue;
	BinaryTreeNode *m_pLeft;
	BinaryTreeNode *m_pRight;
};

/*
	二叉树主要的难点是遍历
	基本上所有的算法都是基于二叉树的遍历的
	至于创建二叉树就需要在输入的时候把线性的结构转换成非线性的
	用输入的方式创建二叉树，
*/

				//将输入独立起来，
BinaryTreeNode * CreateTree(BinaryTreeNode *bTree)
{
	int input;
	scanf("%d",&input);			//按先序建立二叉树
	if(input == 0)
	{
		bTree = NULL;	//置为NULL后结束
		return bTree;	
	}
	bTree = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
	bTree ->m_nValue = input;
	bTree->m_pLeft = CreateTree(bTree->m_pLeft);
	bTree->m_pRight = CreateTree(bTree->m_pRight);
	return bTree;
}

//三种递归遍历方法

void Preorder(BinaryTreeNode *bTree)		//这个是先序遍历，先根，左子树，右子树
{
	if(bTree != NULL)
	{
		printf("%d ",bTree->m_nValue);
		Preorder(bTree->m_pLeft);
		Preorder(bTree->m_pRight);
	}
}

void Inorder(BinaryTreeNode *bTree)		//中序遍历，左子树，根，右子树
{
	if(bTree != NULL)
	{
		Inorder(bTree->m_pLeft);
		printf("%d ",bTree ->m_nValue);
		Inorder(bTree ->m_pRight);
	}hxyy2013.b2b168.com
http://www.wenbing.com/kmhx
}

void Postorder(BinaryTreeNode *bTree)		//后序遍历，左子树，右子树，根
{

	if(bTree != NULL)
	{
		Postorder(bTree->m_pLeft);
		Postorder(bTree->m_pRight);
		printf("%d ",bTree ->m_nValue);
	}
}
int main()
{
	BinaryTreeNode *bTree;

	bTree=CreateTree(bTree);
	printf("先序遍历结果为：\n");
	Preorder(bTree);
	printf("\n");
	
	printf("中序遍历结果为：\n");
	Inorder(bTree);
	printf("\n");

	printf("后序序遍历结果为：\n");
	Postorder(bTree);
	printf("\n");

	return 0;
	system("pause");

}