Поиск в глубину дерева с более чем двумя дочерними узлами в Java

У меня есть приложение с древовидной структурой, в которой каждый родитель имеет 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){


    }

}

java tree depth-first-search
person RagHaven    schedule 29.09.2013    source источник
comment
Ваш вопрос предполагает, что у вас уже есть дерево. Пожалуйста, предоставьте код используемых структур, чтобы его можно было использовать в примере кода.   -  person kenor    schedule 29.09.2013
comment
И DFS, и BFS используют один и тот же алгоритм. При реализации без рекурсии единственная разница между ними заключается в том, что один использует Stack, а другой использует Queue.   -  person atomman    schedule 29.09.2013
comment
Если это производственный код, а не учебное упражнение, взгляните на TreeTraverser Guava docs.guava-libraries.googlecode.com/git/javadoc/com/google/   -  person dnault    schedule 29.09.2013

Ответы (2)


arrow_upward
3
arrow_downward

итеративный:

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). Аргумент node является корнем дерева.

person kenor    schedule 29.09.2013
comment
Можете ли вы предоставить итеративную реализацию? - person RagHaven; 29.09.2013
comment
Вам нужно будет использовать стек для имитации рекурсивного поведения. - person kenor; 29.09.2013
comment
Да, я хотел бы знать, как это сделать. Можно ли обеспечить такую ​​реализацию? - person RagHaven; 29.09.2013
comment
Я добавил реализацию с использованием интерфейса Deque (docs.oracle .com/javase/7/docs/api/java/util/Deque.html) - person kenor; 29.09.2013

arrow_upward
0
arrow_downward

Не проверял, но покажите хотя бы структуру алгоритма. Если вы хотите использовать 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;
}
person atomman    schedule 29.09.2013