Building a search tree in Java

Question

So I¨m building a small game in which I want a search tree with all the possible moves. I¨m having some difficulties implementing the search tree however. I have managed to build a function that can calculate the move but then I¨m not sure how to build the tree, it should be recursivly. Each node should have a list with all possible moves.

public class Tree {
private Node root;
private int level;

public Tree(int level, Board board) {
    this.level = level;
    root = new Node(board);
}


public void add(Board board) {
    int newLevel = board.numberPlacedDiscs();
    if(newLevel>level){
        //Add this at a new level.
        Node newNode =new Node(board);
        newNode.setParent(root);
        root = newNode;

    }else{
        //add at this level.
        root.addChild(new Node(board));
    }
}

}

public class Tree {
    private Node root;
    private int level;

public Tree(int level, Board board) {
    this.level = level;
    root = new Node(board);
}


public void add(Board board) {
    int newLevel = board.numberPlacedDiscs();
    if(newLevel>level){
        //Add this at a new level.
        Node newNode =new Node(board);
        newNode.setParent(root);
        root = newNode;

    }else{
        //add at this level.
        root.addChild(new Node(board));
    }
}

}

As you can see I don't know how to add new Nodes. How do I know when to go down a level in the tree and add more nodes? Everytime a new disc is added to the board it should go down one level.

Answer 1

You can use this method to insert a Node into your tree:

private void insertNode(Node root, Node oldNode, Node newNode) {
        if(root == null) {
           return;
        }

        if(root == oldNode) {
            oldNode.addChild(newNode);
            return;
        }

        for(Node child : root.getChildren()) {
            insertNode(child, oldNode, newNode);
        }
    }

So this method takes three parameters:

• root - this is the root node of your tree.
• oldNode - the node where you want to insert your newNode.
• newNode - this is the node you want to be added to the children of your oldNode.

Node that if you pass a Node that does not exist in your tree, it will not throw any error. But you can modify to do it if you want.

Answer 2

Here is a generic tree in Java

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

public class TreeTest {

    public static void main(String[] args) {

        Tree tree = new Tree("root");
        tree.root.addChild(new Node("child 1"));
        tree.root.addChild(new Node("child 2"));

        tree.root.getChild("child 1").addChild("child 1-1");
        tree.root.getChild("child 1").addChild("child 1-2");

        /*
        root 
        -- child 1
        ---- child 1-1
        ---- child 1-2
        -- child 2
         */
    }

    private static class Tree {
        private Node root;

        Tree(String rootData) {
            root = new Node();
            root.data = rootData;
            root.children = new ArrayList<>();
        }

        public List<Node> getPathToNode(Node node) {
            Node currentNode = node;
            List<Node> reversePath = new ArrayList<>();
            reversePath.add(node);
            while (!(this.root.equals(currentNode))) {
                currentNode = currentNode.getParentNode();
                reversePath.add(currentNode);
            }
            Collections.reverse(reversePath);
            return reversePath;
        }

    }

    static class Node {
        String data;
        Node parent;
        List<Node> children;

        Node() {
            data = null;
            children = null;
            parent = null;
        }

        Node(String name) {
            this.data = name;
            this.children = new ArrayList<>();
        }

        void addChild(String name) {
            this.addChild(new Node(name));
        }

        void addChild(Node child) {
            this.children.add(child);
        }

        void removeChild(Node child) {
            this.children.remove(child);
        }

        public void removeChild(String name) {
            this.removeChild(this.getChild(name));
        }

        public Node getChild(int childIndex) {
            return this.children.get(childIndex);
        }

        Node getChild(String childName) {
            for (Node child : this.children) {
                if (child.data.equals(childName)) {
                    return child;
                }
            }
            return null;
        }

        Node getParentNode() {
            return this.parent;
        }
    }
}

• blog post about generic tree data structure in java

Hope it helps