java Java中的K-Ary树实现：如何？

K-Ary Tree Implementation in Java: how to?

提问by steexd

I've a university project about creating two classes, Tree class and Node class, to implement a k-ary tree using Java.

我有一个关于创建两个类，树类和节点类的大学项目，以使用 Java 实现 k-ary 树。

In the class Tree, there should be a constructor which recives as input an int that indicates the tree arity.

在类 Tree 中，应该有一个构造函数，它接收一个表示树 arity 的 int 作为输入。

I've worked before with general trees and this was my result:

我以前处理过一般的树，这是我的结果：

Class tree: *

类树：*

Class node: *

类节点：*

I absolutely don't know where and how to start to build this project (as I don't know how to manage the arity, maybe with ArrayList?).

我绝对不知道从哪里以及如何开始构建这个项目（因为我不知道如何管理 arity，也许使用 ArrayList？）。

Any advice and suggestions will be greatly appreciated :) Thanks in advance.

任何意见和建议将不胜感激:) 提前致谢。

回答by L Petre

Here are the new versions of the classes, with the methods that you needed.

以下是这些类的新版本，以及您需要的方法。

Node:

节点：

import java.util.ArrayList;
import java.util.List;

public class Node {

    public Node parent; // The parent of the current node
    public List<Node> children; // The children of the current node
    public Object info;

    public static int maxNrOfChildren; // Equal to the k-arity; 

    public Node (Object info)
    {
        this.info=info; 
        children  = new ArrayList<Node>(maxNrOfChildren);
    }

    public void addChild(Node childNode, int position)
    // You must take care so that future insertions don't override a child on i-th position
    {
        if(position>=maxNrOfChildren-1)
        {
            // Throw some error
        }

        else
        {
            System.out.println("this.children="+this.children);
            if(this.children.get(position)!=null)
            {
                // There is alerady a child node on this position; throw some error;
            }
            else
            {
                childNode.parent=this;
                this.children.set(position, childNode);
            }
        }
    }
}

Tree:

树：

import java.util.ArrayList;
import java.util.List;

public class Tree {
    public Node root;

    public Tree(int kArity)
    {
        Node.maxNrOfChildren=kArity;        
    }

    public void addRoot(Object info)
    {
        root=new Node(info);
        root.parent=null;
        root.children=new ArrayList<Node>(Node.maxNrOfChildren);
    }

    public void addNewNodeVasithChildOfNodeU(Node u, Object info, int i)
    {
        Node child=new Node(info);
        u.addChild(child, i);
    }

    // I've made the above two methods of type void, not Node, because
    // I see no reason in returning anything; however, you can override by calling
    //'return root;' or 'return child;'

    public int numberOfNodesInTree(Node rootNode){
        int count=0;

        count++;
        if(rootNode.children.size()!=0) {
            for(Node ch : rootNode.children)
                count=count+numberOfNodesInTree(ch);
        }

        return count;
    }

    public int numberOfNodesInTree()
    {
        return numberOfNodesInTree(this.root);
    }

    public void changeRoot(Node newRoot, int i)
    {
        Node oldRoot=this.root;
        newRoot.parent=null;
        newRoot.addChild(oldRoot, i);
        oldRoot.parent=newRoot;
        this.root=newRoot;
    }

    public static void main(String args[])
    {
        Tree tree=new Tree(3);
        Node a = new Node("a");
        Node b = new Node("b");
        Node c = new Node("c");

        tree.addRoot("root");
        tree.root.addChild(a,0);
        a.addChild(b,0);
        tree.root.addChild(c,1);
        System.out.println(tree.numberOfNodesInTree(tree.root));
    }
}

The logic is correct, but I am getting some Java-related error when I run the main method and I haven't yet figured out what the problem is.

逻辑是正确的，但是当我运行 main 方法时出现了一些与 Java 相关的错误，我还没有弄清楚问题是什么。

回答by L Petre

this can be a starting point:

这可以是一个起点：

Node Class

节点类

import java.util.ArrayList;
import java.util.List;

public class Node {

    public Node parent;//the parent of the current node
    public List<Node> children = new ArrayList<Node>();//the children of the current node
    public String name;//or any other property that the node should contain, like 'info'

    public static int maxNrOfChildren;//equal to the k-arity; 

    public Node (String nodeName)
    {
        name=nodeName; 
    }



    public void addChild(Node childNode)
    {
        if(this.children.size()>=maxNrOfChildren)
        {
            //do nothing (just don't add another node), or throw an error
        }
        else
        {
            childNode.parent=this;
            this.children.add(childNode);
        }
    }
}

