你的分享就是我们的动力 ---﹥

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

时间:2013-07-05 15:02来源:www.chengxuyuans.com 点击:

代码简介

创建、前序、中序、后序递归遍历二叉树
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);
	}
}

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");

}

转载注明地址:http://www.chengxuyuans.com/code/C++/65465.html