S.l.e!ep.￠%

C++樹(shù)的實(shí)現(xiàn) 收藏
C++樹(shù)的實(shí)現(xiàn)
STL里面沒(méi)有提供容器樹(shù)的模板實(shí)現(xiàn)，從網(wǎng)上找到一個(gè)：
?
Tree.h
//tree.h 頭文件
?
#include <list>
#include <algorithm>
using namespace std;
?
struct TreeNode; //定義一個(gè)結(jié)構(gòu)體原形
classTree;????? //定義一個(gè)類原形
classIterator; //定義一個(gè)類原形
typedef list<TreeNode*> List; //重命名一個(gè)節(jié)點(diǎn)鏈表
?
TreeNode* clone(TreeNode*,List&,TreeNode*);//Clone復(fù)制函數(shù)
?
struct TreeNode{
?? int_data;????????????????? //數(shù)據(jù)
?? TreeNode* _parent;????????? //父節(jié)點(diǎn)
?? List_children;???????????? //子節(jié)點(diǎn)
?? TreeNode(int,TreeNode*);??? //構(gòu)造函數(shù)
?? void SetParent(TreeNode&); //設(shè)置父節(jié)點(diǎn)
?? void InsertChildren(TreeNode&); //插入子節(jié)點(diǎn)
};
?
classTree{
public:
?
?//下面是構(gòu)造器和運(yùn)算符重載
?? Tree();??????????????????????????? //默認(rèn)構(gòu)造函數(shù)
?? Tree(constTree&);???????????????? //復(fù)制構(gòu)造函數(shù)
?? Tree(constint);?????????????????? //帶參數(shù)構(gòu)造函數(shù)
?? Tree(constint,constlist<Tree*>&);//帶參數(shù)構(gòu)造函數(shù)
?? ~Tree();?????????????????????????? //析構(gòu)函數(shù)
?? Tree& operator=(constTree&);????? //=符號(hào)運(yùn)算符重載
?? bool operator==(constTree&);????? //==符號(hào)運(yùn)算符重載
?? bool operator!=(constTree&);????? //!=符號(hào)運(yùn)算符重載
?
?? //下面是成員函數(shù)
?? void Clear();????????????????????? //清空
?? boolIsEmpty()const;?????????????? //判斷是否為空
?? intSize()const;?????????????????? //計(jì)算節(jié)點(diǎn)數(shù)目
?? intLeaves();????????????????????? //計(jì)算葉子數(shù)
?? intRoot()const;?????????????????? //返回根元素
?? intHeight();????????????????????? //計(jì)算樹(shù)的高度
?
?
?? //下面是靜態(tài)成員函數(shù)
? static boolIsRoot(Iterator);???? //判斷是否是根
?? static boolisLeaf(Iterator);???? //判斷是否是葉子
?? static IteratorParent(Iterator); //返回其父節(jié)點(diǎn)
?? static intNumChildren(Iterator); //返回其子節(jié)點(diǎn)數(shù)目
?
?? //跌代器函數(shù)
?? Iteratorbegin();????????????????? //Tree Begin
?? Iteratorend();??????????????????? //Tree End
?? friend classIterator;???????????? //Iterator SubClass
private:
?? list<TreeNode*> _nodes;???????? //節(jié)點(diǎn)數(shù)組
?? list<TreeNode*>::iteratorLIt; //一個(gè)節(jié)點(diǎn)迭代器
?? intheight(TreeNode*);
?? intlevel(TreeNode*,Iterator);
};
?
//This is TreeSub Class Iterator
classIterator{
?? private:
??? Tree* _tree;???????????????????? //Tree data
??? list<TreeNode*>::iterator_lit; //List Iterator
?? public:
??? Iterator();?????????????????????????????? //默認(rèn)構(gòu)造函數(shù)
??? Iterator(constIterator&);??????????????? //復(fù)制構(gòu)造函數(shù)
??? Iterator(Tree*,TreeNode*);??????????????? //構(gòu)造函數(shù)
??? Iterator(Tree*,list<TreeNode*>::iterator);//構(gòu)造函數(shù)
??? //運(yùn)算符重載
??? void operator=(constIterator&);????????? //賦值運(yùn)算符重載
??? bool operator==(constIterator&);???????? //關(guān)系運(yùn)算符重載
??? bool operator!=(constIterator&);???????? //關(guān)系運(yùn)算符重載
??? Iterator& operator++();?????????????????? //前綴++運(yùn)算符
??? Iterator operator++(int);???????????????? //后綴++運(yùn)算符
??? int operator*()const;???????????????????? //獲得節(jié)點(diǎn)信息
??? bool operator!();???????????????????????? //賦值運(yùn)算符重載
??
??? typedef list<TreeNode*>::iteratorList;
??? friend classTree;
};
?
Tree.cpp
//tree.cpp 實(shí)現(xiàn)文件
?
#include "Tree.h"
?
//***** 下面是對(duì)于TreeNode結(jié)構(gòu)體的定義實(shí)現(xiàn)*****///
?
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);
}
?
?
?
//***** 下面是對(duì)于Tree類的定義實(shí)現(xiàn)*****///
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);//建立根節(jié)點(diǎn)
?_nodes.push_back(root);//放入樹(shù)中
?list<Tree*>::const_iteratorit;
?for(it = lit.begin();it!=lit.end();it++){
?if(!((*it)->_nodes.empty())){//如果當(dāng)前節(jié)點(diǎn)元素不為空
?? Tree* tp = newTree(**it);
?? TreeNode* p = tp->_nodes.front();
?? root->_children.push_back(p); //設(shè)置根的子節(jié)點(diǎn)
?? p->_parent = root;??????????? //設(shè)置節(jié)點(diǎn)的父節(jié)點(diǎn)為根
?? 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; //判斷為空樹(shù)
?}
}
?
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();
}
?
//***** 下面是對(duì)于Tree::Iterator類的定義實(shí)現(xiàn)*****///
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函數(shù)
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;
}

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/stephenxu111/archive/2008/05/14/2446382.aspx