Построить дерево из заданного массива

== тесты для ссылочного равенства (независимо от того, являются ли они одним и тем же объектом).

.equals() тесты для равенства значений (независимо от того, являются ли они логически «равными»).

Objects.equals () проверяет наличие null перед вызовом .equals(), поэтому вам не нужно (доступно с JDK7, также доступным в Guava ).

String.contentEquals () сравнивает содержимое String с содержимым любого CharSequence (доступно с Java 1.5).

Следовательно, если вы хотите проверить, имеет ли две строки одно и то же значение, вы, вероятно, захотите использовать Objects.equals().

// These two have the same value
new String("test").equals("test") // --> true 

// ... but they are not the same object
new String("test") == "test" // --> false 

// ... neither are these
new String("test") == new String("test") // --> false 

// ... but these are because literals are interned by 
// the compiler and thus refer to the same object
"test" == "test" // --> true 

// ... string literals are concatenated by the compiler
// and the results are interned.
"test" == "te" + "st" // --> true

// ... but you should really just call Objects.equals()
Objects.equals("test", new String("test")) // --> true
Objects.equals(null, "test") // --> false
Objects.equals(null, null) // --> true

Вы почти всегда хотите использовать Objects.equals(). В редкой ситуации, когда вы знаете, что имеете дело с интернированными строками, вы можете использовать ==.

Из JLS 3.10. 5. Строковые литералы :

Кроме того, строковый литерал всегда ссылается на тот же экземпляр класса String. Это связано с тем, что строковые литералы, или, в более общем смысле, строки, которые являются значениями константных выражений ( §15.28 ), «интернированы», чтобы обмениваться уникальными экземплярами, используя метод String.intern.

. Подобные примеры также можно найти в JLS 3.10.5-1 .

0
задан skr 13 July 2018 в 11:08
поделиться

3 ответа

После создания массива TreeNode[] это легко:

TreeNode root = null;
for (int i=0; i<T.length; ++i) {
    if (T[i] == i) { // if it's a root node
        //TODO: Test for multiple root nodes here
        root = nodes[i];
    } else {
        nodes[T[i]].addChild(nodes[i]);
    }
}

Я бы добавил объект private TreeNode parent; в класс TreeNode, инициализировал его до null и установил его в родительская ссылка в методе addChild. Это удобно во время отладки, даже если вам это не нужно для первого использования этого класса. Возможно, вам понадобится это позже.

1
ответ дан Mike Housky 17 August 2018 в 13:15
поделиться
  • 1
    Я хотел бы принять ваш ответ, но результат не совсем корректен. Я запускаю код и получаю: The root = 3 Parent 3 has children = 2 Parent 2 has children = 1 Parent 2 has children = 4 Parent 1 has children = 0 Parent 1 has children = 5 Parent 4 has children = 6 Корень равен 2, а родительский 3 имеет детей = 2, неверно, а фактически наоборот – userX 13 July 2018 в 11:05
  • 2
    @Arefe Это не соответствует данным, предоставленным вами. T[2] = 3 говорит, что 3 является родительским элементом 2, поэтому 2 не может быть корнем. И T[3] = 3 показывает, что у 3 нет родителя, поэтому он является корнем. Существуют ли дополнительные правила и параметры, которые делают 2 корнем? Если да, то что, если 3 действительно было частью дерева, например. T[3] = 7; T[7] = 8; T[8] = 8; T[9] = 8; T[10] = 9; и так далее ...? – Tomek Szpakowicz 13 July 2018 в 11:19
  • 3
    Да, указатель корня K указан там, где вам нужно будет начинать. Таким образом, даже если T [children] = parent, если T [K] = V, то K является родительским элементом V. Как мне изменить код сейчас – userX 13 July 2018 в 11:25
  • 4
    @Mike Я принял ваш ответ с небольшим обновлением – userX 13 July 2018 в 11:43

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

for (int i = 0; i < N; i++) {
    nodes[nodes[i].getValue()].addChild(nodes[i])
}
1
ответ дан Liad Saubron 17 August 2018 в 13:15
поделиться

