#include <iostream>
using namespace std;
template<class T>
struct TreeNode
{
T data;
TreeNode<T> *left, *right;
};
template<class T>
class BinaryTree
{
public:
BinaryTree(){ root = NULL; }
BinaryTree(const TreeNode<T>& tree);
~BinaryTree(){ destroy(root); }
void PreOrder(){ PreOrder(root); }
void Create(T x) { Create(root, x); } //建立二叉树
BinaryTree<T>& operator=(const BinaryTree<T>&);
private:
TreeNode<T> *root;
void PreOrder(TreeNode<T> *t);
void destroy(TreeNode<T> *t);
void Create(TreeNode<T>* &t, T x);
void copyTree(TreeNode<T>* &t, TreeNode<T>* t1);
};
template <class T>
BinaryTree<T>::BinaryTree(const TreeNode<T>& tree)
{
if(tree.root == NULL)
root = NULL;
else
copyTree(root, tree.root);
}
template<class T>
void BinaryTree<T>::PreOrder(TreeNode<T> *t)
{
if(t)
{
cout<<t->data<<" ";
PreOrder(t->left);
PreOrder(t->right);
}
}
template<class T>
void BinaryTree<T>::destroy(TreeNode<T> *t)
{
if(t)
{
destroy(t->left);
destroy(t->right);
delete t;
}
}
template<class T>
void BinaryTree<T>::Create(TreeNode<T>* &t, T x)
{ // 以先序序列输入各结点的数据,某结点的左子树或右子树为空时输入一个特定的值x。
T d;
cin >> d;
if (d == x) t=NULL;
else
{ t = new TreeNode<T> ;
t->data = d;
Create(t->left, x);
Create(t->right, x);
}
}
template <class T>
void BinaryTree<T>::copyTree(TreeNode<T>* &t, TreeNode<T>* t1)
{
if(t1 == NULL)
t = NULL;
else
{
t = new TreeNode<T>;
t->data = t1->data;
copyTree(t->left, t1->left);
copyTree(t->right, t1->right);
}
}
template<class T>
BinaryTree<T>& BinaryTree<T>::operator=(const BinaryTree<T>& tree)
{
if(this != &tree)
{
if(root != NULL) destroy(root);
if(tree.root == NULL)
root = NULL;
else
copyTree(root, tree.root);
}
return *this;
}
int main()
{
BinaryTree<int>::BinaryTree();
BinaryTree<int> b;
b.Create(0);
b.PreOrder();
return 0;
}
帮忙解析一下,最好是图解,这里前序建立二叉树是怎样建立的,以及末尾为0时没有左右子树,这里的0又是如何添加的,添加到哪,十分感谢谢。
为建立二叉树,将二叉树做如下处理:
将二叉树中每个结点的空指针引出一个虚结点,其值为一特定值如“#”,以标识其为空,这样处理后的二叉树称原二叉树的扩展二叉树
设二叉树中的结点均为一个字符,扩展二叉树的前序遍历序列由键盘输入,t为指向根结点的指针
建立二叉树的算法:
首先输入根结点
如果输入的是一个“#”字符,则表明该二叉树为空树,即t == NULL
否则输入的字符应该赋给t->data
之后依次递归建立其左子树和右子树