搜索在N叉树

一个项目我都以这种方式组成的树n元：搜索在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); 
      } 
     } 
    } 
}

来源

2016-05-13 b00k3r

如何分割'n'节点中的关键范围？我的意思是，用二叉树很简单：“key”下面的所有东西都是左边的，其他的东西都在右边。但是''n'元素不是很清楚。 – dasblinkenlight

你做了一个递归调用find（root-> next，key）;'但是不要使用返回的结果。那你为什么打这个电话？ – CiaPan

你说你有*'这样构成的树'*，但你实际上并没有显示任何*'方式'*。你刚刚展示了数据结构，但没有解释它们的含义：列表以某种方式排序？与'next'链接的列表中'键'之间的关系是什么？列表项中的“key”与“子”子树中的“key”之间的关系是什么？ – CiaPan

之前看着孩子，你需要看看在本地节点，因为这是你如何真正找到事情并结束递归。

此外，做一个递归调用并忽略返回值是毫无意义的（除非有一个“out-parameter”，这里没有）。所以不要这样做。

来源

2016-05-13 12:31:23 unwind

看来你试图实现的是一个带有二进制实现的n元树（第一个孩子，右兄弟姐妹）。

这是一个与其他namings更加明显：

struct n_tree{ 
    struct list *root;  
}; 

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

递归搜索功能与键键或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); 
}

来源

2016-05-13 13:19:49 Picodev

这里是（可能是最小的）您的代码修改，以实现您的目标：

struct list *find(struct list *root, int key){ 
    for(; root != NULL; root = root->next){ // scan the siblings' list 
     if(root->key == key)     // test the current node 
      return root;      // return it if the value found 

     if(root->child != NULL) {    // scan a subtree 
      struct list *result = find(root->child->adj, key); 
      if(result)      // the value found in a subtree 
       return result;    // abandon scanning, return the node found 
     } 
    } 
    return NULL;        // key not found 
}

来源

2016-05-16 12:49:04 CiaPan

搜索在N叉树

回答

相关问题