递归创建树

Question

我试图递归填充一棵树，但我的代码只只填写一个深度的长度，然后在quiting。即每个节点只有一个孩子。有没有事情没有考虑到？

public static void populate(Node n, int depth, String player){ 
    System.out.println("Depth: " + depth); 
    if(player.equalsIgnoreCase("X")) 
     player = "O"; 
    else 
     player = "X"; 
    int j = 0; 
    System.out.println("empty spots: " + ((Board)n.getData()).noOfEmpty()); 
    for(int i=0; i<((Board)n.getData()).noOfEmpty(); i++){ 
     if(((Board)n.getData()).getSquare(j).equalsIgnoreCase("X") 
       || ((Board)n.getData()).getSquare(j).equalsIgnoreCase("O")) 
      j++; 
     else{ 
      Board tmp = new Board(((Board)n.getData()), j, player); 
      Node newNode = new Node(tmp); 
      tree.insert(n, newNode); 
      populate(newNode, depth-1, player); 
     } 
    } 
} 

P.S.我检查noOfEmpty()返回值，它应该确定一个节点应该有的子节点的数量。

编辑：@eznme的完整代码的要求：

public class MinMax { 

    protected static Tree tree; 


    public static void createTree(Board b){ 
     tree = new Tree(); 
     tree.setRoot(new Node(b)); 
     populate(tree.getRoot(), 5, "X"); 
     //System.out.println("printing tree"); 
     //tree.print(1); 
    } 

    public static void populate(Node n, int depth, String player){ 
     System.out.println("Depth: " + depth); 
     if(player.equalsIgnoreCase("X")) 
      player = "O"; 
     else 
      player = "X"; 
     int j = 0; 
     System.out.println("empty spots: " + ((Board)n.getData()).noOfEmpty()); 
     for(int i=0; i<((Board)n.getData()).noOfEmpty(); i++){ 
      if(((Board)n.getData()).getSquare(j).equalsIgnoreCase("X") 
        || ((Board)n.getData()).getSquare(j).equalsIgnoreCase("O")) 
       j++; 
      else{ 
       Board tmp = new Board(((Board)n.getData()), j, player); 
       Node newNode = new Node(tmp); 
       tree.insert(n, newNode); 
       populate(newNode, depth-1, player); 
      } 
     } 
    } 
} 

import java.util.ArrayList; 

/** 
* 
* @author Greg 
*/ 
public class Node { 

    protected Object data; 
    protected int score; //fields to be used by the MaxMin class 
    protected ArrayList<Node> children; 

    //constructors 
    public Node(){ 
     children = new ArrayList(0); 
     data = null; 
    } 
    public Node(Object obj){ 
     children = new ArrayList(0); 
     data = obj; 
    } 


    public void setChild(Node n){ 
     //EFFECT: set the ith child to node t 
     children.add(n); 
    } 
    public void setChildren(Node[] t){ 
     //EFFECT: copy the array t, into the array children, effectively 
     // setting all the chidern of this node simultaneouly 
     int l = children.size(); 
     for(int i=0; i<t.length; i++){ 
      children.add(l, t[i]); 
     } 
    } 
    public void setData(Object obj){ 
     //EFFECT: set the date of this node to obj, and also set the number of 
     // children this node has 
     data = obj; 
    } 
    public Node getChild(int i){ 
     //EFFECT: returns the child at index i 
     return children.get(i); 
    } 

    public int noOfChildren(){ 
     //EFFECT: return the length of this node 
      return children.size(); 
    } 

    public Object getData(){ 
     //EFFECT: returns the data of this node 
     return data; 
    } 

    @Override 
    public String toString(){ 
     //EFFECT: returns the string form of this node 
     return "" + data.toString() + "\nwith " + noOfChildren()+ "\n"; 
    } 

    public boolean isLeaf(){ 
     if(children.size()==0) 
      return true; 
     return false; 
    } 


    public void setScore(int scr){ 
     score = scr; 
    } 

    public int getScore(){ 
      return score; 
    } 
} 

public class Tree { 

    private Node root; 

