Функция, которая ищет определенный узел в двоичном дереве?

Question

Я пытаюсь написать функцию, которая пересекает дерево, пока не найдет узел, который содержит заданное значение (в данном случае символ). Я пытался что-то вроде этого:

struct HuffTreeNode* findNode (struct HuffTreeNode* root, unsigned char symbol) 
{ 
    if (root != NULL) 
    { 
    if (root->symbol == symbol) 
    { 
     return root; 
    } 
    else 
    { 
    findNode(root->left,symbol); 
    findNode(root->right,symbol); 
    } 
    } 
    return root; 
} 

Так что, если я назвал findNode(root,'c'), он будет возвращать узел, который содержит «с». Однако я не могу заставить эту функцию работать, любые идеи?

Примечание: Я знаю, что указанная выше функция не имеет ответа, если узел с указанным символом не существует, но пока я просто вызываю его, используя символы, которые, как я знаю, содержатся внутри дерева.

Answer 1

Примечание: Я знаю, что данная функция не имеет ответа, если узел с этим данным символом, не существует,

Это первая проблема. Вы возвращаете root, даже если это не правильный узел. В этом случае вы должны вернуть NULL.

Далее вы рекурсивно вызываете findNode справа и слева, но вы ничего не делаете с их возвращаемыми значениями, поэтому ваш код никогда не сможет работать. Проверьте возвращаемое значение. Если это не NULL, это означает, что совпадение найдено в этом поддереве, поэтому верните его.

struct HuffTreeNode* findNode (struct HuffTreeNode* root, unsigned char symbol) 
{ 
    if (root != NULL) 
    { 
    if (root->symbol == symbol) 
    { 
     return root; 
    } 
    else 
    { 
     struct HuffTreeNode *n; 

     // Try the left sub-tree 
     n = findNode(root->left,symbol); 
     if (n) 
      return n; 

     // Try the right sub-tree 
     n = findNode(root->right,symbol); 
     if (n) 
      return n; 
    } 
    } 

    // Not found 
    return NULL; 
}