Я пишу ответ, однако он не показывает всех детей. Код приведен ниже,

public class App {

    static class TreeNode {

        private int value;
        private ArrayList<TreeNode> children;

        public TreeNode(int nodeValue) {
            this.value = nodeValue;
            this.children = new ArrayList<TreeNode>();
        }

        public int getValue() {
            return this.value;
        }

        public void addChild(TreeNode child) {
            this.children.add(child);
        }

        public ArrayList<TreeNode> getChildren() {
            return this.children;
        }
    }


    public static TreeNode buildGraph(int[] T, int K) {

        final int N = T.length;

        TreeNode[] nodes = new TreeNode[N];

        for (int i = 0; i < N; i++) {
            nodes[i] = new TreeNode(i);
        }

        /*
            T[0] = 1
            T[1] = 2
            T[2] = 3
            T[3] = 3
            T[4] = 2
            T[5] = 1
            T[6] = 4

                 2 - 3
                / \
               1   4
              / |  |
             0  5  6
        * */

        TreeNode root = nodes[K];

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        boolean[] visited = new boolean[N];

        while (!queue.isEmpty()) {

            TreeNode node = queue.poll();
            int index = node.getValue();

            visited[index] = true;

            // T[3] = 3 is a leaf with no further connection to develop
            if (index == T[index]) {
                continue;
            }

            // 2 != 3 for the root node and we havent visited node 3 earlier
            if (index != T[index] && !visited[T[index]]) {

                node.addChild(nodes[T[index]]);
                queue.offer(nodes[T[index]]);
            }

            int left = 0, right = N - 1;

            while (left < index && right > index) {

                if (T[left] == index) {

                    node.addChild(nodes[left]);
                    queue.offer(nodes[left]);
                }

                if (T[right] == index) {

                    node.addChild(nodes[right]);
                    queue.offer(nodes[right]);
                }

                left++;
                right--;
            }
        }

        return root;
    }

    public static void main(String[] args) {

        int[] T = new int[7];

        T[0] = 1;
        T[1] = 2;
        T[2] = 3;
        T[3] = 3;
        T[4] = 2;
        T[5] = 1;
        T[6] = 4;

        TreeNode root = buildGraph(T, 2);

        System.out.println("The root = " + root.getValue());

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){

            TreeNode node = queue.poll();

            ArrayList<TreeNode> children = node.getChildren();

            for (int i = 0; i < children.size(); i++) {

                TreeNode child = children.get(i);
                queue.offer(child);

                System.out.println("Parent "+ node.getValue()+ " has children = "+ child.getValue());
            }
        }
    }
}

. В то время, когда я запускаю, я получаю вывод, например,

The root = 2
Parent 2 has children = 3
Parent 2 has children = 1
Parent 1 has children = 0

. Любой может помочь мне исправить, как я пропущу других детей ?

Обновить

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

public static TreeNode buildGraph1(int[] T, int K) {

        final int N = T.length;

        TreeNode[] nodes = new TreeNode[N];

        for (int i = 0; i < N; i++) {
            nodes[i] = new TreeNode(i);
        }

        /*
       T[children] = parent if the children != K

            T[0] = 1
            T[1] = 2
            T[2] = 3
            T[3] = 3
            T[4] = 2
            T[5] = 1
            T[6] = 4

                 2 - 3
                / \
               1   4
              / |  |
             0  5  6
        * */

        TreeNode root = nodes[K];
        int value = root.getValue();

        if (T[K] != K) {
            nodes[K].addChild(nodes[T[K]]);
        }

        for (int i = 0; i < T.length; ++i) {

            if (K == i) {
                continue;
            }

            if (T[i] != i) {
                nodes[T[i]].addChild(nodes[i]);
            }
        }

        return root;
    }

Вывод представлен ниже:

The root = 2
Parent 2 has children = 3
Parent 2 has children = 1
Parent 2 has children = 4




Parent 1 has children = 0
Parent 1 has children = 5


Parent 4 has children = 6
0
ответ дан userX 17 August 2018 в 13:15
поделиться
Другие вопросы по тегам:

Похожие вопросы: