How to create a general tree with basic function like insert in java-CodePudding

//I have some basic code written down for the General Tree.

class GeneralTree {
     public static class Node{
         String data;
         ArrayList<Node> link;
         Node(){}
         public void setValue(String data){
            this.data = data;
        }

         public String getValue(){
            return data;
        }
     }
     Node root;
     int degree;
     String type; //shows tree type;

     public GeneralTree(){
         degree = 0;
         root = null;
         type = "";
     }
     public GeneralTree(Node root, int degree){
          this.root = root;
          this.degree = degree;
     }
     public Node getRoot(){return root;}
 }


 public class Hw5 {
 }

I tried searching the internet for explanation on General trees. I understand how they work on paper and can even convert a general tree to Binary on paper, but I do not know how a general tree code implementation will work. Binary tree has right and left childs, they are easy to deal with. on the other hand, general trees have an ArrayList that stores multiple childs, which is the confusing part for me. i do not know how an insert function will look like for this and how I will even traverse this tree.

Need Help With:

Code implementation for general tree.
How an insert function will work for the general tree
if you can direct me to some reading material, that would be amazing too.

CodePudding user response：

A general tree is a tree data structure in which each node can have an arbitrary number of child nodes, rather than a fixed number of child nodes as in a binary tree. In Java, you can implement a general tree using a class that represents a tree node, and a ArrayList to store the child nodes for each node. Here is an example implementation of a general tree in Java:

class GeneralTree {
    // Node class representing a tree node
    public static class Node {
        String data; // Data stored in the node
        ArrayList<Node> children; // List of child nodes

        // Constructor to initialize the node
        public Node(String data) {
            this.data = data;
            this.children = new ArrayList<Node>();
        }

        // Setter and getter methods for the node data
        public void setData(String data) {
            this.data = data;
        }
        public String getData() {
            return this.data;
        }

        // Method to add a child node to the current node
        public void addChild(Node child) {
            this.children.add(child);
        }

        // Method to get the list of child nodes for the current node
        public ArrayList<Node> getChildren() {
            return this.children;
        }
    }

    // Tree class representing the general tree
    Node root; // Root node of the tree
    int degree; // Maximum number of children allowed per node

    // Constructor to initialize the tree
    public GeneralTree() {
        this.root = null;
        this.degree = 0;
    }
    public GeneralTree(Node root, int degree) {
        this.root = root;
        this.degree = degree;

To insert a node into a general tree in Java, you can use the addChild method that was defined in the Node class in the previous example. This method takes a Node object as its argument and adds it to the list of child nodes for the current node.

Here is an example of how the addChild method can be used to insert a new node into a general tree:

// Create a new node with the data to be inserted
Node newNode = new Node("New node data");

// Get the root node of the tree
Node root = tree.getRoot();

// Add the new node as a child of the root node
root.addChild(newNode);

In this example, the newNode is added as a child of the root node using the addChild method. This will add the newNode to the list of child nodes for the root node, and the new node will be part of the general tree.

You can also use the addChild method to insert a node at any other position in the tree, by specifying the parent node where the new node should be added as a child. For example, if you want to insert the newNode as a child of the nth child of the root node, you can do it as follows:

// Get the nth child of the root node
Node nthChild = root.getChildren().get(n);

// Add the new node as a child of the nth child of the root
nthChild.addChild(newNode);

In this example, the newNode is added as a child of the nth child of the root node, which is obtained using the getChildren method. This allows you to insert a node at any position in the general tree, as long as you have a reference to the parent node where the new node should be added.

CodePudding user response：

I find that by looking for the solution by myself I learn much more and it sticks better. I'm not saying that you should do that too, Googling skills are your best way to find what you need faster because when you are a novice you can't put what you are looking for in words (I speak from experience).

Use Github, stackoverflow and Tabnine to find code samples, there are plenty out there (use keywords "general tree java code example"). Have a look at a few examples and try to read the code and understand what is happening. You can run the code in debug mode, put some break points in and step through the execution to see what happens. Debugging is a very useful skill.

You can find some examples of general trees here:

https://github.com/cmilliga/GeneralTreesCollegeWork

https://github.com/Faisal-AlDhuwayhi/Electric-Power-Grid/tree/master/Project-Code/src

Each node can have children Node(s) so the ArrayList is there to keep track of the children for that Node. If you want to add a new Node you need to iterate through the Node and its children.

Hopefully this helps.