N元树级序遍历的递归

Question

我目前正在研究N进制树，我偶然发现了级序遍历。理论上看起来很简单，在代码上运行并不困难，但是现在我想把它升级并添加递归，这样我就可以更好地理解它。问题是我现在发现很难这样做。这是我的代码：

- The node class

    

import java.util.ArrayList;
import java.util.List;

/**
 * Implementation of a generic tree node containing the data and a list of children.
 *
 * @param <T> Generic type meant to implement reference types into the tree.
 */
public class Node<T> {
  private T data;
  private List<Node<T>> children;

  /**
   * Constructor that initializes the data and the list of children of the current node.
   *
   * @param data The value of the node.
   */
  public Node(T data) {
    this.data = data;
    children = new ArrayList<>();
  }

  public T getData() {
    return data;
  }

  public void setData(T data) {
    this.data = data;
  }

  public List<Node<T>> getChildren() {
    return children;
  }

  public void setChildren(List<Node<T>> children) {
    this.children = children;
  }
}






-The tree class


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/** Implementation of a generic n-ary tree. */
public class Tree<T> {
  private Node root;
  private List<Node<T>> nodes;
  /**
   * Constructor that initializes the root node of the tree.
   *
   * @param data The value of the root node.
   */
  public Tree(T data) {
    root = new Node<>(data);
  }

  public Node getRoot() {
    return root;
  }

  /**
   * Method that implements the Level Order Traversal algorithm. It's a left to right traverse where
   * each level of the tree is being printed out. First the root , then it's children and then each
   * child's children etc.
   *
   * @param root The root node of a tree.
   */
  public String levelOrderTraversal(Node root) {
    StringBuilder result = new StringBuilder();
    if (root == null) {
      return "";
    }
    result.append("\n");
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
      int queueSize = q.size();
      while (queueSize > 0) {
        Node node = q.peek();
        q.remove();
        result.append(node.getData().toString()).append(" ");
        for (int i = 0; i < node.getChildren().size(); i++) {
          q.add((Node) node.getChildren().get(i));
        }
        queueSize--;
      }
      result.append("\n");
    }
    return result.toString();
  }

  /**
   * This method serves to recursively move through and retrieve the nodes, so they can be printed
   * out to the user.
   *
   * @param root The root node of the tree.
   */
  private void walkThroughElements(Node root) {
    if (root == null) {
      return;
    }
    nodes.add(root);
    for (Object node : root.getChildren()) {
      walkThroughElements((Node) node);
    }
  }
  /**
   * Implementation of pre-order traversal of a generic tree. This traversal visit the root node
   * first , prints it , then visits the whole left sub-tree (the list of every child node), prints
   * every node and then traverses the right sub-tree , prints the nodes and ends the algorithm.
   *
   * @param root The root node of the tree.
   * @return The nodes of the tree as a string.
   */
  private String preOrderTraversal(Node<T> root) {
    nodes = new ArrayList<>();
    StringBuilder result = new StringBuilder();
    walkThroughElements(root);
    for (Node node : nodes) {
      result.append(node.getData()).append(" ");
    }
    result.setLength(result.length() - 1);
    return result.toString();
  }

  public String preOrderTraversal() {
    return preOrderTraversal(root);
  }
}

是否有一种有效的方法，或者递归地运行这种级别顺序遍历方法是否有意义？

这是一些更改后的级别订单代码

    public String levelOrderTraversal(Node root) {
    StringBuilder result = new StringBuilder();
    if (root == null) {
      return "";
    }
    result.append("\n");
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    collectNodes(root, root.getChildren());
    result.append(root.getData().toString()).append(" ");
    result.append("\n");
    return result.toString();
  }

它在调用collectNodes的行上给出错误。

这就是collectNodes（）的外观。

    private void collectNodes(Node<T> node, List<Node<T>> nodes) {
    nodes.add(node);
    for (Object child : node.getChildren()) {
      collectNodes((Node) child, nodes);
    }
  }

Answer 1

