Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

Building a tree recursively

Posted on 2004-04-13
14
314 Views
Last Modified: 2013-11-18
I am doing a method to build a tree recursively. But i doubt it would work. Can someone help? I would like to supply this method with the root node, which contains a player's current coordinate in a game board. And then from there to continuously add children to the root node. Children are adjacent coordinates of the root node. I need to recursively build this tree until the depth is = 2. I am not sure if the int depth = 0 thing will overwrite itself in each recursive call or not. can someone check?





public GameTreeNode buildGameTree(GameTreeNode aNode)
       {
             int i=0;
             int depth = 0;
             
             if (depth != 2)
              {
             
                   int pCopy1[] = new int[aNode.player.length]; // cloning 4 copies of the root's coordinate
                   int pCopy2[] = new int[aNode.player.length];
                   int pCopy3[] = new int[aNode.player.length];
                   int pCopy4[] = new int[aNode.player.length];
             
                  System.arraycopy(aNode.player, 0, pCopy1, 0, aNode.player.length);  
                  System.arraycopy(aNode.player, 0, pCopy2, 0, aNode.player.length);
                  System.arraycopy(aNode.player, 0, pCopy3, 0, aNode.player.length);
                  System.arraycopy(aNode.player, 0, pCopy4, 0, aNode.player.length);
            
                  pCopy1[0]++;      // right hand path coordinate
                  pCopy2[0]--;      // left hand path coordinate
                  pCopy3[1]++;      // upper path coordinate
                  pCopy4[1]--;      // down path coordinate
            
                  GameTreeNode child1 = new GameTreeNode(pCopy1); // building 4 nodes a time
                  GameTreeNode child2 = new GameTreeNode(pCopy2);
                  GameTreeNode child3 = new GameTreeNode(pCopy3);
                  GameTreeNode child4 = new GameTreeNode(pCopy4);
            
                  aNode.addChild(child1);   // adding 4 nodes a time...
                  aNode.addChild(child2);
                  aNode.addChild(child3);
                  aNode.addChild(child4);
                  
                  System.out.println("ADDING 4 childs");
                  
                  depth++;
            
                   buildGameTree(aNode.getChildAt(i));
             }
             
       }
0
Comment
Question by:jtcy
  • 6
  • 3
  • 2
  • +2
14 Comments
 
LVL 86

Expert Comment

by:CEHJ
ID: 10813651
>>I am not sure if the int depth = 0 thing will overwrite itself in each recursive call or not

Yes it will. You should make it an instance variable
0
 
LVL 37

Assisted Solution

by:zzynx
zzynx earned 250 total points
ID: 10813715
I won't comment your current code.

But I think a better (OO) approach would be that each TreeNode (knowing at what dept it is) adds its own children.

something like:

class GameTreeNode extends DefaultMutableTreeNode {

    private int myDepth = 0;
 
    public GameTreeNode(Object userObject, int depth) {
         super(userObject);
         myDepth = depth;
         addSubNodes();
    }

    private void addSubNodes() {
         if (myDepth==2)
           return;
         
         // add a subnode (it's constructor will take care of loading its children):
         add( new GameTreeNode(yourUserObject, myDepth+1) );
    }
   
}
0
 

Author Comment

by:jtcy
ID: 10813716
is this the good way of building a tree? I am not sure actually. I mean, considering its performance. Is it fast or slow?
0
Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center

 
LVL 37

Expert Comment

by:zzynx
ID: 10813813
>> You should make it an instance variable
CEHJ means,

make
          int depth

a member of the buildGameTree()'s class.


e.g.

class YourClass {
      private int depth=0;

      public GameTreeNode buildGameTree(GameTreeNode aNode) {
           // int depth = 0;  // <<<< remove this line
      }
}

>> is this the good way of building a tree?
cf. my previous comment (considering the OO design & maintainability)

>> considering its performance
I don't see a problem
Anyway, once you have to create the children.
0
 
