Поскольку это помечено как домашнее задание, вы, вероятно, должны написать это сами.
Обычно, когда дело доходит до обхода дерева, у вас не так много шансов на оптимизацию, потому что, начиная с узла, у вас есть только варианты посетить родительский узел или дочерние узлы. (В отличие от графика, где вы можете применить алгоритм Дейкстры )
Просто попробуйте, я бы порекомендовал рекурсию.
Узел обычно выглядит так:
public class Node {
public String value; //contains "C" or "D" etc
public List<Node> children = new ArrayList<Node>();
public Node parent;
public Node(Node parent){
this.parent = parent;
}
public Node(Node parent, String value){
this.parent = value;
this.value = value;
}
public boolean equals(Object n){//Nodes are equal if they have the same value
return value.equals(((Node)n).value);
}
}
Если вопрос заключается в том, чтобы найти минимальное количество шагов от А до В (которое является расстоянием), я бы реализовал метод distanceTo, который обходит дерево и ищет целевой узел, пока он не будет найден. Если вы никогда раньше не работали с деревьями, это может быть немного сложно.
Хорошо, поскольку вы никогда раньше не работали с Деревьями :
Дерево - это структура данных, которая содержит определенное количество узлов. Соединения между Узлами представлены ссылками между Узлами.
Каждый узел имеет ссылку на свой родительский узел (тот, что выше) и список дочерних узлов (узлы ниже). Узел может иметь только одного родителя, но любое количество детей. Узел без дочерних элементов называется листом. Корневой узел обычно идентифицируем, потому что его атрибут parent равен null (потому что корень, который является самым верхним узлом, не имеет родителя). Все остальные узлы в дереве имеют parent!=null.
Отправной точкой для Дерева является корневой Узел. Следующий код создает 3 верхних узла из вашей картинки (где тип Node - это класс java выше):
Node nodeRoot = new Node(null, "root"); //create a node with parent=null
Node nodeA = new Node(nodeRoot, "A");
Node nodeB = new Node(nodeRoot, "B");
nodeRoot.children.add(nodeA); //you could also place this functionality
nodeRoot.children.add(nodeB); // in the constructor of Node
Теперь у вас есть 3 дерева (начиная с nodeRoot) с 3 узлами: «корень», «A» и «B».
Теперь вы можете показать все узлы, которые являются прямыми дочерними элементами корневого узла:
for(Node child:nodeRoot.children){
System.out.println(child.value);
}
/* prints:
A
B
*/
Или выведите значение родительского узла:
System.out.println(nodeA.parent.value);
/*prints:
root
*/
Попробуйте завершить код, чтобы создать дерево, представляющее дерево на вашей картинке!
Чтобы продолжить (-> обход дерева), я настоятельно рекомендую вам сначала прочитать что-нибудь об этом . Сосредоточьтесь на Глубине-Первом Обходе и Ширина-Первом Обходе и убедитесь, что вы понимаете разницу.
Относительно "Бинарных Деревьев":
Это работает очень хорошо для недвоичных деревьев. Определение бинарных деревьев гласит:
бинарное дерево - это древовидная структура данных, в которой каждый узел имеет не более двух дочерних элементов.
Поскольку я использовал Список узлов в классе java выше, вы можете использовать любое количество дочерних элементов на узел. Фактически вам придется потратить дополнительную работу, чтобы сделать класс совместимым с бинарным деревом - это означает, что каждый узел может иметь только 0, 1 или 2 дочерних элемента.
Для недвоичных деревьев вы можете: а) использовать приведенный выше класс и б) применять те же алгоритмы (BFS / DFS).