布爾遞歸

試圖寫一個布爾方法，告訴如果某人是某人的後代...但似乎無法做到這一點。當然，如果它是一個孩子......或者孩子的後代，那麼這個對象就是後代。布爾遞歸

public boolean isDescendant(member x){ 
    if (children.contains(x)){ 
     return true; 
    } 
    else{ 
     return false; 
    } 
}

但哪裏或如何插入：

for (int i = 0; i < children.size(); i++){ 
    isDescendant(children.get(i)); 
}

的感謝！

來源

2011-02-16 user618712

您還沒有說過節點是形成循環圖還是DAG /樹，以及子節點是否有連接到其父節點的鏈接。 – 2011-02-16 16:41:17

行走的樹木向下很慢（從根部到樹葉）。考慮爲祖先檢查執行此操作：

/** 
* Checks whether the given node is an ancestor of this node. 
*/ 
public boolean isDescendantOf(Node ancestor) { 
    Preconditions.checkNotNull(ancestor, "Ancestor"); 
    if (equals(ancestor)) { 
     // every node is an ancestor to itself 
     return true; 
    } else if (parent == null) { 
     // not related 
     return false; 
    } else { 
     // recursive call 
     return parent.isDescendantOf(ancestor); 
    } 
}

另一種方式現在是小菜一碟。

public boolean isDescendant(Node descendant) { 
    return descendant.isDescendantOf(this); 
}

沒有循環，沒有指數的努力。

PS：
在我的例子中，我建議將isDescendant重命名爲isAncestorOf。

來源

2011-02-17 00:25:48 whiskeysierra

我想你想要的是如下：

// Cleaned up version 
public boolean isDescendant(member x){ 
    // check for direct descendance 
    if (children.contains(x)){ 
     return true; 
    } 
    // check for being descendant of the children 
    for (Child c: children){ 
     if (children.get(i).isDescendant(x)) { 
      return true; 
     } 
    } 
    return false; 
}

來源

2011-02-16 16:21:43 jjnguy

這就是我在開始時所做的......但我開始試圖在我的腦海中遵循它，並且它開始沒有意義。但也許是對的？ – user618712 2011-02-16 16:23:00

晚上在這裏還是`isDescendant（children.get（i））`將永遠是真的？你是不是指`children.get（i）.isDescendant（x）`？ – 2011-02-16 16:23:25

@Alex，你是對的，我改變了。 – jjnguy 2011-02-16 16:24:10

-1

public boolean isDescendant(member currentRoot, member x){ 
    //check the current level 
    if (currentRoot.children().contains(x)){ 
     return true; 
    } 

    //leaf 
    if(currentRoot.children().isEmpty()){ return false; } 

    //try all my children 
    boolean found = false; 
    for(Member child : currentRoot.children()){ 
     found = isDescendant(child, x); 
     if(found) break; 
    } 

    return found; 
}

您需要遞歸在當前根，最有可能的。

來源

2011-02-16 16:25:13

-1

編輯：如果你的數據結構有父指針，使用這些而不是在樹中搜索你的後代。如果不是，請考慮添加它們。使用父指針查看whiskeysierra的解答。只有添加它們是不可能的，請考慮這個答案。

目前的答案都必須通過孩子兩個循環（一個在children.contains()，一個更高版本）。

這個變種可能更有效一些（但它不會改變O-class），並且有點短。（如果孩子是一組具有快速包含支票（如HashSet的），往往層次不那麼深（所以你並不需要在所有遞歸），其他答案是更好的。）

public boolean isDescendant(Member x) { 
    for(Member child : children) { 
     if(child.equals(x) || child.isDescendant(x)) 
     return true; 
    } 
    return false; 
}

如果一個節點被認爲是它自己的後代，你可以這樣寫：

public boolean isDescendant(Member x) { 
    if(equals(x)) 
     return true; 
    for(Member child : children) { 
     if(child.isDescendant(x)) 
     return true; 
    } 
    return false; 
}

來源

2011-02-16 17:03:20

回答

相關問題