c - 在二叉树中搜索特定节点的函数？

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')，它将返回包含“c”的节点。但是，我似乎无法使上述功能正常工作，有什么想法吗？

注意:我知道如果具有给定符号的节点不存在，上述函数不会有响应，但现在我只是使用我知道包含在树中的符号来调用它。

Answer 1

Note: I know that the above function doesn't have a response if a node with that given symbol doesn't exist,

这是第一个问题。您返回 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;
}