--------------------BinaryTree.h-------------------------------
#include<iostream>
#include<stdlib.h>
using namespace std;
template<class T>
struct BinTreeNode
{
T data;
BinTreeNode<T> *leftChild,*rightChild; //左右孩子指针
BinTreeNode():leftChild(NULL),rightChild(NULL){}
BinTreeNode(T x,BinTreeNode<T> *l=NULL,BinTreeNode<T> *r=NULL):data(x),leftChild(l),rightChild(r){}
};
template<class T>
class BinaryTree
{
public:
// BinaryTree():root(NULL){}
BinaryTree():root(NULL){CreateBinTree(root);}
void PreOrder(){PreOrder(root);} //前序遍历
void inOrder(){inOrder(root);} //中序遍历
void postOrder(){postOrder(root);} //后序遍历
protected:
BinTreeNode<T> *root; //二叉树的根结点指针
// void Print(BinTreeNode<T> *p); //输出二叉树每个结点的值
void CreateBinTree(BinTreeNode<T> *&subTree);//利用二叉树前序遍历生成二叉树
void PreOrder(BinTreeNode<T> *&subTree);
void inOrder(BinTreeNode<T> *&subTree);
void postOrder(BinTreeNode<T> *&subTree);
};
template<class T>
void BinaryTree<T>::CreateBinTree(BinTreeNode<T> *&subTree)
{
char value;
cin>>value;
if(value=='#') subTree=NULL;
else
{
subTree=new BinTreeNode<T>(value);
if(subTree==NULL)
{
cerr<<"内存分配错误!";
exit(1);
}
CreateBinTree(subTree->leftChild);
CreateBinTree(subTree->rightChild);
}
};
template<class T>
void BinaryTree<T>::PreOrder(BinTreeNode<T> *&subTree)
{
if(subTree!=NULL)
{
cout<<subTree->data<<" ";
PreOrder(subTree->leftChild);
PreOrder(subTree->rightChild);
}
};
template<class T>
void BinaryTree<T>::inOrder(BinTreeNode<T> *&subTree)
{
if(subTree!=NULL)
{
inOrder(subTree->leftChild);
cout<<subTree->data<<" ";
inOrder(subTree->rightChild);
}
};
template<class T>
void BinaryTree<T>::postOrder(BinTreeNode<T> *&subTree)
{
if(subTree!=NULL)
{
postOrder(subTree->leftChild);
postOrder(subTree->rightChild);
cout<<subTree->data<<" ";
}
};
--------------------------main.cpp----------------------------------
#include"BinaryTree.h"
int menu()
{
int choice=0;
cout<<" ****************二叉树练习******************"<<endl<<endl;
cout<<" 前序遍历输出二叉树，请按1:"<<endl;
cout<<" 中序遍历输出二叉树，请按2:"<<endl;
cout<<" 后序遍历输出二叉树，请按3:"<<endl;
cout<<" 退出请按4:"<<endl<<endl;
cout<<" ********************************************"<<endl<<endl;
cout<<" Please enter the number:";
cin>>choice;
return choice;
}
int main()
{
cout<<"前序遍历建立二叉树:"<<endl;
BinaryTree<char> tree;
bool exit=false;
while(true)
{
int choice=menu();
switch(choice)
{
case 1:
tree.PreOrder();break;
case 2:
tree.inOrder();break;
case 3:
tree.postOrder();;break;
case 4:exit=true;break;
default:cout<<" 您的输入有误，请重新输入!";break;
}
system("pause"); //暂停
system("cls"); //清屏
if(exit==true) break;
}
return 0;
}