N叉树层序遍历的递归
Recursion of Level Order Traversal of N-ary tree
我目前正在研究 N-ary 树，我偶然发现了 Level Order Traversal。这在理论上似乎很容易，在代码上 运行 并不难，但现在我想加强它并添加递归，这样我就可以更好地思考它。事情是我现在发现很难这样做。我的代码是：
- 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);
}
}
使用递归通常会比迭代慢并且使用更多的堆栈 space as well.But 是的，这也可以使用递归方式（DFS 方法）来解决。
您可以使用迭代（例如通过堆栈）或递归来解决这些迭代问题。让我们使用一种收集节点的方法，就像您的 walkThroughElements():
深度优先
递归
//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());
}
}
如您所见，深度优先递归比广度优先递归更容易，但无论如何都易于阅读。递归将使用调用堆栈来维护状态，因此它占用（非堆）内存并且对其深度也有限制（取决于有多少内存但臭名昭着的 WhosebugException 会告诉你有错误或树太深）。
广度优先的迭代更容易，并且需要额外的结构，如堆栈或队列。这些构造需要一些堆内存，并且 可能 由于一些优化而更快，但总的来说我不会在意这里的性能差异，因为它们应该只对真正的大树表现出来 - 并且在这种情况下，递归可能已经达到调用堆栈限制。
偷懒才是正道
// 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
我目前正在研究 N-ary 树，我偶然发现了 Level Order Traversal。这在理论上似乎很容易，在代码上 运行 并不难，但现在我想加强它并添加递归，这样我就可以更好地思考它。事情是我现在发现很难这样做。我的代码是：
- 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);
}
}
使用递归通常会比迭代慢并且使用更多的堆栈 space as well.But 是的，这也可以使用递归方式（DFS 方法）来解决。
您可以使用迭代（例如通过堆栈）或递归来解决这些迭代问题。让我们使用一种收集节点的方法，就像您的 walkThroughElements():
深度优先
递归
//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());
}
}
如您所见，深度优先递归比广度优先递归更容易，但无论如何都易于阅读。递归将使用调用堆栈来维护状态，因此它占用（非堆）内存并且对其深度也有限制（取决于有多少内存但臭名昭着的 WhosebugException 会告诉你有错误或树太深）。
广度优先的迭代更容易，并且需要额外的结构，如堆栈或队列。这些构造需要一些堆内存，并且 可能 由于一些优化而更快，但总的来说我不会在意这里的性能差异，因为它们应该只对真正的大树表现出来 - 并且在这种情况下，递归可能已经达到调用堆栈限制。
偷懒才是正道
// 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