struct tree {
   char info;
   struct tree* left;
   struct tree* right;
};

typedef struct tree Tree;

Tree* address = NULL; // How to remove this global variable?

void nodeAddress (Tree* a, char v) {
   if (a != NULL) {
      nodeAddress(a->left, v);
      if (a->info == v) address = a;
      nodeAddress(a->right, v);   
   }
}

CodePudding user response：

Just use return, unless you really think the double-pointer is clearer.

Since you've underspecified your goal, it is hard to give you a good example:

• if more than one node can match v, your code is will pick the right-most one, but

• if we can assume only one node can match v, or any matching node is a good result, then you can optimize out some needless recursion (unless of course you know you're justifiably protecting against f.e. a timing side-channel attack by recursing over the whole tree in all cases).

So, here's the simpler example assuming the first match found is good:

struct tree {
   char info;
   struct tree * left;
   struct tree * right;
};

struct tree * find_matching_node(struct tree * a, char v)
{
   struct tree * found = NULL;
   if (a != NULL)
   {
       if (a->info == v)
       {
           found = a;
       }
       if(found == NULL)
       {
           found = find_matching_node(a->left, v);
       }
       if(found == NULL)
       {
           found = find_matching_node(a->right, v);
       }
   }
   return found;
}

But here's one that's exactly equivalent to your example:

struct tree * find_matching_node(struct tree * a, char v)
{
   struct tree * found = NULL;
   struct tree * found_rightmost;
   if (a != NULL)
   {
       if (a->info == v)
       {
           found = a;
       }
       if(found == NULL)
       {
           found = find_matching_node(a->left, v);
       }
       found_rightmost = find_matching_node(a->right, v);
       if(found_rightmost != NULL)
       {
           return found_rightmost;
       }
   }
   return found;
}

You can of course do the double pointer, which is a smaller code change:

void find_matching_node(struct tree * a, char v, struct tree * * found)
{
   if (a != NULL) {
      find_matching_node(a->left, v, found);
      if (a->info == v) *found = a;
      find_matching_node(a->right, v, found);   
   }
}

But notice that this last version retains both the inefficiency of recursing into the whole tree and the ambiguity about which behavior is intended if there are multiple matches. The inefficiency can be solved by a strong-enough optimizing compiler, but the ambiguity locks the code into always recursing into the right half just in case you intended to get the right-most match in the event of multiple matches.

CodePudding user response：

I agree with the above, you should just simply use return.

Consider also the use of another layer of abstraction for pointers, which is completely a matter of personal choice. I personally find this type of pointer type definition makes the code a lot cleaner:

struct tree;
typedef struct tree *Position;
typedef struct tree
{
   char info;
   Position left;
   Position right;
} Tree; 

CodePudding user response：

Following your tips, I found the solution. Thanks! Here's the code:

find_matching_node(Tree* a, char v, Tree** found) {

if (a != NULL) {

  find_matching_node(a->left, v, found);

  if (a->info == v) *found = a;

  find_matching_node(a->right, v, found);

}

}

Tree* find(Tree* a, char v) {

Tree* found = NULL;

if (a != NULL) {

  if (a->info == v) {

     found = a;

     return found;

  }

  if(found == NULL) find_matching_node(a->left, v, &found);

  if(found == NULL) find_matching_node(a->right, v, &found);

}

return found;

}

void main() {

Tree* x = find(root, 'a');

}