ArrayList симметричного обхода в Java

Question

Существует ArrayList некоторого класса со значениями, как

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 

Объект является таким, что он имеет родительский NodeID хранятся (т.е. для узла d3, Parent (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); 

     } 
    } 

} 
} 

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

Answer 1

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

После того, как вы это сделали, обход на месте довольно прост. Он имеет эту схему:

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

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