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 6 Years Ago by Dewey1040: n/a

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 6 Years Ago by Dewey1040: n/a

This article has been dead for over six months. Start a new discussion instead.