1. 首页
  2. 问答
  3. 试图制作一个模板递归树打印机

试图制作一个模板递归树打印机

2010-10-11 54 views
2

我想为模板类树做一个递归树打印机，以便它可以打印树，而不必事先知道那里的数据类型。但我无法弄清楚我需要的语法。试图制作一个模板递归树打印机

现在我知道代码只会打印树的根，但我甚至无法做到这一点。

想法？

编辑：

这里的编译器错误消息：

test.cpp(8) : error C2079: 'tempValue' uses undefined class 'Object' 
test.cpp(9) : error C2228: left of '.retrieve' must have class/struct/union 
     type is 'HWTreeItr<Object> *' 
     with 
     [ 
      Object=Object 
     ] 
     did you intend to use '->' instead? 
test.cpp(27) : error C2664: 'print_tree' : cannot convert parameter 1 from 'HWTreeItr<Object>' to 'HWTreeItr<Object> *' 
     with 
     [ 
      Object=char 
     ] 
     and 
     [ 
      Object=Object 
     ] 
     No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called

HWTreeOriginal.h

/*==================================================================== 

    Tree data structure 

    Tree points to a single TreeNode that acts as the root --> no siblings 

    TreeNodes points to child TreeNode and to sibling TreeNod 

    ====================================================================*/ 

#ifndef HWTREE_H 
#define HWTREE_H 

#include <list> 

using namespace std; 

/* ================================================================ 

Class Declarations 

/================================================================ */ 

template <class Object> 
class HWTree; 

template <class Object> 
class HWTreeItr; 

/* ------------------------------------------------------- 
TreeNode -- used internally 
    ------------------------------------------------------- */ 
template <class Object> 
class HWTreeNode 
{ 
private: 
    HWTreeNode(const Object & element=Object(), HWTreeNode* child=NULL, HWTreeNode* sibling=NULL); 
~HWTreeNode(); 

    Object m_element; 
HWTreeNode* m_first_child; 
HWTreeNode* m_next_sibling; 

    friend class HWTree<Object>; 
    friend class HWTreeItr<Object>; 
}; 

/* ------------------------------------------------------- 
Tree - used with TreeItr 
    ------------------------------------------------------- */ 
template <class Object> 
class HWTree 
{ 
public: 
// constructors 
HWTree(const Object& initial_element); 
~HWTree(); 

// accessors 
    HWTreeItr<Object> get_root(); 

//mutators 
void add_child(const Object& obj, const HWTreeItr<Object>& itr); 
void add_sibling(const Object& obj, const HWTreeItr<Object>& itr); 
void remove_left_child(const HWTreeItr<Object>& itr); 

private: 
HWTreeNode<Object>* m_root; 
}; 


/* ------------------------------------------------------- 
TreeItr class; maintains "current position" in Tree 
    ------------------------------------------------------- */ 
template <class Object> 
class HWTreeItr 
{ 
public: 
// constructor 
    HWTreeItr(); 
// accessors 
    bool retrieve(Object & result) const; 
// mutators 
void next_sibling(); 
void child(); 
bool isPastEnd() const; 
    friend class HWTreeNode<Object>; 

private: 
HWTreeNode<Object>* m_current; 
    friend class HWTree<Object>; 
}; 



/* ================================================================ 

Tree Node Class Code 

/================================================================ */ 
template <class Object> 
HWTreeNode<Object>::HWTreeNode(const Object & element=Object(), HWTreeNode* child=NULL, HWTreeNode* sibling=NULL) 
: m_element(element), m_first_child(child), m_next_sibling(sibling) 
{ } 

template <class Object> 
HWTreeNode<Object>::~HWTreeNode() 
{ 
if (m_first_child != NULL) 
    delete m_first_child; 
if (m_next_sibling != NULL) 
    delete m_next_sibling; 
} 

/* ================================================================ 

Tree Code 

    ================================================================ */ 
template <class Object> 
HWTree<Object>::HWTree(const Object& initial_element) 
{ 
    m_root = new HWTreeNode<Object>(initial_element); // create TreeNode 
} 

template <class Object> 
HWTree<Object>::~HWTree() 
{ 
delete m_root; 
} 


