Два коротких пункта: пусть ваши друзья выбирают и форматируют имя!Вы захотите выработать привычку выбирать простые и выразительные имена переменных и сохранять аккуратно отформатированный код.
Давайте начнем с четких шагов:
(1) Существуетисточник слов данных, выраженный в виде дерева узлов.Избегая слишком большого количества деталей, давайте установим важные детали типа узла и сделаем дерево узлов доступным с помощью метода получения.
Важная деталь, которую следует упомянуть, заключается в том, что узлы предназначены для хранения в отсортированном двоичном деревеон имеет различные значения ключа и для которого значение любого левого узла строго меньше, чем значение узла, а значение любого правого узла строго больше, чем значение узла.Это имеет важное следствие, которое заключается в том, что значения левого поддерева узла все строго меньше, чем значение узла, а значения правого поддерева аналогично все строго больше значения узла.
public class Node<K, V> {
public K key;
public V value;
public Node<K, V> left;
public Node<K, V> right;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
public Node<String, Integer> getRootNode() {
// Undetailed ...
}
(2) Требуются три основные операции: операция по сбору узлов дерева в список, операция по сортировке этого списка и операция по отображению отсортированного списка.:
public List<Node<String, Integer>> flatten(Node<String, Integer> rootNode) {
// Undetailed ...
}
public void sort(List<Node<String, Integer>> nodes) {
// Undetailed ...
}
public void print(List<Node<String, Integer>> nodes) {
// Undetailed ...
}
(3) Это соответствует, например, следующим образом:
public void tester() {
Node<String, Integer> rootNode = getRootNode();
List<Node<String, Integer>> flatNodes = flatten(rootNode);
sort(flatNodes);
print(flatNodes)l
}
(4) Остается детализировать несколько методов.Мы начинаем с «сплющить».Это будет реализовано как рекурсивная операция.А поскольку обход хранилища для плоского списка проще, метод будет разделен на две части, одна из которых выделяет хранилище, а другая выполняет рекурсивную обработку.Этот метод передачи коллекции хранения типичен для такого рода обработки.
«flatten» использует свойство упорядочения узла относительно левого узла узла и правого узла узла: «flatten»добавляет все значения левого поддерева в список плоских узлов, за которым следует узел, за которым следуют все значения правого поддерева.
public List<Node<String, Integer>> flatten(Node<String, Integer> rootNode) {
List<Node<String, Integer>> flatNodes = new ArrayList<Node<String, Integer>>();
flatten(rootNode, flatNodes);
return flatNodes;
}
public void flatten(Node<String, Integer> node, List<Node<String, Integer>> flatNodes) {
if ( node == null ) {
return;
}
flatten(node.left, flatNodes);
flatNodes.add(node);
flatten(node.right, flatNodes);
}
(5) За счет ясности этоможно сделать несколько более эффективным путем перемещения нулевых проверок.Для полностью сбалансированного дерева это позволит избежать около 2/3 рекурсивных вызовов, что является довольно хорошим сокращением.Это имеет значение только в том случае, если количество узлов велико.И хороший компилятор, вероятно, все равно преобразует код таким образом.
public List<Node<String, Integer>> flatten(Node<String, Integer> rootNode) {
List<Node<String, Integer>> flatNodes = new ArrayList<Node<String, Integer>>();
if ( rootNode != null ) {
flatten(rootNode, flatNodes);
}
return flatNodes;
}
public void flatten(Node<String, Integer> node, List<Node<String, Integer>> flatNodes) {
Node<String, Integer> leftNode = node.left;
if ( leftNode != null ) {
flatten(leftNode, flatNodes);
}
flatNodes.add(node);
Node<String, Integer> rightNode = node.right;
if ( rightNode != null ) {
flatten(rightNode, flatNodes);
}
}
(6) Следующий бит сортирует список плоских узлов.Представлены две реализации: более современная, которая использует лямбды, и более старая версия, в которой используется явный компаратор.Сравнения пишутся для генерации списка, отсортированного от наименьшего к наибольшему.Чтобы изменить порядок сортировки, измените порядок сравнения.
public void sort(List<Node<String, Integer>> nodes) {
Collections.sort(
nodes,
((Node<String, Integer> n1, Node<String, Integer> n2) -> Integer.compare(n1.value, n2.value)) );
}
public static final Comparator<Node<String, Integer>> NODE_COMPARATOR =
new Comparator<Node<String, Integer>>() {
public int compare(Node<String, Integer> n1, Node<String, Integer> n2) {
return Integer.compare(n1.value, n2.value);
}
};
public void sort(List<Node<String, Integer>> nodes) {
Collections.sort(nodes, NODE_COMPARATOR);
}
(7) Печать полученного отсортированного списка оставлена в качестве упражнения.