Construire l'arbre N-aire à partir de ArrayList dans Java

Question

J'essaye de construire l'arbre de N-aire à partir d'un ArrayList. L'arbre de N-aire est représenté comme binaire avec des pointeurs d'enfant et de frère. Voici le nœud de classe, chaque élément de nœud transporte des données qui doivent être imprimées avec une traversée de précommande.

public class Node { 


    public String data; 
    public int ID,parentID; 

    public Node child,sibling; 



    public Node(){} 

    public Node(String data,int ID,int parentID) 
    { 
     this.data = data; 
     this.ID = ID; 
     this.parentID = parentID; 

    } 

} 

C'est l'arbre de classe.

public class NTree 
{ 
    public Node root; 

    public NTree(){}  
    public void addTreeNode(Node parent, Node newChild) 
    { 

     if(parent.child == null) 
     { 
      parent.child = newChild;    
      return; 
     } 

     Node temp = parent.child; 

     while(temp.sibling != null) 
     { 
      temp = temp.sibling; 
     } 
     temp.sibling = newChild;   

    } 


    public Node find_parentNode(ArrayList<Node> nodes ,int parentID) 
    { 
     for(int i= 0;i<nodes.size();i++) 
     { 
      if(nodes.get(i).parentID == parentID) 
       return nodes.get(i); 
     } 

     return null; 
    } 

    public void preorder(Node root) 
    { 

      if (root == null) return; 

      System.out.println(root.data); 
      preorder(root.child);   
      preorder(root.sibling); 

    } 

Dans le programme principal, j'ai mis la racine comme un nœud qui a parentID = 0 et liste tableau de nœuds est l'ordre fine.In ajouter nœud d'arbre, je dois avoir ce qui est le nœud parent et qui est le nouveau noeud. Quand la fonction preorder est appelée, elle se bloque au: preorder (root.child); Je pense qu'il y a un problème avec la création de l'arbre. Des idées?

for(int i = 0; i < list_nodes.size(); i++) 
{                 
     Node parent = tree.find_parentNode(list_nodes, list_nodes.get(i).parentID);          
     tree.addTreeNode(parent, list_nodes.get(i));    
} 
tree.preorder(tree.root); 



. ComException in thread "main" java.lang.StackOverflowError 
    at java.io.FileOutputStream.write(Unknown Source) 
    at java.io.BufferedOutputStream.flushBuffer(Unknown Source) 
    at java.io.BufferedOutputStream.flush(Unknown Source) 
    at java.io.PrintStream.write(Unknown Source) 
    at sun.nio.cs.StreamEncoder.writeBytes(Unknown Source) 
    at sun.nio.cs.StreamEncoder.implFlushBuffer(Unknown Source) 
    at sun.nio.cs.StreamEncoder.flushBuffer(Unknown Source) 
    at java.io.OutputStreamWriter.flushBuffer(Unknown Source) 
    at java.io.PrintStream.write(Unknown Source) 
    at java.io.PrintStream.print(Unknown Source) 
    at java.io.PrintStream.println(Unknown Source) 
    at solution.NTree.preorder(NTree.java:77) 
    at solution.NTree.preorder(NTree.java:78) 

Answer 1

Petite modification dans les méthodes addTreeNode et find_parentNode. S'il vous plaît essayer ci-dessous:

public void addTreeNode(Node parent, Node newChild) 
{ 

    if(parent==null){ 
     return; 
    } 
    if(parent.child == null) 
    { 
     parent.child = newChild;    
     return; 
    } 

    Node temp = parent.child; 

    while(temp.sibling != null) 
    { 
     temp = temp.sibling; 
    } 
    temp.sibling = newChild;   

} 


public Node find_parentNode(ArrayList<Node> nodes ,int parentID) 
{ 
    for(int i= 0;i<nodes.size();i++) 
    { 
     if(nodes.get(i).ID == parentID) 
      return nodes.get(i); 
    } 

    return null; 
} 

Dans la méthode principale, ci-dessous est le cas d'utilisation:

NTree tree = new NTree(); 
    tree.root = new Node("A", 1, 0); 
    ArrayList<Node> list_nodes = new ArrayList<Node>(); 
    list_nodes.add(tree.root); 
    list_nodes.add(new Node("B", 2, 1)); 
    list_nodes.add(new Node("C", 3, 1)); 
    list_nodes.add(new Node("D", 4, 1)); 
    list_nodes.add(new Node("E", 5, 3)); 
    list_nodes.add(new Node("F", 6, 3)); 

    for (int i = 0; i < list_nodes.size(); i++) { 
     Node parent = tree.find_parentNode(list_nodes, list_nodes.get(i).parentID); 
     tree.addTreeNode(parent, list_nodes.get(i)); 
    } 
    tree.preorder(tree.root);