二叉树的遍历.cpp

二叉树的遍历应用

// eXp_3.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#include <malloc.h>
#include <stdlib.h>

#define OVERFLOW -2
#define OK 1
#define ERROR 0

typedef int status;
typedef char TElemType;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode  *lchild,*rchild;
}BiTNode,*BiTree;


status CreateBiTree(BiTree &T)   //创建结点
{
	char ch;
	scanf("%c",&ch);
	if(ch==' ')
		T=NULL;
	else 
	{
		if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
			exit(OVERFLOW);
		T->data=ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
}

status PreOrderTraverse(BiTree T)//先序
{
	if(T)
	{
		printf("%c",T->data);		
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
				return OK;			
	}
	return ERROR;
}


status InOrderTraverse(BiTree T){//中序
	if(T)
	{
		InOrderTraverse(T->lchild);
		printf("%c",T->data);
		InOrderTraverse(T->rchild);
	}
	return OK;
}

status PosOrderTraverse(BiTree T)
{//后序
	if(T)
	{
		PosOrderTraverse(T->lchild);
		PosOrderTraverse(T->rchild);
		printf("%c",T->data);
	}

	return OK;
}
int main(int argc, char* argv[])
{
	BiTree T;
	printf("先序建立二叉树,请依次输入结点的值,空格表示结点为空\n");
	if(CreateBiTree(T)){
		printf("先序遍历序列为:");
		PreOrderTraverse(T);
		printf("\n中序遍历序列为:");
		InOrderTraverse(T);
		printf("\n后序遍历序列为:");
		PosOrderTraverse(T);
	}
	printf("\n");
	getchar();
	getchar();
	return 0;	
}