C++ only.

P ROBLEM 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.

#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.