在 n-Ary 树中查找元素

Question

给定以下结构

struct nNode {
   int val;
   struct nNode parent;
   struct nNode children;
   struct nNode next;
   struct nNode prev;

};

其中 children 指向第一个 child 并遍历到其他 child 我们需要遵循 node->children->next ...

我正在尝试 return 使用函数

指向包含一些 val 的元素的指针

struct nNode* nNode_find(struct nNode *node, int val)
{
  // We found the node return the pointer
  if(node->val == val) return node;
  // We didn't found let's check the children
  struct nNode *child = node->children;
  while(child) {
    nNode_find(child, val);
    child = child->children;
    // We didn't found on child, lets check his brothers
    struct nNode *sibling = child->next;
    while(sibling) {
      nNode_find(sibling, val);
      sibling = sibling->next;
    }
  }
  // We didn't found the element return NULL
  return NULL;
}

给定一棵树 TREE 喜欢：

  /*                      1
   *            /---------|--------\
   *          2           3         4
   *        /   \                 /
   *      5       6              7
   */

像

这样的命令

struct nNode *ptr = nNode_find(TREE, 3);

应该 return 指向 root->children->next 的指针，但实际 nNode_find 是 returning NULL.

Answer 1

问题是您忽略了递归 nNode_find 中的 return 值。如果值 returned 是非 NULL，你应该直接 return 它。所以而不是

nNode_find(child, val);

做

struct nNode* found = nNode_find(child, val);
if (found) {
    return found;
}

此外，每个 nNode_find 调用应该只处理一个节点，而不是子节点的子节点，等等；你会想要做一些调试打印以确保每个节点最多被搜索一次并且只被搜索一次。

在 n-Ary 树中查找元素

Find element in a n-Ary tree

c

tree

n-ary-tree