Tree Class

树类

import java.util.ArrayList;
import java.util.List;

public class Tree {


    public Node root = new Node("root");

    public Tree(int kArity)
    {
        Node.maxNrOfChildren=kArity;
        root.parent=null;
    }

    public void traverseTree(Node rootNode)//depth first
    {
        System.out.println(rootNode.name);
        if(rootNode.children.size()!=0)
            for(Node ch : rootNode.children)
                traverseTree(ch);
    }


    public static void main(String args[])
    {
        Tree tree=new Tree(3);
        Node a = new Node("a");
        Node b = new Node("b");
        Node c = new Node("c");

        tree.root.addChild(a);
        a.addChild(b);
        tree.root.addChild(c);
        tree.traverseTree(tree.root);
    }
}

Please give further details about your project specifications, otherwise i can't figure out which kind of functionality you need within these classes

请提供有关您的项目规范的更多详细信息，否则我无法弄清楚您在这些类中需要哪种功能

回答by Samuel Audet Arsenault

The idea behind creating a k-array, is that this is not a conventional structure like a list or a set, the node is like an element in a linked list, it point to the n other child node and can also point to the parent, whant determine what should be the child or the parent in that sctructure is an entire different question. As for the list of child in the node you can use any structure you whant ArrayList most likely will be a good fit. The choice of a structure depend on many factors like size, how often it will be accessed does it need to be sorted etc.

创建 k-array 背后的想法是，这不是像列表或集合这样的传统结构，节点就像链表中的一个元素，它指向第 n 个子节点，也可以指向父节点，要确定该结构中的孩子或父母应该是什么是一个完全不同的问题。至于节点中的孩子列表，您可以使用任何您希望 ArrayList 最适合的结构。结构的选择取决于许多因素，例如大小、访问的频率、是否需要对其进行排序等。

回答by Nithin Sivakumar

Have a look at this. Hope it helps.

看看这个。希望能帮助到你。

import java.util.ArrayList;

public class Nary
{
public static Node root;

public static int insert(Node rootNode, int parentId, ArrayList<Node> nodeToAdd)
{
    if(rootNode == null)
        return 0;
    if(rootNode.children == null)
        rootNode.children = new ArrayList<Node>();
    if(rootNode.id == parentId)
    {
        for(int i =0; i < nodeToAdd.size(); i++)
        {
            Node node = nodeToAdd.get(i);
            node.parent = rootNode;
            rootNode.children.add(node);
        }
        return 1;
    }
    else
    {
        for(int i = 0; i < rootNode.children.size(); i++)
        {
            int resultFlag = insert(rootNode.children.get(i), parentId, nodeToAdd);
            if(resultFlag == 1)
            {
                return 1;
            } 

        }
    }
    return -1;
}

public static void traverse(Node root)
{
    if(root == null)
    {
        return;
    }

    System.out.println(root.data + " " + root.id );
    for(Node child : root.children)
    {
        traverse(child);
    }

}

public static void main(String[] args) {

    // Insertion
    root = new Node(0, "root");
    int parentId = root.id;

    Node Bread = new Node(1, "Bread");
    Node Milk = new Node(2, "Milk");
    Node Meat = new Node(3, "Meat");
    Node Eggs = new Node(4, "Eggs");

    ArrayList<Node> nodeList = new ArrayList<Node>();
    nodeList.add(Bread);
    nodeList.add(Milk);
    nodeList.add(Meat);
    nodeList.add(Eggs);

    insert(root, parentId, nodeList);


    // Add children for Bread
    parentId = Bread.id;

    Node Bread0 = new Node(11, "Whole-Wheat");
    Node Bread1 = new Node(12, "Whole-Grain");
    Node Bread2 = new Node(13, "Italian");

    ArrayList<Node> nodeList1 = new ArrayList<Node>();
    nodeList1.add(Bread0);
    nodeList1.add(Bread1);
    nodeList1.add(Bread2);

    insert(root, parentId, nodeList1);

    Add children for Milk
    parentId = Milk.id;

    Node Milk0 = new Node(21, "Whole");
    Node Milk1 = new Node(22, "skim");
    Node Milk2 = new Node(23, "Almond");

    ArrayList<Node> nodeList2 = new ArrayList<Node>();
    nodeList2.add(Milk0);
    nodeList2.add(Milk1);
    nodeList2.add(Milk2);

    insert(root, parentId, nodeList2);

    traverse(root);

 }
 }

class Node{

int id;
String data;
Node parent;
ArrayList<Node> children;
public Node(int id, String data)
{
    this.id = id;
    this.data = data;
}
}