如何递归遍历潜在的无限树

Question

我有对象

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 值提取到一个列表中。我想我需要为此递归，但是我不知道该怎么做。

Answer 1

解决此类问题的常用模式与链表的模式类似。如果你想搜索一棵二叉树，那么你可以添加每个节点的左和右 child 因为它是 class 属性并且具有 return 你像这样的节点的功能:

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
}

因为每个节点都会引用它的 childs 你可以向左 child 举个例子，直到你找到你需要的 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;
}

我没有尝试该代码，但我认为它应该可以工作。如果你的树不是二元的而是“多级的”，那么你需要将所有的 children 保存在一个列表中，并且总是运行通过带有递归函数的整个列表。

Answer 2

您可以编写一个方法，使用递归接收 Node 和 returns 节点列表。

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 class 有一个 getChildren 方法来获取节点的子节点作为列表。

这是我在写这个解决方案时使用的节点class：

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

如何递归遍历潜在的无限树

How to recursively traverse a potentially infinite tree

java

tree

recursion