    public Tree(){ 
     setRoot(null); 
    } 

    public Tree(Node n){ 
     setRoot(n); 
    } 

    public Tree(Object obj){ 
     setRoot(new Node(obj)); 
    } 

    protected Node getRoot(){ 
     return root; 
    } 

    protected void setRoot(Node n){ 
     root = n; 
    } 

    public boolean isEmpty(){ 
     return getRoot() == null; 
    } 

    public Object getData(){ 
     if(!isEmpty()) 
      return getRoot().getData(); 
     return null; 
    } 

    public Object getChild(int i){ 
     return root.getChild(i); 
    } 

    public void setData(Object obj){ 
     if(!isEmpty()) 
      getRoot().setData(obj); 
    } 

    public void insert(Node p,Node c){ 
     if(p != null) 
      p.setChild(c); 
    } 

    public void print(int mode){ 
     if(mode == 1) pretrav(); 
     else if(mode == 2) postrav(); 
     else 
      System.out.println("yeah... mode 1 or 2...nothing else, try agn"); 
    } 

    public void pretrav(){ 
     pretrav(getRoot()); 
    } 

    protected void pretrav(Node t){ 
     if(t == null) 
      return; 
     System.out.println(t.getData()+" \n"); 
      for(int i=0; i<t.noOfChildren(); i++) 
       pretrav(t.getChild(i)); 
    } 

    public void postrav(){ 
     postrav(getRoot()); 
    } 

    protected void postrav(Node t){ 
     if(t == null) 
      return; 
     System.out.print(t.getData()+" "); 
      for(int i=0; i<t.noOfChildren(); i++) 
       pretrav(t.getChild(i)); 
     System.out.print(t.getData()+" "); 
    } 
} 

public class Board { 

    boolean isFull = false;   // a check to see if the board is full 
    String[] grid = new String[9]; //an array represting the 9 square on a board 
    int hV; 
    String MIN, MAX; 

    public Board(){ 
     for(int i=0; i<grid.length;i++) 
      grid[i] = Integer.toString(i); 
     hV = heuristicValue(this); 
    } 

    public Board(Board b, int x, String player){ 
     this.grid = b.getBoard(); 
     if(!(grid[x].equalsIgnoreCase("X")|| grid[x].equalsIgnoreCase("X"))) 
      grid[x] = player; 
    } 

    public boolean setSquare(String player, int position){ 
     /* 
     EFFECT:set a square on the board to either a X or a O, debending on the player 
     PRECON: square (x,y) is empty 
     POATCON: square (x,y) has player 'symbol' 
     */ 

     boolean isValidPlay = false; 
     try{ 
      //as a sanity 
      Integer.parseInt(grid[position]); 
      grid[position] = player; 
      isValidPlay = true; 

     }catch(NumberFormatException e){ 
      System.out.println("positon " + position + "is already occupied"); 
     } 
     return isValidPlay; 
    } 

    public boolean endGame(){ 
     /* 
     * EFFECT: check to see if the game have been won or drawn 
     */ 
     if(ticTacToe(0,1,2)){ 
      //System.out.println("Player " + grid[0] + " wins"); 
      return true; 
     } 
     else if(ticTacToe(3,4,5)){ 
      //System.out.println("Player " + grid[3] + " wins"); 
      return true; 
     } 
     else if(ticTacToe(6,7,8)){ 
      //System.out.println("Player " + grid[6] + " wins"); 
      return true; 
     } 
     else if(ticTacToe(0,4,8)){ 
      //System.out.println("Player " + grid[0]+ " wins"); 
      return true; 
     } 
     else if(ticTacToe(0,3,6)){ 
      //System.out.println("Player " + grid[0]+ " wins"); 
      return true; 
     } 
     else if(ticTacToe(1,4,7)){ 
      //System.out.println("Player " + grid[1] + " wins"); 
      return true; 
     } 
     else if(ticTacToe(2,5,8)){ 
      //System.out.println("Player " + grid[2] + " wins"); 
      return true; 
     }else if(ticTacToe(2,4,6)){ 
      //System.out.println("Player " + grid[2] + " wins"); 
      return true; 
     } 
     else 
      return isDrawn(); 
    } 