/* ================================================================ 

TreeItr Code 

    ================================================================ */ 
/** 
* Return an iterator representing the first node in the list. 
* This operation is valid for empty lists. 
*/ 
template <class Object> 
HWTreeItr<Object> HWTree<Object>::get_root() 
{ 
HWTreeItr<Object> itr; 
itr.m_current = m_root; 
return itr; 
} 

template <class Object> 
void HWTree<Object>::add_child(const Object& obj, const HWTreeItr<Object>& itr) 
{ 
if (itr.m_current != NULL) 
{ 
    HWTreeNode<Object>* pNew = new HWTreeNode<Object>(obj, NULL); // 1) new node without children 
    pNew->m_next_sibling = itr.m_current->m_first_child; // 2) hook into exising children 
    itr.m_current->m_first_child = pNew; 
} 
} 

template <class Object> 
void HWTree<Object>::add_sibling(const Object& obj, const HWTreeItr<Object>& itr) 
{ 
if (itr.m_current != NULL) 
{ 
    HWTreeNode<Object>* pNew = new HWTreeNode<Object>(obj, NULL); // 1) new node without children 
    pNew->m_next_sibling = itr.m_current->m_next_sibling; // 2) hook into exising children 
    itr.m_current->m_next_sibling = pNew; 
} 
} 

template <class Object> 
void HWTree<Object>::remove_left_child(const HWTreeItr<Object>& itr) 
{ 
return; 
} 



/* ================================================================ 

Class: Tree Iterator 

/================================================================ */ 
template <class Object> 
HWTreeItr<Object>::HWTreeItr() : m_current(NULL) 
{} 

template <class Object> 
bool HWTreeItr<Object>::isPastEnd() const 
{ 
if (m_current == NULL) 
    return true; 
else 
    return false; 
} 

template <class Object> 
bool HWTreeItr<Object>::retrieve(Object & result) const 
{ 
if (m_current != NULL) // bug: _current != ____.end() but where to get a list 
{ 
    HWTreeNode<Object>* pNode = m_current; 
    if (pNode != NULL) // another attemp to catch crash 
    result = pNode->m_element; 
    return true; 
} else 
    return false; 
} 

template <class Object> 
void HWTreeItr<Object>::next_sibling() 
{ 
if (m_current != NULL) 
    m_current = m_current->m_next_sibling; 
} 


template <class Object> 
void HWTreeItr<Object>::child() 
{ 
if (m_current != NULL) 
    m_current = m_current->m_first_child; 
} 



#endif

TEST.CPP

#include "HWTreeOriginal.h" 
#include <iostream> 
#include <string> 
using namespace std; 

void print_tree(HWTreeItr<class Object>* currentItr, int level=0) 
{ 
    Object tempValue; 
    currentItr.retrieve(tempValue); 
    cout << string(level, ' ') << tempValue; 
} 

int main() 
{ 
    HWTree<char> myTree('A'); 
    HWTreeItr<char> myItr = myTree.get_root(); 
    HWTreeItr<char> tempItr; 

    myTree.add_child('B', myItr); 
    myItr.child(); 
    tempItr=myItr; 
    myTree.add_sibling('C', myItr); 
    myItr.next_sibling(); 
    myTree.add_sibling('D', myItr); 

    myItr=myTree.get_root(); 
    print_tree((HWTreeItr<char>)myItr, 0); 
    return 0; 
}

来源

2010-10-11 Dark Nation

+0

你能解释，而不是发生了什么？这里有很多代码，所以知道它是编译还是运行时错误会有所帮助。 – Gretchen 2010-10-11 16:38:03

+0

如果您收到错误信息或有问题，请告诉我们*这些错误信息是什么或者您有什么问题。 “我无法工作”并不能帮助诊断问题。 – sth 2010-10-11 16:39:05

+0

你可能和[这个人]在同一个班级（http://stackoverflow.com/questions/3899636/how-can-i-print-a-binary-tree-search-class-vertically）？ – sbi 2010-10-11 17:15:37

回答

0

乍一看，您的print_tree函数似乎期望指向HWTreeItr<Object>, 的指针，其中Object类似乎没有被定义。你想要一个模板版本print_tree？

