遞歸創建樹

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有關嗎？什麼是董事會。

我希望我的捐款能幫助你，我鼓勵你發佈更多詳細信息，以澄清孔，使我幫你多一點。