Сортировка предиката, чтобы уделить узлы в глубине первого порядка поиска

Question

У меня есть список узлов, где каждый из узлов принадлежит к одному или нескольким деревьям. (Они не обязательно разделяют общего предка)

Я хочу сортировать узлы в том же порядке, в котором я найду их при выполнении первого поиска глубины.

Давайте скажем, у меня есть предикат для сортировки корней деревьев вместе, и еще один предикат, чтобы вместе составить детей общего родителя. У каждого узла есть родительский аксессу и рассчитанник детей. Я хочу избежать использования перечисления детей по причинам производительности (если возможно).

Что может быть псевдокодом для предиката, чтобы передать функцию сортировки (предикат вернет логическое значение, если узел 1 меньше, чем узел 2).

Answer 1

Я нашел простое рабочее решение:

Для узла выполните функцию, которая возвращает путь из корня. Например, в файловой системе путь для файла может быть: C: Directory file.txt, где «C:», «Directory» и «file.txt» являются родительскими узлами.

Предикат просто должен сравнивать пути вместе, как было бы простое сравнение строк. Путь не должен быть строкой, функция сравнения пути должна сравнивать элементы пути один за другим, начинающееся в корне, и вернуть, как только элемент пути отличается.

Полученный вид такой же, как в первом поиске глубины.

Answer 2

Я думаю, что вам нужно хранить полезную информацию в узлах, поэтому предикат может выбрать предыдущий узел из пары не связанных узлов.

Вот моя (может быть не очень умна или даже, работающая) попытка:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 *
 */
public class SortingTree {

    private static class Node implements Comparable<Node> {
        private final String data;
        private Node p, l, r;

        private int ordinal = 0;

        public Node(String data) {
            this.data = data;
        }

        public Node setLeft(Node n) {
            n.ordinal = ordinal + 1;
            if (ordinal == 0)
                n.ordinal = 2;
            else
                n.ordinal = ordinal + 2;
            n.p = this;
            return n;
        }

        public Node setRight(Node n) {
            if (ordinal == 0)
                n.ordinal = 1;
            else
                n.ordinal = ordinal + 4;
            n.p = this;
            return n;
        }

        public String toString() {
            return data;
        }


        public int compareTo(Node o) {
            // check if one of args is root
            if (p == null && o.p != null) return -1;
            if (p != null && o.p == null) return 1;
            if (p == null && o.p == null) return 0;

            // check if one of args is left subtree, while other is right
            if (ordinal % 2 == 0 && o.ordinal % 2 == 1) return -1;
            if (ordinal % 2 == 1 && o.ordinal % 2 == 0) return 1;

            // if ordinals are the same, first element is the one which parent have bigger ordinal
            if (ordinal == o.ordinal) {
                return o.p.ordinal - p.ordinal;
            }
            return ordinal - o.ordinal;
        }
    }

    public static void main(String[] args) {
        List<Node> nodes = new ArrayList<Node>();

        Node root = new Node("root"); nodes.add(root);
        Node left = root.setLeft(new Node("A")); nodes.add(left);
        Node leftLeft = left.setLeft(new Node("C")); nodes.add(leftLeft); nodes.add(leftLeft.setLeft(new Node("D")));
        nodes.add(left.setRight(new Node("E")));

        Node right = root.setRight(new Node("B")); nodes.add(right);
        nodes.add(right.setLeft(new Node("F"))); nodes.add(right.setRight(new Node("G")));

        Collections.sort(nodes);
        System.out.println(nodes);
    }
}