搜索在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叉樹

回答

相關問題