如何：。

template <typename Object> 
void print_tree(HWTreeItr<Object>& const currentItr, int level=0) 
{ 
    Object tempValue; 
    currentItr.retrieve(tempValue); 
    cout << string(level, ' ') << tempValue; 
}

（编辑 - 我留在参数列表中的<class Object>应该只是<Object>

来源

2010-10-11 16:43:01 Gretchen

+0

如果我使用这个，我得到： – 2010-10-11 16:51:29

+0

test.cpp（7）：错误C2649：'typename'：不是'class' – 2010-10-11 16:51:56

+0

'HWTreeItr ＆const'应该是'HWTreeItr ＆const' – Vinzenz 2010-10-11 17:06:36

0

首先，我不得不修复树实现，它实际上是编译的定义的方法或函数可能没有默认参数如果你已经声明它们

在这种情况下，这是你的构造函数

/*==================================================================== 

    Tree data structure 

    Tree points to a single TreeNode that acts as the root --> no siblings 

    TreeNodes points to child TreeNode and to sibling TreeNod 

====================================================================*/ 

#ifndef HWTREE_H 
#define HWTREE_H 

// #include <list> unnecessary include 
// using namespace std; => Really bad never do this in a header 

/* ================================================================ 

Class Declarations 

/================================================================ */ 

template <class Object> 
class HWTree; 

template <class Object> 
class HWTreeItr; 

/* ------------------------------------------------------- 
TreeNode -- used internally 
    ------------------------------------------------------- */ 
template <class Object> 
class HWTreeNode 
{ 
private: 
    HWTreeNode(const Object & element=Object(), HWTreeNode* child=NULL, HWTreeNode* sibling=NULL); 
~HWTreeNode(); 

    Object m_element; 
HWTreeNode* m_first_child; 
HWTreeNode* m_next_sibling; 

    friend class HWTree<Object>; 
    friend class HWTreeItr<Object>; 
}; 

/* ------------------------------------------------------- 
Tree - used with TreeItr 
    ------------------------------------------------------- */ 
template <class Object> 
class HWTree 
{ 
public: 
// constructors 
HWTree(const Object& initial_element); 
~HWTree(); 

// accessors 
    HWTreeItr<Object> get_root(); 

//mutators 
void add_child(const Object& obj, const HWTreeItr<Object>& itr); 
void add_sibling(const Object& obj, const HWTreeItr<Object>& itr); 
void remove_left_child(const HWTreeItr<Object>& itr); 

private: 
HWTreeNode<Object>* m_root; 
}; 


/* ------------------------------------------------------- 
TreeItr class; maintains "current position" in Tree 
    ------------------------------------------------------- */ 
template <class Object> 
class HWTreeItr 
{ 
public: 
// constructor 
    HWTreeItr(); 
// accessors 
    bool retrieve(Object & result) const; 
// mutators 
void next_sibling(); 
void child(); 
bool isPastEnd() const; 
    friend class HWTreeNode<Object>; 

private: 
HWTreeNode<Object>* m_current; 
    friend class HWTree<Object>; 
}; 



/* ================================================================ 

Tree Node Class Code 
* Removed all default arguments from it as this is not allowed 
================================================================ */ 
template <class Object> 
HWTreeNode<Object>::HWTreeNode(const Object & element, HWTreeNode* child, HWTreeNode* sibling) 
: m_element(element), m_first_child(child), m_next_sibling(sibling) 
{ } 

template <class Object> 
HWTreeNode<Object>::~HWTreeNode() 
{ 
if (m_first_child != NULL) 
    delete m_first_child; 
if (m_next_sibling != NULL) 
    delete m_next_sibling; 
} 

/* ================================================================ 

Tree Code 

    ================================================================ */ 
template <class Object> 
HWTree<Object>::HWTree(const Object& initial_element) 
{ 
    m_root = new HWTreeNode<Object>(initial_element); // create TreeNode 
} 

template <class Object> 
HWTree<Object>::~HWTree() 
{ 
delete m_root; 
} 


/* ================================================================ 

TreeItr Code 

    ================================================================ */ 
