数据结构_树_二叉树的建立、遍历、复制与移除_二叉链表存储_C++实现

"head.h"

#include<iostream>
using namespace std;

class BitNode
{
public:
	BitNode();
	char ch;
	BitNode *lchild,*rchild;
};

BitNode::BitNode()
{
	lchild=rchild=NULL;
}

class BiTree
{
public:
	BiTree();
	void CreatBiTree();//建立二叉树
	void Traverse();//遍历二叉树
	void CopyBiTree();//复制二叉树
private:
	void ReMoveBiTree(BitNode *&);//移除整棵二叉树
	void PreOrderCreatBiTree(BitNode *&);//先序建立二叉树
	void PreOrderTraverse(BitNode *&);//先序遍历二叉树
	void InOrderTraverse(BitNode *&);//中序遍历二叉树
	void PostOrderTraverse(BitNode *&);//后序遍历二叉树
	void Copy(BitNode *&,BitNode *&);//复制二叉树
	BitNode * root;
	char ch;
};

BiTree::BiTree()
{
	root=NULL;
}

void BiTree::CreatBiTree()
{
	cout<<"CreatBiTree Called !"<<endl<<endl;
	if(root!=NULL)
		ReMoveBiTree(root);
	char choice;
	cout<<"You Choice , Please ?"<<endl<<endl
		<<"1 . PreOrderCreatBiTree"<<endl
		<<"9 . Quit"<<endl<<endl;
	cin>>choice;
	cout<<"Please Enter The BitTree :"<<endl<<endl;
	switch(choice)
	{
	case '1':
		PreOrderCreatBiTree(root);
		break;
	case '9':
		break;
	default:
		cout<<"No Such Choice !"<<endl<<endl;
		break;
	}
	cin.clear();
}

void BiTree::Traverse()
{
	cout<<"Traverse Called !"<<endl<<endl;
	if(root==NULL)
	{
		cout<<"BiTree Is Empty !"<<endl<<endl;
		return ;
	}
	char choice;
	cout<<"You Choice , Please ?"<<endl<<endl
		<<"1 . PreOrderTraverse"<<endl
		<<"2 . InOrderTraverse"<<endl
		<<"3 . PostOrderTraverse"<<endl
		<<"9 . Quit"<<endl<<endl;
	cin>>choice;
	switch(choice)
	{
	case '1':
		PreOrderTraverse(root);
		break;
	case '2':
		InOrderTraverse(root);
		break;
	case '3':
		PostOrderTraverse(root);
		break;
	case '9':
		break;
	default:
		cout<<"No Such Choice !"<<endl<<endl;
		break;
	}
	cout<<endl<<endl;
}

void BiTree::PreOrderTraverse(BitNode * &t)
{
	if(t!=NULL)
	{
		cout<<t->ch;
		PreOrderTraverse(t->lchild);
		PreOrderTraverse(t->rchild);
	}
}

void BiTree::InOrderTraverse(BitNode *& t)
{
	if(t!=NULL)
	{
		InOrderTraverse(t->lchild);
		cout<<t->ch;
		InOrderTraverse(t->rchild);
	}
}

void BiTree::PostOrderTraverse(BitNode *& t)
{
	if(t!=NULL)
	{
		PostOrderTraverse(t->lchild);
		PostOrderTraverse(t->rchild);
		cout<<t->ch;
	}
}

void BiTree::PreOrderCreatBiTree(BitNode *& t)
{
	if(cin>>ch)
	{
		if(ch=='#')
			t=NULL;
		else
		{
			t=new BitNode;
			t->ch=ch;
			PreOrderCreatBiTree(t->lchild);
			PreOrderCreatBiTree(t->rchild);
		}
	}
}

void BiTree::ReMoveBiTree(BitNode *& t)
{
	if(t!=NULL)
	{
		ReMoveBiTree(t->lchild);
		ReMoveBiTree(t->rchild);
		delete t;
	}
}

void BiTree::CopyBiTree()
{
	cout<<"Copy BiTree Called !"<<endl<<endl;
	if(root==NULL)
	{
		cout<<"No BiTree To Copy !"<<endl<<endl;
		return;
	}
	BitNode * t;
	Copy(t,root);
	PreOrderTraverse(t);
	cout<<endl<<endl;
	InOrderTraverse(t);
	cout<<endl<<endl;
	PostOrderTraverse(t);
	cout<<endl<<endl;
	ReMoveBiTree(t);
}

void BiTree::Copy(BitNode *&t,BitNode *&r)
{
	if(r!=NULL)
	{
		t=new BitNode;
		t->ch=r->ch;
		Copy(t->lchild,r->lchild);
		Copy(t->rchild,r->rchild);
	}
}

"main.h"

#include<iostream>
#include"head.h"
using namespace std;

int main()
{
	BiTree t;
	char choice;
	while(1)
	{
		cout<<"You Choice , Please ?"<<endl<<endl
			<<"1 . CreatBiTree"<<endl
			<<"2 . Traverse"<<endl
			<<"3 . CopyBiTree"<<endl
			<<"9 . Quit"<<endl<<endl;
		cin>>choice;
		switch(choice)
		{
		case '1':
			t.CreatBiTree();
			break;
		case '2':
			t.Traverse();
			break;
		case '3':
			t.CopyBiTree();
			break;
		case '9':
			return 0;
			break;
		default:
			cout<<"No Such Choice !"<<endl<<endl;
			break;
		}
	}
	return 0;
}