    public boolean ticTacToe(int x, int y, int z){ 
     /* 
     * check is x, y and z has the same value 
     */ 
     try{ 
      Integer.parseInt(grid[x]); 
      return false; 
     }catch(NumberFormatException e){ 
     if(grid[x].equals(grid[y]) 
       && grid[x].equals(grid[z])) 
      return true; 
     else 
      return false; 
     } 
    } 

    public String getSquare(int i){ 
     return grid[i]; 
    } 

    @Override 
    public String toString(){ 
     String msg = ""; 
     for(int i=0; i<grid.length; i++){ 
      msg = msg + grid[i] + " "; 
      if(i==2 || i==5) 
       msg = msg+ "\n"; 
     } 
     return msg; 
    } 

    public boolean isDrawn(){ 
     /* 
     * check to see if there are any 'free' spaces on the board, if there are any 
     * return false, else return true 
     */ 
     for(int i=0; i<grid.length; i++){ 
     try{ 
      Integer.parseInt(grid[i]); 
      return false; 
      }catch(NumberFormatException e){ 
      } 
     } 
     System.out.println("Game drawn"); 
     return true; 
    } 

    public String[] getBoard(){ 
     return grid; 
    } 

    public int noOfEmpty(){ 
     //EFFECT: returns the number of empty squares 
     int count = 0; 
     for(int i=0; i<grid.length; i++) 
      if (!(grid[i].equalsIgnoreCase("X") || grid[i].equalsIgnoreCase("O"))) 
       count++; 
     return count; 
    } 

    public int heuristicValue(Board b){ 
     String MAX = "X", MIN = "O"; 
     /* 
     * calculate a value that will be used as a heuristic function 
     * the function works for ever X in a row WITHOUT O: 1 point, 
     * for two X in a row WITHOUT a O: 5 points 
     * and 3 X in a row: 100 points 
     */ 
     //System.out.println("Computing heuristic"); 
     //System.out.println("Computing horizontals"); 
     int hCount = 0; 
     //sum up the horizontals 
     for(int i=0; i<9; i=i+3){ 
      int tmpMAX = playerCount(b, MAX,i,i+1,i+2); 
      int tmpMIN = playerCount(b, MIN,i,i+1,i+2); 
      //System.out.println(tmpMAX); 
      //System.out.println(tmpMIN); 
      if(tmpMIN > 0){ 
       //System.out.println("Min was zero"); 
      } 
      else if(tmpMAX==1){ 
       //System.out.println("has one"); 
       hCount = hCount + 1; 
      } 
      else if(tmpMAX==2){ 
       //System.out.println("was tw0"); 
       hCount = hCount + 5; 
      } 
      else if(tmpMAX==3){ 
       //System.out.println("full 100"); 
       hCount = hCount + 100; 
      } 
     } 
     //System.out.println("Computing verticals"); 
     //sum up the verticals 
     for(int i=0; i<3; i++){ 
      int tmpMAX = playerCount(b, MAX,i,i+3,i+6); 
      int tmpMIN = playerCount(b, MIN,i,i+3,i+6); 
      if(tmpMIN > 0){} 
      else if(tmpMAX==1){ 
       hCount = hCount +1; 
      } 
      else if(tmpMAX==2){ 
       hCount = hCount + 5; 
      } 
      else if(tmpMAX==3){ 
       hCount = hCount + 100; 
      } 
     } 
     //System.out.println("Computing diagonals"); 
     //sum up diagonals 
     if(playerCount(b, MIN,0,4,8)==0){ 

      if(playerCount(b, MAX,0,4,8)==1){ 
       hCount = hCount + 1; 
      } 
      if(playerCount(b, MAX,0,4,8)==2) 
       hCount = hCount + 5; 
      if(playerCount(b, MAX,0,4,8)==3) 
       hCount = hCount + 100; 
     } 
     if(playerCount(b, MIN,2,4,6)==0){ 

      if(playerCount(b, MAX,2,4,6)==1){ 
       hCount = hCount + 1; 
      } 
      if(playerCount(b, MAX,2,4,6)==2) 
       hCount = hCount + 5; 
      if(playerCount(b, MAX,2,4,6)==3) 
       hCount = hCount + 100; 
     } 
     //System.out.println("Computing completed"); 
     int hV = hCount; 
     return hV; 
    } 

