java - Java中具有2个以上子节点的树的深度优先搜索

Question

我有一个具有树结构的应用程序，其中每个父节点都有 3 个或更多子节点。每个节点包含一个整数值。我试图查看树中是否存在给定的整数值。如何在树上进行深度优先搜索？我知道我们从根部开始，然后尽可能地探索树的每个分支。不过，我在 Java 中实现这个方法时遇到了麻烦。我是否需要某种其他数据结构来进行遍历？

如果有人可以提供示例实现，将会很有帮助。

树结构如下。我需要实现findNode函数:

public class Tree{

    public Node{

        Node [] children;
        int val;

        public Node[] getChildren(){
            return children;
        }

        public getVal(int i){
            return children[i].val;
        } 

    }

    public boolean findNode(int val){


    }

}

Answer 1

迭代:

public boolean findNode(Node node, int value) {
  Deque<Node> stack = new ArrayDeque<Node>();
  stack.push(node);
  while (!stack.isEmpty()) {
    Node n = stack.pop();
    if (n.getVal() == value)
      return true;
    for (Node child : n.getChildren())
      stack.push(child);
  }
  return false;
}

递归:

public boolean findNode(Node node, int value) {
  if (node.getVal() == value)
    return true;
  for (Node n : node.getChildren()) {
    if (findNode(n, value))
      return true;
  }
  return false;
}

public int getVal() {
  return val;
}

您不需要 getVal(int i) 方法。节点参数是树的根。