Trying to make a templated recursive tree printer_问答_开发者

I'm trying to make a recursive tree printer for a template class tree so that it can print the tree without knowing what kind of data is there beforehand. But I can't figure the syntax out that I need.

Right now I know that the code would only print the root of the tree, but I can't even get it to do that.

Ideas?

edit:

Here's the compiler error messages:

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>开发者_如何学C 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;
}

First I had to fix the tree implementation that it is actually compilable. The definition of a method or function may not have default parameters if you declared them already.

In this case this was your Constructor

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

  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

Now your main:

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

On first glance, it seems that your print_tree function is expecting a pointer to a HWTreeItr<Object>, where the Object class does not seem to be defined. Do you want a templated version of print_tree?

How about:

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

(EDITED - I left the <class Object> in the argument list. Should just be <Object>