1. 首頁
  2. 問答
  3. 試圖製作一個模板遞歸樹打印機

試圖製作一個模板遞歸樹打印機

2010-10-11 53 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

相關問題

 相關問題