正确的方法是以懒惰的方式去做

// assume not null Node::data (if so, wrap into Optional or similar)
static <T> Stream<T> levelOrderTraversal(Node<T> tree) {

    final List<Node<T>> fifo = new ArrayList<>();

    if(tree != null)
        fifo.add(tree);

    final Function<T, T> next = o -> {
        if(fifo.isEmpty())
            return null; // End Of Stream
        Node<T> x = fifo.remove(0);
        System.out.println("++++++ " + x.data);
        if(x.children != null)
            fifo.addAll(x.children);
        return x.data;
    };

    return Stream.iterate(null, next::apply).skip(1).takeWhile(Objects::nonNull);
}

例如

++++++ foo
foo
++++++ bar1
bar1
++++++ bar2
bar2
++++++ par11
par11
++++++ par12
par12
++++++ par21
par21
++++++ par22
par22
++++++ subA
subA
++++++ subB
subB

只控制中间的遍历级别（而不是整个树）。

例如，如果记录每个节点扩展并过滤树，则不会记录所有节点

    levelOrderTraversal(tree)
            .takeWhile(x -> !x.equals("bar2"))
            .forEach(System.out::println);

只展开foo，bar1和bar2节点

++++++ foo
foo
++++++ bar1
bar1
++++++ bar2

Answer 2

使用递归通常会比迭代慢，并且使用更多的堆栈空间。但是，是的，这也可以用递归方法（DFS方法）来解决。

供参考：https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/33562/Java-1ms-DFS-recursive-solution-and-2ms-BFS-iterative-solution

Answer 3

您可以使用迭代（例如通过堆栈）或递归来解决这些迭代问题。让我们使用一个方法来收集节点，非常类似于您的walkousElements（）：

深度优先

递归

//add the node and then go deeper
void collect(Node node, Collection<Node> nodes) {
  nodes.add(node);

  for(Node child : node.getChildren()) {
    collect(child, nodes);
  }
}

迭代

class Level {
  final Node node;
  Iterator<Node> childItr;

  //constructor, setters, getters
}

void collect(Collection<Node> nodes) {
  Stack<Level> levels = new Stack<>();

  nodes.add(root);
  levels.push(new Level(root, root.getChildren().iterator()));

  while( !levels.isEmpty() ) {
    Level currentLevel = levels.peek();
    
    //remove the current level as it doesn't have any more children
    if( !currentLevel.childItr.hasNext() ) {
      levels.pop();
    } else {
      //get the next child and add it to the result
      Node child = currentLevel.childItr.next();
      nodes.add(child);

      //go down to the child's level
      levels.push(new Level(child, child.getChildren().iterator())
    }
  }
}

广度优先

递归

//add the children first (i.e. the entire level) and then go deeper
void collectChildren(Node node, Collection<Node> nodes) {      
  for(Node child : node.getChildren()) {
    nodes.add(child);
    collectChildren(child, nodes);
  }
}

//special case: root node
void collect(Collection<Node> nodes) {
   nodes.add(root);
   collectChildren(root, nodes);
}

迭代

void collect(Collection<Node> nodes) {
  Queue<Node> nodesToProcess = new LinkedList<>();

  nodesToProcess.add(root);

  while( !nodesToProcess.isEmpty() ) {
    Node node = nodesToProcess.poll();

    nodes.add(node);

    nodesToProcess.addAll(node.getChildren());
  }
}

正如您所看到的，递归在深度优先上比广度优先更容易，但无论如何都很容易阅读。递归将使用调用堆栈来维护状态，因此它会占用（非堆）内存，并且对其深度也有限制（取决于内存量，但臭名昭著的StackOverflowException会告诉您存在错误或树太深）。

宽度优先的迭代更容易，并且需要额外的构造，如堆栈或队列。对于这些结构，它需要一些堆内存，并且可能由于一些优化而更快，但一般来说，我不会在这里讨论性能差异，因为它们应该只在真正大的树上显示自己——在这种情况下，递归可能已经达到了调用堆栈的限制。