CODEWITHSUNDEEP
javabinary-tree
user138980
user138980

Reputation:

How to fill a binary tree from a string, java

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.

Upvotes: 0

Views: 2766

Answers (3)

Brendan Lesniak
Brendan Lesniak

Reputation: 2311

Use a stack to keep track of the '(' and ')'

Push all the '(' onto the stack and pop off when you encounter ')'.

From there, you just have to decide how to interpret the in between stuff for yourself.

Upvotes: 0

OscarRyz
OscarRyz

Reputation: 199215

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

Upvotes: 1

Scott M.
Scott M.

Reputation: 7347

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

Upvotes: 0

Related Questions