通過遞歸對象迭代

-3

我想通過遞歸對象進行迭代，但Java從我所瞭解的中不支持這一點。通過遞歸對象迭代

例如，給定對象Item：

public class Item { 

    Long uuid; 
    List<Item> children; 
}

隨着for環，我可以通過children迭代但由於children將包含更多children其中將包含更多children等，沒有辦法來自動確定基於該深度的深度和迴路。

有沒有辦法通過遞歸對象迭代？

來源

2015-09-07 Hooli

如果樹非常深，請使用Eran建議的呼吸優先搜索。如果樹是很寬的，用深度優先搜索可能看起來像：

class ItemVisitor { 
    public void accept(Item item) { 
     // Do something 
     for (Item i : item.getChildren()) { 
      this.accept(i); 
     } 
    } 
}

編輯：

對於呼吸優先搜索，用隊列和當前的所有孩子追加節點上。

public void visitTree(Item head) { 
    Queue<Item> queue = new PriorityQueue<Item>(); 
    while (queue.size() > 0) { 
     Item curr = queue.poll(); 
     // Do something 
     for (Item i : curr.getChildren()) 
      queue.add(i); 
    } 
}

來源

2015-09-07 10:20:40

如果你沒有親子樹中的循環，你可以使用一個簡單的遞歸函數來確定後代的數量：

public class Item { 
    ... 

    public int getDescendantCount() { 
     int count = 0; 
     if (children != null) { 
      count += children.size(); 
      for (Item child : children) 
        count += child.getDescendantCount(); 
     } 
     return count; 
    } 
}

來源

2015-09-07 10:16:27 wero

類似的東西來呢？

void read(Item item) { 
    if (item == null) { 
     //do something with the uuid ? 
     return; 
    } else { 
     for (Item i : item.children) { 
      read(i); 
     } 
    } 
}

來源

2015-09-07 10:16:51 McNultyyy

我的OP已經有了一個'Item'的引用他爲什麼會需要類似這樣的東西，通過'Item'查找？ –

如果您可以將深度作爲單獨的數據項存儲並通過類設計/封裝來執行，那麼您就很好。

你提出的是某種不確定深度樹的節點。您可以實現任何正常的深度優先或寬度優先的搜索方法;在任何標準的數據結構和算法教科書/ Web引用中查找並用Java實現。如果您使用堆棧（後進先出或LIFO隊列），或者如果使用FIFO隊列，則Eran提供的解決方案是標準的深度優先搜索。這些都是很好和乾淨的方法，但不是最簡單的方法。

最笨的方法將是一個深度優先搜索一個簡單的遞歸函數：

public void recurseIntoChildren(Item item) { 
    if(item.children.size() == 0) { 
     // you are now at a leaf node: do something 
    } 
    for(Item child : item.children) { 
     recurseIntoChildren(child); 
    } 
}

這種形式假設你想要做的葉節點的東西。如果你正在尋找一些東西，你可以讓recurseIntoChildren（）在你找到你想要的時候返回一個特殊值，這樣你就可以跳出所有剩下的遞歸循環（讓它返回null或者其他值來指示循環應該繼續）。如果你想採取其他行動，由你來滿足你的需求。

這不是最有效的方法（除非編譯器將尾遞歸優化爲簡單的循環）。

來源

2015-09-07 10:24:06 Laogeodritt

我不知道該函數的確切目標是什麼，但您可以始終通過子項遞歸循環。

例如

public void loopChildren(List<Item> items) { 
    for (Item i : items) { 
     System.out.println(i.uuid); 
     loopChildren(i.children);   
    }  
}

它只是不斷循環，直到列表的末尾。如果一個孩子沒有孩子，那麼列表應該是空的，因此它終止於該迭代。

希望這會有所幫助。

來源

2015-09-07 10:24:13 Brian

通過遞歸對象迭代

回答

相關問題