树2——创建二叉树及三种遍历

建立二叉树

编写建立二叉树的算法，要求二叉树按照链式方式存储。

    
该题是西北大学考研题。可以按照先序序列的输入建立二叉树，即先输入根结点，然后是左子树，然后是右子树。输入时如果有左孩子（或右孩子）结点，则输入结点元素；如果没有，则输入“#”。例如对于下图的所示的二叉树，它的输入结点序列就是对应右边二叉树的先序遍历，即ABE##FG###D#G##。

code：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <iostream>

typedef char DataType;
using namespace std;
typedef struct Node 
{
	DataType data;
	struct Node *lchild;
	struct Node *rchild;
}*BiTree,BitNode;

void CreateBitTree(BiTree *T);
void PreOrderTraverse(BiTree T);
void InOrderTraverse(BiTree T);
void PostOrderTraverse(BiTree T);

void InitBitTree(BiTree *T);
void DestroyBitTree(BiTree *T);

void main()
{
	BiTree T;
	InitBitTree(&T);
	cout << "根据输入二叉树的先序序列创建二叉树（‘#’表示为空）：" << endl;
	CreateBitTree(&T);
	cout << "二叉树的先序序列：" << endl;
	PreOrderTraverse(T);
	printf("\n");
	cout << "二叉树的中序遍历：" << endl;
	InOrderTraverse(T);
	printf("\n");
	cout << "二叉树的后序遍历：" << endl;
	PostOrderTraverse(T);
	printf("\n");
	DestroyBitTree(&T);
	system("pause");
}

void CreateBitTree(BiTree *T)
{
	DataType ch;
	scanf("%c",&ch);
	if (ch=='#')
	{
		*T = NULL;
	} 
	else
	{
		*T = (BiTree)malloc(sizeof(BitNode));
		if (!(*T))
		{
			exit(-1);
		}
		(*T)->data = ch;
		CreateBitTree(&((*T)->lchild));
		CreateBitTree(&((*T)->rchild));
	}
}

void DestroyBitTree(BiTree *T)
{
	if (*T)
	{
		if ((*T)->lchild)
		{
			DestroyBitTree(&((*T)->lchild));
		}
		if ((*T)->rchild)
		{
			DestroyBitTree(&((*T)->rchild));
		}
		free(*T);
		*T = NULL;
	}
}

void InitBitTree(BiTree *T)
{
	*T = NULL;
}

void PreOrderTraverse(BiTree T)
{
	if (T)
	{
		printf("%2c",T->data);
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}

void InOrderTraverse(BiTree T)
{
	if (T)
	{
		InOrderTraverse(T->lchild);
		printf("%2c",T->data);
		InOrderTraverse(T->rchild);

	}
}
void PostOrderTraverse(BiTree T)
{
	if (T)
	{
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		printf("%2c",T->data);

	}
}

结果：