/** 
* Return an iterator representing the first node in the list. 
* This operation is valid for empty lists. 
*/ 
template <class Object> 
HWTreeItr<Object> HWTree<Object>::get_root() 
{ 
HWTreeItr<Object> itr; 
itr.m_current = m_root; 
return itr; 
} 

template <class Object> 
void HWTree<Object>::add_child(const Object& obj, const HWTreeItr<Object>& itr) 
{ 
if (itr.m_current != NULL) 
{ 
    HWTreeNode<Object>* pNew = new HWTreeNode<Object>(obj, NULL); // 1) new node without children 
    pNew->m_next_sibling = itr.m_current->m_first_child; // 2) hook into exising children 
    itr.m_current->m_first_child = pNew; 
} 
} 

template <class Object> 
void HWTree<Object>::add_sibling(const Object& obj, const HWTreeItr<Object>& itr) 
{ 
if (itr.m_current != NULL) 
{ 
    HWTreeNode<Object>* pNew = new HWTreeNode<Object>(obj, NULL); // 1) new node without children 
    pNew->m_next_sibling = itr.m_current->m_next_sibling; // 2) hook into exising children 
    itr.m_current->m_next_sibling = pNew; 
} 
} 

template <class Object> 
void HWTree<Object>::remove_left_child(const HWTreeItr<Object>& itr) 
{ 
return; 
} 



/* ================================================================ 

Class: Tree Iterator 

/================================================================ */ 
template <class Object> 
HWTreeItr<Object>::HWTreeItr() : m_current(NULL) 
{} 

template <class Object> 
bool HWTreeItr<Object>::isPastEnd() const 
{ 
if (m_current == NULL) 
    return true; 
else 
    return false; 
} 

template <class Object> 
bool HWTreeItr<Object>::retrieve(Object & result) const 
{ 
if (m_current != NULL) // bug: _current != ____.end() but where to get a list 
{ 
    HWTreeNode<Object>* pNode = m_current; 
    if (pNode != NULL) // another attemp to catch crash 
    result = pNode->m_element; 
    return true; 
} else 
    return false; 
} 

template <class Object> 
void HWTreeItr<Object>::next_sibling() 
{ 
if (m_current != NULL) 
    m_current = m_current->m_next_sibling; 
} 


template <class Object> 
void HWTreeItr<Object>::child() 
{ 
if (m_current != NULL) 
    m_current = m_current->m_first_child; 
} 

#endif

现在你的主：

#include "HWTreeOriginal.h" 
#include <iostream> 
#include <string> 
using namespace std; // Bad practise 

// This is how this needs to look like 
template< typename Object > 
void print_tree(HWTreeItr<Object> & currentItr, int level=0) 
{ 
    Object tempValue; 
    currentItr.retrieve(tempValue); 
    cout << string(level, ' ') << tempValue; 
} 

int main() 
{ 
    HWTree<char> myTree('A'); 
    HWTreeItr<char> myItr = myTree.get_root(); 
    HWTreeItr<char> tempItr; 

    myTree.add_child('B', myItr); 
    myItr.child(); 
    tempItr=myItr; 
    myTree.add_sibling('C', myItr); 
    myItr.next_sibling(); 
    myTree.add_sibling('D', myItr); 

    myItr=myTree.get_root(); 
    // Do not use C-Casts like you did before, it did not help anyway as you noticed. 
    print_tree(myItr, 0); 
    return 0; 
}

来源

2010-10-11 16:44:17 Vinzenz

+0

那么我没有实现你的遍历，因为我希望你能从这里找到你的方式;-)你也需要通过这样做学到一些东西:-) – Vinzenz 2010-10-11 16:52:04

+0

不幸的是，我认为我们不允许修改类本身，像严重破坏一样（严重吗？没有父指针在节点中？） – 2010-10-11 16:52:41

+0

我想知道你正在测试它的编译器。我只是在codepad.org上使用GCC来快速查找错误。唯一真正的编译错误是构造函数定义的默认参数。某些旧的或非标准的编译器可能会忽略或允许使用这些编译器。我没有做任何其他修改，因为我不想再做更多的修改。 – Vinzenz 2010-10-11 16:56:12

相关问题

 相关问题