java - 在 Java 中构建搜索树

Question

所以我正在构建一个小游戏，我想要一个包含所有可能 Action 的搜索树。然而，我在实现搜索树时遇到了一些困难。我设法构建了一个可以计算移动的函数，但我不确定如何构建树，它应该是递归的。每个节点都应该有一个包含所有可能移动的列表。

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

如您所见，我不知道如何添加新节点。我怎么知道什么时候在树中向下一个级别并添加更多节点？每次将新光盘添加到板上时，它都应该下降一个级别。

Answer 1

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关于java中的泛型树数据结构

希望对你有帮助