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

Question

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

在 class 树中，应该有一个构造函数，它接收一个指示树元数的 int 作为输入。

我以前用过普通树，这是我的结果：

Class 树：*

Class节点：*

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

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

Answer 1

创建k-array背后的想法是，这不是像列表或集合这样的常规结构，节点就像链表中的一个元素，它指向 n 个其他 child 节点，也可以指向 parent，确定该结构中的 child 或 parent 是一个完全不同的问题。至于节点中 child 的列表，您可以使用任何您想要的结构 ArrayList 最有可能是一个很好的选择。结构的选择取决于许多因素，如大小、访问频率、是否需要排序等。

Answer 2

这可以作为起点：

节点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);
        }
    }
}

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

请提供有关您的项目规格的更多详细信息，否则我无法确定您需要哪些功能类

Answer 3

这是类的新版本，其中包含您需要的方法。

节点：

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

树：

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

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

Answer 4

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

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

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

K-Ary Tree Implementation in Java: how to?

java

algorithm

tree