I wrote a program which creates an n-ary tree using the left child right sibling approach. Each node of the tree is labeled by a dynamically allocated array of ints. I am currently having a problem where if I am searching for a node labeled 1 2 3 4 5, and if there is a node labeled 1 2 3 higher up in the tree then the node labeled 1 2 3 4 5, my function finds 1 2 3 and returns that as the best match.

the main file calls findNode when it needs to pass a node to a function and all it has is a label which the user enters. Here is a line of code where that happens.

``tree->add( tmp, size, tree->findNode( tmp3 ), tree->findNode( tmp2 ), tmpNode);``

I wrote 3 functions, one which the main file calls, and that then calls two helper functions. betterMatch and findHelp. betterMatch returns an integer which is equal to the best match... if im searching for 1 2 3 4 5, it should return 5 as long as there is a node with the label 1 2 3 4 5.

findHelp returns the node you are searching for. Here is my code for the 3 functions.

FINDNODE FUNCTION

``````Node& Tree::findNode( int* label ){

int x = betterMatch( *root, label, 0 );

return( findHelp(*root, label, x));
}``````

BETTERMATCH FUNCTION

``````int betterMatch( Node& node, int* label, int best ){

if( label == NULL ){
return 0;
}

int i, x, y, count = 0;
int* tmp = new int[node.getSize()];

tmp = node.getLabel();
for( i = 0; i < node.getSize(); i++ ){
if( tmp[i] == label[i] )
count++;
}

if( count > best )
best = count;

try{
x = betterMatch( node.getLc(), label, best );
}catch(int){}

try{
y = betterMatch( node.next(), label, best );
}catch(int){};

if(best < x || best < y){
if( x > y ){
try{
return( betterMatch( node.getLc(), label, best) );
}catch(int){};

}else{
try{
return( betterMatch( node.next(), label, best) );
}catch(int){};
}
}
return( best );
}``````

FINDHELP FUNCTION

``````Node& findHelp(Node& node, int* label, int bestMatch ) {
//recursive function to find specific node
//located in tree with given root

if( label == NULL ){
Node *nil = new Node();
return(*nil);
}

int i, count = 0;
int* tmp = new int[node.getSize()];

tmp = node.getLabel();
for( i = 0; i < node.getSize(); i++ ){
if( tmp[i] == label[i] )
count++;
}

if( count == node.getSize() && count >= bestMatch ){
return node;

}else{
try{
return( findHelp(node.getLc(), label, 0));   //call findHelp for leftchild
}
catch(int){};                 //if exception is thrown dont do anything
try{
return( findHelp(node.next(), label, 0));    //same as for leftchild
}
catch(int){};
}
cout << "Node with given label cannot be found" << endl;
Node *nil = new Node();
return(*nil);
}``````

Edited by Dewey1040: n/a

1
Contributor
1
2
Views
8 Years
Discussion Span
Last Post by Dewey1040

An easier problem im having with this program is I can't get my nodeCount() function to return the correct amount of nodes, Its reporting there are 3 nodes when there are only 2. Here are the two functions I'm using to do this. Any help on this post or last post would be appreciated

``````//function main file calls
int Tree::numberOfNodes() const{

return( nodeCount(*root, 1) );
}

//Recursive helper function
int nodeCount( Node& tmp, int i ){

if( tmp.getLabel() != NULL )         //if the label is not NULL i = i + 1
i++;

try{
i = nodeCount( tmp.getLc(), i );   //call nodeCount for left child
}
catch(int){};                   //if exception is thrown dont do anything
try{
i = nodeCount( tmp.next(), i );    //same process for right sibling
}
catch(int){};

return( i );

}``````

Edited by Dewey1040: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.