递归创建一棵树

本文介绍了递归创建一棵树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我试图递归地填充一棵树，但我的代码只填写一个深度长度，然后退出.即每个节点只有一个子节点.有什么地方没有考虑到吗?

I am trying to recursively populate a tree, but my code is only only fill out one depth length, and then quiting. i.e. each node only has one child. Is there something am failing to take in to consideration?

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

附言然后我检查 noOfEmpty() 返回值，它应该确定一个节点应该有的子节点数.

P.S. and i check the noOfEmpty() return value, which should determine the number of children a node should have.

@eznme 要求的完整代码:

edit:@eznme the complete code as requested:

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;

import java.io.IOException;

公共类 Main {

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

}

推荐答案

所以这就是我在你的情况下会做的事情 (minimax tic-tac-toe):

So here is what I would do in your case (minimax tic-tac-toe):

术语:

• 一个节点的高度:从这个节点到它更远的叶子的距离.
• 一个节点的深度:从树的根到这个节点的距离.

• Height of a node: Distance from this node to it's further leaf.
• Depth of a node: Distance from the root of the tree, to this node.

您必须不断尝试所有情况，直到:棋盘已满或一名玩家获胜.所以，你的树的高度是 numberOfCells + 1.如果我们简化问题并且不担心对称重复:每个节点都有 numberOfcells - nodeDepth 子节点.

You have to keep trying all cases until: the board is full OR one player won. So, your tree's height is numberOfCells + 1. If we simplify the problem and don't worry about symmetric duplicates: Each node will have numberOfcells - nodeDepth childs.

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

节点类:

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