C++ only.

P PROBLEM STATEMENT:

Write a breadth-first traversal for a Top-Down Tree

CODE:

You must write correctly functioning code for

breadthFirstTraversal( void (*processnode)(BaseData &value) )

Note the breadth first traversal included does not correctly work this is the code provided in the

textbook for a binary tree -eliminate it.

TD_tree.t

#ifndef TDTREE_T

#define TDTREE_T

#include

template

TDTree::TDTree(int (*precedes)(const BaseData& x, const BaseData& y))

: GenTree ()

{

compare = precedes;

}

template

TDTree::TDTree(const TDTree & initTopDownTree)

: GenTree (initTopDownTree)

{

compare = initTopDownTree.compare;

}

template < class BaseData>

bool TDTree::add(BaseData parent, BaseData item, int childnum)

{

if ( GenTree::root == 0 )

{

GenTree::root = new GtNode;

GenTree::root->info = item;

GenTree::root->firstChild = NULL;

GenTree::root->sibling = NULL;

return(true);

}

else

return(add_aux( GenTree::root, parent, item, childnum) );

}

template < class BaseData>

bool TDTree::add_aux(GtNode * rt, BaseData parent,

BaseData item, int childnum)

{

GtNode *temp;

GtNode *prev;

int c ;

if ( rt != 0 )

if (compare(parent,rt->info) == 0)

{

temp = new GtNode;

temp->info = item;

temp->firstChild = 0;

if (childnum == 1 || rt->firstChild == 0)

{

temp->sibling = rt->firstChild;

rt->firstChild = temp;

}

else

{

for ( c = 2, prev = rt -> firstChild; ( c ++c, prev = prev -> sibling) ;

temp -> sibling = prev -> sibling;

prev -> sibling = temp;

}

return(true);

}

else if (!add_aux(rt->firstChild,parent,item,childnum))

return(add_aux(rt->sibling,parent,item,childnum));

else

return(true);

else

return(false);

}

template

void TDTree::breadthFirstTraversal( void (*processnode)(BaseData &value) )

{

/*

std::queue< GtNode* > nodes2visit;

GtNode *item = GenTree::root;

if ( item )

{

nodes2visit.push( item );

while ( !nodes2visit.empty() )

{

item = nodes2visit.front();

nodes2visit.pop();

processnode( (item->info) );

if (item -> firstChild )

nodes2visit.push( item -> firstChild );

if (item -> sibling )

nodes2visit.push( item -> sibling );

}

*/

}

#endif

I comment on the code that is used for breadthfirst traversal. The problem is: it only works on Binary Trees, not the General Trees.

driver.cpp

#include

using std::cout;

using std::cin;

using std::endl;

#include "TD_Tree.h"

//#include "BinTree.h"

//#include "BinSearchTree.h"

//#include "ThreadBinTree.h"

//#include "AvlTree.h"

int preceed (const char& c1, const char& c2)

{

return c1 - c2;

}

bool preceed2 (const int &x, const int &y)

{

return x <= y;

}

void dump(char & value)

{

cout << value;

}

void dump2( int & value)

{

cout << value << " ";

}

int main()

{

TDTree t1( preceed);

//Input for 'H', 'i', ' ', 't', 'h', 'E', 'r', 'e'

t1.add( 'H', 'H', 1 );

t1.add( 'H', 'i', 1 );

t1.add( 'i', ' ', 1 );

t1.add( 'H', 't', 2 );

t1.add( 't', 'h', 1 );

t1.add( 't', 'r', 2 );

t1.add( 't', 'e', 3 );

t1.add( 'h', 'E', 1 );

// t1.add( 'H', 'Z', 3 );

/// t1.add( 'i', 'y', 2);

//Sending in to the function

cout << " t1 printing breadth first traversal ";

t1.breadthFirstTraversal( dump);

cout << endl << endl;

cout << " oops ... let's try that again ";

cout << " t1 printing depth first traversal ";

t1.depthFirstTraversal( dump);

cout << endl << endl;

cout<

return (0);

}

The output has to be "Hit hrEe" as a breadth first traversal of the top down tree.