c++ - 尝试制作模板化递归树打印机

Question

我正在尝试为模板类树制作一个递归树打印机，以便它可以打印树而无需事先知道那里有什么类型的数据。但是我想不出我需要的语法。

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

想法？

编辑:

编译器错误信息如下:

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

---

测试.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;
}

Answer 1

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

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

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

  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;
}