二叉树三种遍历方式(递归)

二叉树的先序、中序、后序遍历，采用递归实现。

#include<stdio.h>
#include<stdlib.h>
typedef char DataType;
//定义二叉树类型的节点
typedef struct BTnode{
	DataType data;//数据域
	struct BTnode* lchild,*rchild;//左孩子和右孩子
}BTree;

//创建二叉树,以先序的方式输入，如果左孩子或右孩子为空，则输入#
/*
   例子  A      输入为:ABD##E##CF###
       /  \
     B     C
	/ \    / 
   D   E  F    
*/
void createBTree(BTree * &t)
{
	char c;
   	c=getchar();
	if(c=='#')
		t=NULL;
	else
	{
		t=(BTree*)malloc(sizeof(BTree));
		t->data=c;
		createBTree(t->lchild);//创建左子树
		createBTree(t->rchild);//创建右子树
	}
}

//先序遍历
void preOrder(BTree *root)
{
	if(NULL!=root)
	{
		printf("%c  ",root->data);//先访问根节点
		preOrder(root->lchild);//再先序遍历左子树
		preOrder(root->rchild);//最后先序遍历右子树
	}
}

//中序遍历
void inOrder(BTree *root)
{
	if(NULL!=root)
	{	
		inOrder(root->lchild);//先中序遍历左子树
		printf("%c  ",root->data);//再访问根节点
		inOrder(root->rchild);//最后中序遍历右子树
	}
}

//后序遍历
void postOrder(BTree *root)
{
	if(NULL!=root)
	{	
		postOrder(root->lchild);//先后序遍历左子树
		postOrder(root->rchild);//再后序遍历右子树
		printf("%c  ",root->data);//最后访问根节点
	}
}

int main()
{
	BTree *root;
	createBTree(root);//创建二叉树

    preOrder(root);//先序遍历
	printf("\n");

	inOrder(root);//中序遍历
	printf("\n");

	postOrder(root);//后序遍历
	printf("\n");

	return 0;
}

评论

3 楼 renread 2012-11-24  

jacobcookie 写道

renread 写道

数据输入之后就没反应了。

没理由啊，你怎么输入数据的?

不好意思，理解错了，每次输一个字符都按了回车.

2 楼 jacobcookie 2012-11-23  

renread 写道

数据输入之后就没反应了。

没理由啊，你怎么输入数据的?

1 楼 renread 2012-11-23  

数据输入之后就没反应了。