1

私はこのように構成されたツリーn-aryを持っています:

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);
            }
        }
    }
}
4

3 に答える 3

1

あなたが実装しようとしているのは、バイナリ実装 (最初の子、右の兄弟) を持つ n-ary ツリーのようです。

他の命名法ではより明白です:

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);
}
于 2016-05-13T13:19:49.973 に答える
0

目標を達成するためのコードの（おそらく最小の）変更は次のとおりです。

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-16T12:49:04.257 に答える