我有一個物件
Node(String url, List<Node> children);
現在這可能有幾個層次深，即
Node node1 = new Node ("www.google.com", new List<Node>())) (That list would contain more nodes, etc etc.
我想遍歷和展平樹，這樣我就可以將所有 url 值提取到一個串列中。我想我需要為此進行遞回，但是我不知道該怎么做。
uj5u.com熱心網友回復：
您可以撰寫一個方法，該方法Node使用遞回接收并回傳節點串列。
public List<Node> flattenNodes(Node node) {
LinkedList<Node> nodes = new LinkedList<>();
//recursively add the result of flattening children to nodes list
node.getChildren().forEach(n -> {
nodes.addAll(flattenNodes(n));
});
//add the current node to nodes list too
nodes.add(node);
return nodes;
}
這假設Node該類具有getChildren將節點的子節點作為串列獲取的方法。
這是我在撰寫此解決方案時使用的節點類：
public class Node {
private final String url;
private final List<Node> children;
public Node(String url, List<Node> children) {
this.url = url;
this.children = children;
}
public List<Node> getChildren() {
return children;
}
public String getUrl() {
return url;
}
}
我使用以下代碼測驗了解決方案：
Node aaa = new Node("www.aaa.com", new LinkedList<Node>());
Node aa = new Node("www.aa.com", List.of(aaa));
Node a = new Node("www.a.com", List.of(aa));
Node bb = new Node("www.bb.com", new LinkedList<Node>());
Node b = new Node("www.b.com", List.of(bb));
Node head = new Node("www.google.com", List.of(a, b));
flattenNodes(head).forEach(node -> System.out.println(node.getUrl()));
運行此測驗將以下內容列印到控制臺：
www.aaa.com
www.aa.com
www.a.com
www.bb.com
www.b.com
www.google.com
uj5u.com熱心網友回復：
您可能用于此類問題的常用模式與鏈接串列的模式類似。如果您想搜索二叉樹，那么您可以添加每個節點的左子節點和右子節點作為它的類屬性，并具有回傳這些節點的函式，如下所示：
class Node
{
Node leftChild;
Node rightChild;
string nodesUrl;
// make the same function for right child
public void setLeftChild(Node leftChild)
{
this.leftChild = leftChild;
}
// make the same function for right child
public Node getLeftChild()
{
return leftChild;
}
// make here functions for setting and getting the node′s url
}
由于每個節點都將參考它的子節點，因此您可以訪問左子節點，直到找到所需的 url。如果沒有成功到達樹的末尾，則必須嘗試通過的每個節點的每個 rightChild 并重復此程序。這可以通過遞回函式來實作，該函式通常用于搜索樹。
Node getNodeWithSearchingUrl(Node rootNode, string searchUrl)
{
Node leftChild = rootNode.getLeftChild();
Node rightChild = rootNode.getRightChild();
Node foundNode = null;
if(rootNode != null && rootNode.getUrl().Equals(searchUrl))
{
return rootNode;
}
if(leftChild != null)
{
foundNode = getNodeWithSearchingUrl(leftChild, searchUrl);
}
if(foundNode == null && rightChild != null)
{
foundNode = getNodeWithSearchingUrl(rightChild, searchUrl);
}
return foundNode;
}
我沒有嘗試代碼，但我認為它應該可以作業。如果您的樹不是二元樹而是“多級”樹，那么您需要將所有子樹保存在一個串列中，并始終使用遞回函式遍歷整個串列，而不是只保存左子樹和右子樹。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/383329.html