#include <iostream>
using namespace std;
template <class datatype>
struct TreeNode
{
datatype data;
TreeNode<datatype> * left,* right;
};
template<class datatype>
class BTree_Link
{
public:
BTree_Link();//构造函数
~BTree_Link();//析构函数
datatype Pre_Tree(TreeNode<datatype> * root);//前序遍历
datatype Mid_Tree(TreeNode<datatype> * root);//中序遍历
datatype Las_Tree(TreeNode<datatype> * root);//后续遍历
datatype Lev_Tree(TreeNode<datatype> * root);//层序遍历
private:
TreeNode<datatype> *root;
TreeNode<datatype> * Creat(); //创建节点
void Relse(TreeNode<datatype> *root); //删除节点
};
template<class datatype>
BTree_Link<datatype> ::BTree_Link() //构造函数
{
root = Creat();
}
template<class datatype>
BTree_Link<datatype>::~BTree_Link() //析构函数
{
Relse(root);
}
template<class datatype>
datatype BTree_Link<datatype> :: Pre_Tree(TreeNode<datatype> * root) //递归算法 前序遍历
{
if (root == NULL)
return 0;
else
{
cout << root.data<<endl;
Pre_Tree(root.left);
Pre_Tree(root.right);
}
}
template<class datatype>
datatype BTree_Link<datatype>::Mid_Tree(TreeNode<datatype> *root) //中序遍历 递归算法
{
if (root == NULL)
return 0;
else
{
Mid_Tree(root.left);
cout << root.data;
Mid_Tree(root.right);
}
}
template <class datatype>
datatype BTree_Link<datatype>::Las_Tree(TreeNode<datatype> *root) //后续遍历
{
if (root == NULL)
return 0;
else
{
Las_Tree(root.left);
Las_Tree(root.right);
cout<<root.data;
}
}
template<class datatype>
void BTree_Link<datatype>::Relse(TreeNode<datatype> * root) //删除节点
{
if (root != NULL)
{
Relse(root->left);
Relse(root->right);
delete root;
}
}
template<class datatype>
TreeNode<datatype> * BTree_Link<datatype>::Creat() //创建一颗二叉树
{
datatype ch;
TreeNode<datatype> *root;
cin>>ch;
if (ch =='#')
root = NULL;
else
{
root = new TreeNode<datatype>;
root->data = ch;
root->left = Creat();
root->right = Creat();
}
return root;
}
|