注：本文只是对学习清华殷人昆《数据结构（用面向对象方法与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
评论