问题描述

关于多叉树中 迭代器使用的问题

tree.h文件

 #include <iostream>
#include <list>
#include <algorithm>
using namespace std;  

struct TreeNode;
class Tree;
class Iterator;
typedef list<TreeNode*> List; 

TreeNode* clone(TreeNode*,List&,TreeNode*);

struct TreeNode{
   int _data;
   TreeNode* _parent;
   List _children;
   TreeNode(int,TreeNode*);
   void SetParent(TreeNode&);
   void InsertChildren(TreeNode&);
};  

class Tree{
public:  

   Tree();
   Tree(const Tree&);
   Tree(const int);
   Tree(const int,const list<Tree*>&);
   ~Tree();
   Tree& operator=(const Tree&);
   bool operator==(const Tree&);
   bool operator!=(const Tree&);      

   void Clear();
   bool IsEmpty()const;
   int Size()const;
   int Leaves();
   int Root()const;
   int Height();                      

   static bool IsRoot(Iterator);
   static bool isLeaf(Iterator);
   static Iterator Parent(Iterator);
   static int NumChildren(Iterator); 

   Iterator begin();
   Iterator end();
   friend class Iterator;
private:
   list<TreeNode*> _nodes;
   list<TreeNode*>::iterator LIt;
   int height(TreeNode*);
   int level(TreeNode*,Iterator);
};  

class Iterator{
   private:
    Tree* _tree;
    list<TreeNode*>::iterator _lit;
   public:
    Iterator();
    Iterator(const Iterator&);
    Iterator(Tree*,TreeNode*);
    Iterator(Tree*,list<TreeNode*>::iterator);
    void operator=(const Iterator&);
    bool operator==(const Iterator&);
    bool operator!=(const Iterator&);
    Iterator& operator++();
    Iterator operator++(int);
    int operator*()const;
    bool operator!();            

    typedef list<TreeNode*>::iterator List;
    friend class Tree;
};  

tree.cpp文件

 #include "tree.h"

TreeNode::TreeNode(int type= 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(const int type)
{
 _nodes.push_back(new TreeNode(type));
}

Tree::Tree(const Tree& t)
{
 if(t._nodes.empty())return;
 clone(t._nodes.front(),_nodes,0);
}

Tree::Tree(const int type,const list<Tree*>& lit)
{
 TreeNode* root = new TreeNode(type);
 _nodes.push_back(root);
 list<Tree*>::const_iterator it;
 for(it = lit.begin();it!=lit.end();it++){
 if(!((*it)->_nodes.empty())){
   Tree* tp = new Tree(**it);
   TreeNode* p = tp->_nodes.front();
   root->_children.push_back(p);
   p->_parent = root;
   list<TreeNode*>::iterator lit1 = tp->_nodes.begin();
   list<TreeNode*>::iterator lit2 = tp->_nodes.end();
   list<TreeNode*>::iterator lit3 = _nodes.end();
   _nodes.insert(lit3,lit1,lit2);
 }
 }
}

Tree::~Tree()
{
 for(list<TreeNode*>::iterator it = _nodes.begin();it!=_nodes.end();it++){
 delete* it;
 }
}

Tree& Tree::operator =(const Tree & t)
{
 Clear();
 Tree* p = new Tree(t);
 _nodes = p->_nodes;
 return *this;
}

bool Tree::operator ==(const Tree& t)
{
 if(_nodes.size()!=t._nodes.size()){
 return false;
 }
 list<TreeNode*>::iterator it = _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;
}

bool Tree::operator !=(const Tree& t)
{
 if(_nodes.size()!=_nodes.size()){
 return true;
 }
 else{
 list<TreeNode*>::iterator it = _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*>::iterator it = _nodes.begin();it!=_nodes.end();it++){
 delete* it;
 }
 _nodes.clear();
}

bool Tree::IsEmpty()const
{
 return _nodes.empty();
}

int Tree::Size()const
{
 return (int)_nodes.size();
}

int Tree::Leaves()
{
 int i = 0;
 list<TreeNode*>::iterator it = _nodes.begin();
 while(it!=_nodes.end()){
 if((*it)->_children.size()==0){
   i++;
 }
 it++;
 }
 return i;
}

int Tree::Height()
{
 if(_nodes.size()!=0){
 TreeNode* TNode = _nodes.front();
 return height(TNode);
 }
 else{
 return -1;
 }
}

int Tree::height(TreeNode* node)
{
 if(!node){
 return -1;
 }
 else{
 list<TreeNode*> plist = node->_children;
 if(plist.size()==0){
   return 0;
 }
 int hA = 0;
 for(list<TreeNode*>::iterator it = plist.begin();it!=plist.end();it++){
  int hB = height(*it);
   if(hB>hA){
    hA = hB;
   }
 }
 return hA+1;
 }
}

Iterator Tree::begin()
{
 return Iterator(this,_nodes.begin());
}

Iterator Tree::end()
{
 return Iterator(this,_nodes.end());
}

int Tree::Root()const
{
 return (*_nodes.begin())->_data;
}

bool Tree::IsRoot(Iterator it)
{
 TreeNode p = *it;
 if(p._parent == 0){
 return true;
 }
 return false;
}

bool Tree::isLeaf(Iterator it)
{
 TreeNode p = *it;
 if(p._children.size() == 0){
 return true;
 }
 return false;
}

Iterator Tree::Parent(Iterator it)
{
 TreeNode p = *it;
 Tree* t = it._tree;
 Iterator Ite(t,p._parent);
 return Ite;
}

int Tree::NumChildren(Iterator it)
{
 TreeNode p = *it;
 return (int)p._children.size();
}

Iterator::Iterator()
{
}

Iterator::Iterator(const Iterator& 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*>::iterator lt)
{
 _tree = t;
 _lit = lt;
}

void Iterator::operator =(const Iterator& it)
{
 _tree = it._tree;
 _lit = it._lit;
}

bool Iterator::operator ==(const Iterator & it)
{
 return _tree == it._tree && _lit == it._lit;
}

bool Iterator::operator !=(const Iterator & it)
{
 return _tree != it._tree || _lit != it._lit;
}

Iterator& Iterator::operator ++()
{
 ++_lit;
 return *this;
}

Iterator Iterator::operator ++(int)
{
 Iterator it(*this);
 ++_lit;
 return it;
}

int Iterator::operator *() const
{
 return ((*_lit)->_data);
}

bool Iterator::operator !()
{
 return _lit == _tree->_nodes.end();
}

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*>::iterator lt = l.begin();lt!=l.end();lt++){
 cl.push_back(clone(*lt,nodes,cp));
 }
 return cp;
}

编译后，这里报错
tree.cpp: In static member function static bool Tree::IsRoot(Iterator)?
tree.cpp:189: error: conversion from int?to non-scalar type TreeNode?requested
tree.cpp: In static member function static bool Tree::isLeaf(Iterator)?
tree.cpp:198: error: conversion from int?to non-scalar type TreeNode?requested
tree.cpp: In static member function static Iterator Tree::Parent(Iterator)?
tree.cpp:207: error: conversion from 鈏nt?to non-scalar type 釺reeNode?requested
tree.cpp: In static member function 鈙tatic int Tree::NumChildren(Iterator)?
tree.cpp:216: error: conversion from int?to non-scalar type TreeNode?requested

为什么会这样报错，应该怎么改正？