    int playerCount(Board b, String player, int x, int y, int z){ 
     int count = 0; 
     if(b.getSquare(x).equals(player)) 
      count = count + 1; 
     if(b.getSquare(y).equals(player)) 
      count = count + 1; 
     if(b.getSquare(z).equals(player)) 
      count = count + 1; 
     //System.out.println("playerCount; " + count); 
     return count; 
    } 
} 

import java.io.*; 

进口产生java.io.IOException;

公共类主要{

public static void main(String[] args) throws IOException{ 
    BufferedReader reader = new BufferedReader(new 
              InputStreamReader(System.in)); 
    Board thisGame = new Board(); 
    System.out.println("Start \n" + thisGame.toString()); 
    MinMax.createTree(thisGame); 
    System.exit(0); 
} 

}

Answer 1

所以这里是我会在你的情况做（极小井字棋）：

术语：

• 节点的高度：从这个节点到它的距离是进一步叶。节点的
• 深度：从树的根部的距离，到该节点。

您必须继续尝试所有情况，直到董事会已满或赢得一名玩家。所以，你的树的高度是numberOfCells + 1。 如果我们简化问题并且不担心对称副本： 每个节点将有numberOfcells - nodeDepth孩子。

public static void main(String[] args){ 
    Tree t = new Tree(); 
    int nbCells = 9; 
    t.setRoot(buildTree(new Board(nbCells), 0, -1)); 
} 

public static Node buildTree(Board b, int player, int positionToPlay){ 
    if(player != 0){ 
     b.setCellAt(positionToPlay, player); 
    } 
    Node n = new Node(b, b.nbEmptyCells()); 

    int j = 0; 
    for(int i = 0; i < b.nbCells(); i++){ 
     if(b.getCellAt(i) == 0) 
      n.setChildAt(j++, buildTree(new Board(b), changePlayer(player), i)); 
    } 

return n; 
} 

public static int changePlayer(int p){ 
    switch(p){ 
    case 0: 
     return 1; 
    case 1: 
     return 2; 
    case 2: 
     return 1; 
    default: 
     return 0; 
    } 
} 

Node类：

public class Node { 
    private Board board; 
    private Node[] childs; 

    public Node(Board b, int nbChilds){ 
     this.board = new Board(b); 
     this.childs = new Node[nbChilds]; 
    } 

    public Node getChildAt(int i){ 
     return childs[i]; 
    } 

    public int nbChilds(){ 
     return childs.length; 
    } 

    public void setChildAt(int i, Node n){ 
     this.childs[i] = n; 
    } 

    public Board getBoard(){ 
     return this.board; 
    } 

Answer 2

为了递归构建一个N叉树，我这样做：

​​

我希望它能帮助。

节点创建与此算法中（在二叉树）的秩序：

   1 
     2    9 
    3  6  10  13 
4 5 7 8 11 12 14 15 

Answer 3

我觉得你有一种错误的做法。 首先，你正在做一个循环和递归，除了使用depth变量没有意义，因为你永远不会检查它的价值，要么结束递归，要么知道你想做什么。 一个动态的功能循环本身内使用是不太好，因为迭代应该从循环的开始被明确定义。 i是在你的背景只是无用。

所以，如果我理解你的代码，有问题的情况是，其中有3米空的广场和4米非空的广场，因为你会遍历i从0到3，什么也不做，但是从0到3，然后退出递增j的情况下，因为i将会达到3.

当然，我可能会误解一些观点，因为我不知道tree是从哪里来的？它与n有关吗？什么是董事会。

我希望我的捐款能帮助你，我鼓励你发布更多详细信息，以澄清孔，使我帮你多一点。