Обход inorder в Java

Question

Существует массив некоторых классов со значениями

Node,Depth,Value
root,0,-2147483647
d3,1,4
e3,2,0
c5,2,0
c3,2,-3
c4,1,4
e3,2,0
c5,2,0
c3,2,-3
e6,1,4
d6,2,0
f4,2,0
f6,2,-3
f5,1,4
d6,2,0
f4,2,0
f6,2,-3

Объект таков, что в нем хранится идентификатор родительского узла (т. Е. Для узла d3, родительский (d3)-root. Отношение таково, что все узлы ниже данного узла X с depth=X.depth+1 его дети. Итак, коренные дети это: d3,c4,f5,e6 d3 дети это: c3,e3,c5

Теперь я должен написать некоторый код для генерации обхода по нему. что-то вроде:

root,0,-2147483647
d3,1,4
e3,2,0
d3,1,4
c5,2,0
d3,1,4
c3,2,-3
d3,1,4
root,0,-2147483647
c4,1,4
e3,2,0
c4,1,4
c5,2,0
c4,1,4
c3,2,-3
c4,1,4
root,0,-2147483647
e6,1,4
d6,2,0
e6,1,4
f4,2,0
e6,1,4
f6,2,-3
e6,1,4
root,0,-2147483647
f5,1,4
d6,2,0
f5,1,4
f4,2,0
f5,1,4
f6,2,-3
f5,1,4
root,0,-2147483647

Я написал метод Java, как это

private static void inordertraversal() {

ListIterator <nextmove> iter = nmstack.listIterator();
while(iter.hasNext())
{
    nextmove node=iter.next();
    if(node.depth==CutoffDepth)
    {
        maxdepth=true;
    }

    if (!maxdepth)
    {
        System.out.println(node.To.Name+","+node.depth+","+node.weight);

    }
    else
    {
        nextmove parent=findparent(node.parent);
        if (node.parent!=0)
        {   
        System.out.println(node.To.Name+","+node.depth+","+node.weight);
        System.out.println(parent.To.Name+","+parent.depth+","+parent.weight);

        }
        else
        {
            System.out.println(parent.To.Name+","+parent.depth+","+parent.weight);
            System.out.println(node.To.Name+","+node.depth+","+node.weight);

        }
    }

}
}

Но это не ОБЩЕЕ (если глубина увеличивается / изменяется, она не будет работать), а также неполное. Как сделать этот обход inorder от arraylist у меня есть. Предположим, что Arraylist имеет имя узла, его глубину и серийный номер его родителя. Может ли кто-нибудь дать мне указатель? Это не бинарное дерево.

Answer 1

Во-первых, вы абсолютно хотите взять ArrayList и сначала построим дерево из него. Вы действительно не хотите пробовать обход структуры данных по порядку, пока она все еще представлена ​​в виде ArrayList, Это твое первое задание.

Как только вы это сделаете, обход по порядку довольно прост. У него есть такая схема:

1. рекурсивно исследовать левого ребенка;
2. обработать этот узел;
3. рекурсивно исследовать правильного ребенка.

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