由Java中的ArrayList构造N进制树

Question

我试图从一个ArrayList中构造N元树，N元树表示为带有子指针和兄弟指针的二进制。这里是类节点，每个节点元素携带的数据应该通过预购遍历打印出来。

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;

    }   

}

这是类树。

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);

    }

在主程序中，我将根设置为一个parentID为0的节点，并且节点的数组列表是好的。为了添加树节点，我必须有哪个是父节点和哪个是新节点。当调用preorder函数时，它在：preorder（root.child）；我认为这棵树的创建存在一些问题。有什么想法吗？

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

在addTreeNode和find_parentNode方法中做了一些小修改。请尝试以下操作：

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;
}

在main method中，下面是用例：

    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);