創(chuàng)建、前序、中序、后序遞歸遍歷二叉樹

代碼簡介

創(chuàng)建、前序、中序、后序遞歸遍歷二叉樹
VS2010編譯通過

代碼片段

/*
	關(guān)于非線性的數(shù)據(jù)結(jié)構(gòu)當然樹形結(jié)構(gòu)最重要，而樹里面又屬二叉樹最重要，
	所以在后面將列出二叉樹的各種使用方法，包括基本的遍歷，和我在一些
	資料上看到的關(guān)于二叉樹的面試題型。至于一些很高級的樹形結(jié)構(gòu)，如平
	衡樹，還有線索樹等，就暫時不寫出來，先完成最基本的，再一點點的加
*/

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

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

/*
	二叉樹主要的難點是遍歷
	基本上所有的算法都是基于二叉樹的遍歷的
	至于創(chuàng)建二叉樹就需要在輸入的時候把線性的結(jié)構(gòu)轉(zhuǎn)換成非線性的
	用輸入的方式創(chuàng)建二叉樹，
*/

				//將輸入獨立起來，
BinaryTreeNode * CreateTree(BinaryTreeNode *bTree)
{
	int input;
	scanf("%d",&input);			//按先序建立二叉樹
	if(input == 0)
	{
		bTree = NULL;	//置為NULL后結(jié)束
		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("先序遍歷結(jié)果為：\n");
	Preorder(bTree);
	printf("\n");
	
	printf("中序遍歷結(jié)果為：\n");
	Inorder(bTree);
	printf("\n");

	printf("后序序遍歷結(jié)果為：\n");
	Postorder(bTree);
	printf("\n");

	return 0;
	system("pause");

}