注：本文只是对学习清华殷人昆《数据结构（用面向对象方法与c++描述）》的人有些微帮助，其他人就没有必要浪费时间看了。因为老实说这本书里的代码实现的确不怎么样。
我的目的，就是努力实现和书里的代码相同的接口，尽最大可能和原代码一摸一样。因为这样的话，一则自己以后看起来比较方便，只要对着课本翻翻就行了；二则这样可能对别的学这本书的人有一定的好处。由于自己的习惯，我在原书的类名前加了_。
/*
Name: _BinaryTree.h
Copyright:
Author: elmar
Date: 19-07-03 23:43
Description:
*/
#ifndef _BinaryTree_H
#define _BinaryTree_H
#include <iostream>
#include <deque> //用于Insert中的层次遍历
using namespace std;
template <class Type> class _BinaryTree;
template <class Type> class _BinTreeNode
{
friend class _BinaryTree<Type>;
public:
_BinTreeNode():data(Type()), leftChild(NULL), rightChild(NULL){}
_BinTreeNode(Type item,
_BinTreeNode<Type>* left = NULL,
_BinTreeNode<Type>* right = NULL);
_BinTreeNode(const _BinTreeNode<Type>& b){*this = b;}
Type GetData() const {return data;}
_BinTreeNode<Type>* GetLeft() const {return leftChild;}
_BinTreeNode<Type>* GetRight() const {return rightChild;}
void SetData(const Type& item) {data = item;}
void SetLeft(_BinTreeNode<Type>* L) {leftChild = L;}
void SetRight(_BinTreeNode<Type>* R) {rightChild = R;}
_BinTreeNode<Type>& operator = (const _BinTreeNode<Type>& b);
private:
_BinTreeNode<Type> *leftChild, *rightChild;
Type data;
};
template <class Type> class _BinaryTree
{
public:
_BinaryTree(): root(NULL){}
_BinaryTree(Type value): RefValue(value), root(NULL){}
_BinaryTree(const _BinaryTree<Type>& bt);
virtual ~_BinaryTree(){destroy(root);}
virtual bool IsEmpty() {return root == NULL ? true : false;}
virtual _BinTreeNode<Type>* Parent(_BinTreeNode<Type>* current)
{return root == NULL || root == current ? NULL : Parent(root, current);}
virtual _BinTreeNode<Type>* LeftChild(_BinTreeNode<Type>* current)
{return root != NULL ? current->leftChild : NULL;}
virtual _BinTreeNode<Type>* RightChild(_BinTreeNode<Type>* current)
{return root != NULL ? current->rightChild : NULL;}
virtual int Insert(const Type& item){return Insert(root, item);}
// virtual int Find(const Type& item) const;
const _BinTreeNode<Type>* GetRoot() const {return root;}
_BinaryTree<Type>& operator = (const _BinaryTree<Type>&);
_BinaryTree<Type>& operator += (const _BinaryTree<Type>& bt){return Append(bt);}
friend istream& operator >> (istream& in, _BinaryTree<Type>& Tree)
{
Type item;
cout << "Construct binary tree: " << endl;
cout << "Input data (end with " << Tree.RefValue <<" ):";
in >> item;
while (item != Tree.RefValue)
{
Tree.Insert(item);
cout << "Input data (end with " << Tree.RefValue <<" ):";
in >> item;
}
return in;
}
friend ostream& operator << (ostream& out, _BinaryTree<Type>& Tree)
{
out << "Preorder traversal of binary tree." << endl;
Tree.Traverse(Tree.root, out);
out << endl;
return out;
}
private:
_BinTreeNode<Type>* root; //二叉数的根指针
Type RefValue; //数据输入停止的标志
_BinTreeNode<Type>* Parent(_BinTreeNode<Type>* start, _BinTreeNode<Type>* current);
int Insert(_BinTreeNode<Type>*& current, const Type& item); //操作成功返回0，否则-1
void Traverse(_BinTreeNode<Type>* current, ostream& out) const; //输出根为current的二叉树
// int Find(_BinTreeNode<Type>* current, const Type& item) const;
void destroy(_BinTreeNode<Type>* current);
_BinaryTree<Type>& Append(const _BinaryTree<Type>& bt); //为elmar所加的函数。把二叉树bt加到当前树上
};
template <class Type> _BinTreeNode<Type>::_BinTreeNode(Type item,
_BinTreeNode<Type>* left,
_BinTreeNode<Type>* right)
{
data = item;
leftChild = left;
rightChild = right;
}
template <class Type> _BinTreeNode<Type>& _BinTreeNode<Type>::operator = (const _BinTreeNode<Type>& b)
{
leftChild = b.leftChild; rightChild = b.rightChild; data = b.data;
return *this;
}
template <class Type> _BinaryTree<Type>::_BinaryTree(const _BinaryTree<Type>& bt)
{
root = NULL;
RefValue = bt.RefValue;
Append(bt);
}
template <class Type> void _BinaryTree<Type>::destroy(_BinTreeNode<Type>* current)
{
if (current !=NULL)
{
destroy(current->leftChild);
destroy(current->rightChild);
delete current;
}
}
template <class Type> _BinTreeNode<Type>*
_BinaryTree<Type>::Parent(_BinTreeNode<Type>* start, _BinTreeNode<Type>* current)
{
if (start == NULL) return NULL;
if (start->leftChild == current || start->rightChild == current) return start;
_BinTreeNode<Type>* p;
if ((p = Parent(start->leftChild, current)) != NULL) return p;
else return Parent(start->rightChild, current);
}
template <class Type> void
_BinaryTree<Type>::Traverse(_BinTreeNode<Type>* current, ostream& out) const
{
if (current != NULL)
{
out << current->data << ' ';
Traverse(current->leftChild, out);
Traverse(current->rightChild, out);
}
}
//层次遍历以current为根的二叉树，把item插入在第一个叶子的的左指针，
//或第一个缺右孩子的节点的右指针
template <class Type> int
_BinaryTree<Type>::Insert(_BinTreeNode<Type>*& current, const Type& item)
{
_BinTreeNode<Type>* p = new _BinTreeNode<Type>(item);
if (p == NULL) return -1;
if (current == NULL)
{
current = p;
return 0;
}
else
{
deque<_BinTreeNode<Type>*>* deck = new deque<_BinTreeNode<Type>*>;//队列
deck->push_back(current);
typename deque<_BinTreeNode<Type>*>::const_iterator iter;
while (true)
{
iter = deck->begin();
deck->pop_front();
if ((*iter)->leftChild == NULL)
{
(*iter)->leftChild = p;
delete deck;
return 0;
}
else if ((*iter)->rightChild == NULL)
{
(*iter)->rightChild = p;
delete deck;
return 0;
}
else
{
deck->push_back((*iter)->leftChild);
deck->push_back((*iter)->rightChild);
}
}
}
}
template <class Type> _BinaryTree<Type>& _BinaryTree<Type>::Append(const _BinaryTree<Type>& bt)
{
deque<_BinTreeNode<Type>*>* deck = new deque<_BinTreeNode<Type>*>;
deck->push_back(bt.root);
typename deque<_BinTreeNode<Type>*>::const_iterator iter;
while (!deck->empty())
{
iter = deck->begin();
deck->pop_front();
this->Insert((*iter)->GetData());
if ((*iter)->leftChild != NULL)
{
deck->push_back((*iter)->leftChild);
}
if ((*iter)->rightChild != NULL)
{
deck->push_back((*iter)->rightChild);
}
}//while
delete deck;
return *this;
}
template <class Type> _BinaryTree<Type>& _BinaryTree<Type>::operator = (const _BinaryTree<Type>& bt)
{
RefValue = bt.RefValue;
if (bt.root == NULL) return *this;
if (!this->IsEmpty())this->destroy(root);
return this->Append(bt);
}
#endif
