C++樹的實現 收藏
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;
}

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/stephenxu111/archive/2008/05/14/2446382.aspx