在Java中構建一個搜索樹

Question

所以，我要構建一個小遊戲，在這個小遊戲中我需要一個包含所有可能動作的搜索樹。但是，在實現搜索樹時遇到一些困難。我設法構建了一個可以計算移動的函數，但是我不知道如何構建樹，它應該是遞歸的。每個節點應該有一個包含所有可能移動的列表。

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的泛型樹數據結構

希望它可以幫助

Answer 2

您可以使用此方法插入Node插入樹中：

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

所以這個方法有三個參數：

• 根 - 這是你的樹的根節點。
• oldNode - 要插入newNode的節點。
• newNode - 這是您想要添加到您的oldNode的孩子的節點。

節點如果你通過了一個Node不存在於你的樹中，它不會拋出任何錯誤。但是，如果你願意，你可以修改。