how to return the pointer of a specific value in a tree in C?-CodePudding

using this struct :

typedef struct node {
  int content;
  struct node* right;
  struct node* left;
}Node;

I'm trying to write a code that return the pointer of the the node if node ->content== x I have tried this so far but I don't think its right :

 Node* find (Node* p,int x)
{
  Node* L,*R;
    if(p==NULL)
    retutn NULL;
  L=find(p->left,x);
    if(L->content == x)
    return L;
  R=find(p->right,x);
    if(R->content == x)
  return R;
}

can u help me correct my code?

CodePudding user response：

First, the code doesn't even compile because of retutn.

L=(p->left,x);    // Equivalent to: L = x;

should be

L=find(p->left,x);

Same idea for the right side.

L could be NULL.

if(L->content == x)

should be

if(L != NULL)

or just

if(L)

Same idea for the right side.

You never check if the current node is a match. You need to add the following:

if ( p->content == x )
   return p;

The following is correct:

Node* L, *R;

However, it's very easy to accidentally do

Node* L, R;

Maybe you should avoid grouping such declarations. On the plus side, this should be caught at compile-time (unless you avoid turning on even the most basic warnings).

All together,

Node* find(Node* p, int x)
{
   if ( !p )
      return NULL;

   if ( p->content == x )
      return p;

   Node* L = find( p->left, x );
   if ( L )
      return L;

   Node* R = find( p->right, x );
   if ( R )
      return R;

   return NULL;
}

CodePudding user response：

The part of the function starting from these statements

L=find(p->left,x);
  if(L->content == x)
  return L;

is incorrect. For starters it is unclear why the node pointed to by the pointer p is not checked. And the call of the function can return a null pointer. So this if statement can invoke undefined behavior.

The function definition depends on whether it is a binary search tree or not. That is whether nodes of the tree are ordered.

If it is not a binary search tree then the function can be defined the following way

Node * find( const Node *root, int x )
{
    if ( root == NULL )
    {
        return NULL;
    }
    else if ( root->content == x )
    {
        return ( Node * )root;
    }
    else
    {
        Node *p = find( root->left, x );
        return p == NULL ? find( root->right, x ) : p;
    }
}

If the tree is a binary search tree then the function can look the following way

Node * find( const Node *root, int x )
{
    if ( root == NULL )
    {
        return NULL;
    }
    else if ( x < root->content )
    {
        return find( root->left, x );
    }
    else if ( root->content < x )
    {
        return find( root->right, x );
    }
    else
    {
        return ( Node * )root;
    }
}

A non-recursive function can look the following way

Node * find( const Node *root, int x )
{
    int found = 0;

    while ( !found && root != NULL )
    {
        if ( x < root->content )
        {
            root = root->left;
        }
        else if ( root->content < x )
        { 
            root = root->right;
        }
        else
        {
            found = 1;
        }
    }

    return ( Node * ) ( found ? root : NULL );
}