0

I have an application which has a tree structure where each parent has 3 or more child nodes. Each node contains an integer value. I am trying to see if a given integer value is present in the tree. How do I do a Depth First Search on the tree? I understand that we start at the root and then explore as far as possible in each branch of the tree. I am having trouble implementing this in Java though. Would I need some sort of other data structure to do the traversal?

It would be helpful if someone could give a sample implementation.

The tree structure is as follows. I need to implement the findNode function:

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){


    }

}
4

2 回答 2

3

iterative:

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;
}

recursive:

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;
}

You do not need the getVal(int i) method. The node argument is the root of the tree.

于 2013-09-29T18:31:28.540 回答
0

未测试，但至少显示了算法的结构。如果您想要 BFS，只需将 替换Stack为LinkedList.

public boolean findNodeDFS(Node root, int value) {
    Stack<Node> nodes = new Stack<>(){{
      add(root);  
    }};
    while (!nodes.isEmpty()) {
        Node current = nodes.pop();

        if (current.getValue() == value) {
            return true;
        }
        nodes.addAll(Arrays.asList(current.getChildren()));
    }
    return false;
}
于 2013-09-29T18:36:17.700 回答