How to fill a binary tree from a string, java.

Question

Hi, I'm suppose to fill a binary tree with integers based upon a string like this.

 [int](LT)(RT)

LT is an expression of the same form for the left part of the tree. Same with RT. A valid string would be something like this: 4(2(1)(3))(6(5)(7). How can I fill this tree? This is not a sorted tree of any kind. So it can just fill every "level" with nodes. Thank you for help.

Answer 1

grab the first number of the string, split on '(', strip the trailing ')', recursively repeat.

Answer 2

You have to create a parser for that and fill some kind of data structure with the instructions from your parser.

Then when your data structure is filled you just push it into the tree.

Something along the lines:

 Structure s = Parser.parse("4(2(1)(3))(6(5)(7)");

And then iterate the structure.

  Tree binaryTree = ...

  for( Instruction i : s ) {

      if( i.leaf == Tree.LEFT ) {
          tree.addLeft( i.value );
      } else if ( i.leaf == Tree.RIGHT ) {
           tree.addRight( i.value );
      }
  }