?C++樹的實現
STL里面沒有提供容器樹的模板實現，自已寫一個：
Tree.h
//tree.h 頭文件 #include <list> #include <algorithm> using namespace std; struct TreeNode; //定義一個結構體原型 classTree; //定義一個類原型 classIterator; //定義一個類原型 typedef list<TreeNode*> List; //重命名一個節點鏈表 TreeNode* clone(TreeNode*,List&,TreeNode*);//Clone復制函數 struct TreeNode{ int_data; //數據 TreeNode* _parent; //父節點 List_children; //子節點 TreeNode(int,TreeNode*); //構造函數 void SetParent(TreeNode&); //設置父節點 void InsertChildren(TreeNode&); //插入子節點 }; classTree{ public: //下面是構造器和運算符重載 Tree(); //默認構造函數 Tree(constTree&); //復制構造函數 Tree(constint); //帶參數構造函數 Tree(constint,constlist<Tree*>&);//帶參數構造函數 ~Tree(); //析構函數 Tree& operator=(constTree&); //=符號運算符重載 bool operator==(constTree&); //==符號運算符重載 bool operator!=(constTree&); //!=符號運算符重載 //下面是成員函數 void Clear(); //清空 boolIsEmpty()const; //判斷是否為空 intSize()const; //計算節點數目 intLeaves(); //計算葉子數 intRoot()const; //返回根元素 intHeight(); //計算樹的高度 //下面是靜態成員函數 static boolIsRoot(Iterator); //判斷是否是根 static boolisLeaf(Iterator); //判斷是否是葉子 static IteratorParent(Iterator); //返回其父節點 static intNumChildren(Iterator); //返回其子節點數目 //跌代器函數 Iteratorbegin(); //Tree Begin Iteratorend(); //Tree End friend classIterator; //Iterator SubClass private: list<TreeNode*> _nodes; //節點數組 list<TreeNode*>::iteratorLIt; //一個節點迭代器 intheight(TreeNode*); intlevel(TreeNode*,Iterator); }; //This is TreeSub Class Iterator classIterator{ private: Tree* _tree; //Tree data list<TreeNode*>::iterator_lit; //List Iterator public: Iterator(); //默認構造函數 Iterator(constIterator&); //復制構造函數 Iterator(Tree*,TreeNode*); //構造函數 Iterator(Tree*,list<TreeNode*>::iterator);//構造函數 //運算符重載 void operator=(constIterator&); //賦值運算符重載 bool operator==(constIterator&); //關系運算符重載 bool operator!=(constIterator&); //關系運算符重載 Iterator& operator++(); //前綴++運算符 Iterator operator++(int); //后綴++運算符 int operator*()const; //獲得節點信息 bool operator!(); //賦值運算符重載 typedef list<TreeNode*>::iteratorList; friend classTree; }; ?
Tree.cpp
//tree.cpp 實現文件 #include "Tree.h" //***** 下面是對于TreeNode結構體的定義實現*****/// TreeNode::TreeNode(inttype= 0,TreeNode* Parent = 0){ _data = type; _parent = Parent; } void TreeNode::SetParent(TreeNode& node){ _parent = &node; } void TreeNode::InsertChildren(TreeNode& node){ TreeNode* p = &node; _children.push_back(p); } //***** 下面是對于Tree類的定義實現*****/// Tree::Tree(){ } Tree::Tree(constinttype){ _nodes.push_back(new TreeNode(type)); } Tree::Tree(constTree& t){ if(t._nodes.empty())return; clone(t._nodes.front(),_nodes,0); } Tree::Tree(constinttype,constlist<Tree*>& lit){ TreeNode* root = new TreeNode(type);//建立根節點 _nodes.push_back(root);//放入樹中 list<Tree*>::const_iteratorit; for(it = lit.begin();it!=lit.end();it++){ if(!((*it)->_nodes.empty())){//如果當前節點元素不為空 Tree* tp = newTree(**it); TreeNode* p = tp->_nodes.front(); root->_children.push_back(p); //設置根的子節點 p->_parent = root; //設置節點的父節點為根 list<TreeNode*>::iteratorlit1 = tp->_nodes.begin(); list<TreeNode*>::iteratorlit2 = tp->_nodes.end(); list<TreeNode*>::iteratorlit3 = _nodes.end(); _nodes.insert(lit3,lit1,lit2); } } } Tree::~Tree(){ for(list<TreeNode*>::iteratorit = _nodes.begin();it!=_nodes.end();it++){ delete* it; } } Tree& Tree::operator =(constTree & t){ Clear(); Tree* p = newTree(t); _nodes = p->_nodes; return *this; } boolTree::operator ==(constTree& t){ if(_nodes.size()!=t._nodes.size()){ return false; } list<TreeNode*>::iteratorit = _nodes.begin(); list<TreeNode*>::const_iterator_it = t._nodes.begin(); while(it!=_nodes.end()&&_it!=t._nodes.end()){ if((*it)->_data!=(*_it)->_data){ return false; } it++; _it++; } return true; } boolTree::operator !=(constTree& t){ if(_nodes.size()!=_nodes.size()){ return true; } else{ list<TreeNode*>::iteratorit = _nodes.begin(); list<TreeNode*>::const_iterator_it = t._nodes.begin(); while(it!=_nodes.end()&&_it!=t._nodes.end()){ if((*it)->_data!=(*_it)->_data){ return true; } it++; _it++; } return false; } } void Tree::Clear(){ for(list<TreeNode*>::iteratorit = _nodes.begin();it!=_nodes.end();it++){ delete* it; } _nodes.clear(); } boolTree::IsEmpty()const{ return _nodes.empty(); } intTree::Size()const{ return (int)_nodes.size(); } intTree::Leaves(){ inti = 0; list<TreeNode*>::iteratorit = _nodes.begin(); while(it!=_nodes.end()){ if((*it)->_children.size()==0){ i++; } it++; } return i; } intTree::Height(){ if(_nodes.size()!=0){ TreeNode* TNode = _nodes.front(); return height(TNode); } else{ return -1; //判斷為空樹 } } intTree::height(TreeNode* node){ if(!node){ return -1; } else{ list<TreeNode*> plist = node->_children; if(plist.size()==0){ return 0; } inthA = 0; for(list<TreeNode*>::iteratorit = plist.begin();it!=plist.end();it++){ inthB = height(*it); if(hB>hA){ hA = hB; } } return hA+1; } } IteratorTree::begin(){ return Iterator(this,_nodes.begin()); } IteratorTree::end(){ return Iterator(this,_nodes.end()); } intTree::Root()const{ return (*_nodes.begin())->_data; } boolTree::IsRoot(Iteratorit){ TreeNode p = *it; if(p._parent == 0){ return true; } return false; } boolTree::isLeaf(Iteratorit){ TreeNode p = *it; if(p._children.size() == 0){ return true; } return false; } IteratorTree::Parent(Iteratorit){ TreeNode p = *it; Tree* t = it._tree; IteratorIte(t,p._parent); return Ite; } intTree::NumChildren(Iteratorit){ TreeNode p = *it; return (int)p._children.size(); } //***** 下面是對于Tree::Iterator類的定義實現*****/// Iterator::Iterator(){ } Iterator::Iterator(constIterator& it){ _tree = it._tree; _lit = it._lit; } Iterator::Iterator(Tree* t, TreeNode* n){ _tree = t; list<TreeNode*>& nodes = _tree->_nodes; _lit = find(nodes.begin(),nodes.end(),n);//<algorithm> Members } Iterator::Iterator(Tree * t, list<TreeNode*>::iteratorlt){ _tree = t; _lit = lt; } void Iterator::operator =(constIterator& it){ _tree = it._tree; _lit = it._lit; } boolIterator::operator ==(constIterator & it){ return _tree == it._tree && _lit == it._lit; } boolIterator::operator !=(constIterator & it){ return _tree != it._tree || _lit != it._lit; } Iterator& Iterator::operator ++(){ ++_lit; return *this; } IteratorIterator::operator ++(int){ Iteratorit(*this); ++_lit; return it; } intIterator::operator *() const{ return ((*_lit)->_data); } boolIterator::operator !(){ return _lit == _tree->_nodes.end(); } //Clone函數 TreeNode* clone(TreeNode* node,List& nodes,TreeNode* nodep){ TreeNode* cp = new TreeNode(node->_data,nodep); nodes.push_back(cp); List& l = node->_children; List& cl = cp->_children; for(list<TreeNode*>::iteratorlt = l.begin();lt!=l.end();lt++){ cl.push_back(clone(*lt,nodes,cp)); } return cp; }?
)