LVL 85

Expert Comment

by:Mike Tomlinson
ID: 10817874
An alternative approach would be to pass the depth in to your buildGameTree()  function as one of the parameters.  When you pass in the root node, pass in the depth as zero.  Then increment your depth as you are in code and continue to make your recursive calls.

Idle_Mind
0
 
LVL 1

Accepted Solution

by:
wll9111 earned 250 total points
ID: 10949509
public int minimax(GameState aState, String player, int depth,int alpha, int beta)
     {
           if (target_level == depth)
                   return evaluate(aState);
           else
            {
                  
                 Vector movements = makeMoves(aState);            // create all possible moves...
                     
                     
                     if (player.equals("min"))
                      {
                                  
                                   for (int i = 0; i<movements.size();i++)
                                    {
                                          if (alpha<beta)
                                           {
                                               GameState temp = (GameState)movements.get(i);
                                               int score = minimax(temp,"max",depth+1,alpha,beta);
                                               if (score < beta)
                                                {
                                                      beta = score;
                                                }
                                               
                                            }
                                         return beta;
                                    }
                            
                      }
                 
                 if (player.equals("max"))
                  {
                        
                               for (int j=0;j<movements.size();j++)
                                {
                                      if (alpha<beta)
                                      {
                                           GameState temp2 = (GameState)movements.get(j);
                                           int score2 = minimax(temp2,"min",depth+1,alpha,beta);
                                           if (score2>alpha)
                                            {
                                                  alpha = score2;
                                                  bestScore = alpha;
                                            }
                                                 
                                      }
                                  return alpha;
                                }
                        
                  }
                 
              return bestScore;
                        
           
            }
     
               
     }
0
 
LVL 1

Expert Comment

by:wll9111
ID: 10949540
 public static void main(String[] args) throws java.io.IOException
     {
            FileReader inFile = new FileReader(args[0]);                        // creating two copies of the input file...
            FileReader inFile2 = new FileReader(args[0]);
            
            Yylex lexer = new Yylex(inFile);                                          // creating a lexer...
            Parser parser = new Parser(lexer);                                          // creating a parser...
                                                
            parser.debugParser = true;                                                // debugging tools set off by default...
            parser.printAST = true;
            
            // get the start symbol...
            parser.next_symbol();                                                            
                parser.nProgram();                  
                      
                 // here we create a listing file...
            parser.writeFile(inFile2);

            
    }
   
0
 
LVL 37

Expert Comment

by:zzynx
ID: 10949668
Hi, wll9111, sure you put your comments in the right Q?
0
 
LVL 37

Expert Comment

by:zzynx
ID: 10949769
Strange things are happening here.
16 days wihtout further comments.
And now a comment that at first sight (I'll stay moderate) doesn't have any link to the Q is accepted within minutes.
???

jtcy, could you please comment on this?
0
 

Author Comment

by:jtcy
ID: 10949913
sorry, that;s my course mate. I told him to join here post the solution for me.
0
 
LVL 37

Expert Comment

by:zzynx
ID: 10950012
>> I told him to join here post the solution for me
Is that really the solution to your Q "how to build a tree recursively"?
????  8-O

If you can explain that you certainly deserve a ton of points.
0
 

Author Comment

by:jtcy
ID: 10950046
um...sort of, actually he posted the wrong topic but anyway I asked the question intentioned to how to implement the minimax tree recursively, so yeah.
0
 
LVL 37

Expert Comment

by:zzynx
ID: 10950129
>> actually he posted the wrong topic
There's nothing against posting the right answer (or let it post by someone you know and even accept)
But accepting the wrong answer is not so nice for all the people who'll read this Q in the future...
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Windows 10 IE Certificate Issue 10 51
jboss wildfly 10.1 10 228
JavaFX TableView not displaying correctly 3 55
passing enum to a method 3 18
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

840 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question