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