c - 在 n 叉树中搜索项目

Question

我有一棵以这种方式组成的 n 叉树:

struct n_tree{
    struct list *adj;    
};

struct list{
    struct n_tree *child;
    struct list *next;
    int key;
};

如何搜索项目？我已经实现了这个功能，但是它不起作用...谢谢!

struct list *find(struct list *root, int key){
    if(root){
        find(root->next,key);
        if (root != NULL){
            if(root->key == key){
                return root;
            }
            else if(root->child != NULL){
                return find(root->child->adj,key);
            }
        }
    }
}

Answer 1

看来您要实现的是一个具有二进制实现的 n 叉树(第一个 child ，右 sibling )。

其他命名更明显:

struct n_tree{
  struct list *root;    
};

struct tree_node{
    int key;
    struct tree_node *first_child;
    struct tree_node *right_sibling;
};

递归搜索函数返回具有键 key 的节点，如果没有找到节点则返回 NULL 可以是:

struct tree_node *find_node(struct tree_node *from, int key){
  // stop case
  if (from==NULL) return NULL;
  if (from->key==key) return from;
  // first we'll recurse on the siblings
  struct tree_node *found;
  if ( (found=find_node(from->right_sibling,key) != NULL ) return found;
  // if not found we recurse on the children
  return find_node(from->first_child, key);
}

如果你需要一个带有 n_tree 参数的包装函数:

struct tree_node* find(struct n_tree* tree, int key) {
  return find_node(tree->root, key);
}