• Status: Solved
• Priority: Medium
• Security: Public
• Views: 491

how to construct a binary tree from an array of data

I have this binary tree constructor:
``````public BinaryTree(E data, BinaryTree<E> leftTree, BinaryTree<E> rightTree) {
root = new Node<E>(data);
if (leftTree != null) {
root.left = leftTree.root;
} else {
root.left = null;
}
if (rightTree != null) {
root.right = rightTree.root;
} else {
root.right = null;
}
}
``````
and the node:
``````public Node(E data) {
this.data = data;
left = null;
right = null;
}
``````
And an array of strings:
``````String[] data = {"Kyle", "Robert", "Sammy", "Duke", "Shadow", "Fish1", "Fish2", "Fish3"};
``````
and I'm doing my head in trying to figure out how to create a tree from my array. I tried using a for loop, but it just looks really weird, and doesn't work anyway.

I don't care about the order right now, I just want a complete tree without duplicates.
0
Kyle Hamilton
• 4
• 3
• 3
3 Solutions

Commented:
The approach you want to take is to start with one Node:

Node root = new Node(data[0]) ;   // In your case this will contain Kyle.

Then you need to write a piece of code that inserts the others one at a time, so you want a method like this:

public void addToTree(Node node, String newValue) {
}

which you will call in a loop:

for (int j = 1 ; j < data.length ; j++) {
}

Does that make sense?  If you can write the addToTree() method then this would build up the binary tree?

This looks like it may be a homework project, so I don't think it's appropriate for me to write that method for you, but let me give you an outline and see if that helps.

Inside addToTree(Node node, String newValue) what you need to decide is:
a) Is the newValue to the 'left' or 'right' of the current node.
(Strings that are alphabetically before other strings generally go to the left, String.compare() may be useful here).

Let's assume in this case it's to the left.
b) See if there's more tree to the left of the current node.
If there is no subtree to the left, then you should add a new node to the tree in that spot.
If there is an existing subtree to the left, you need to repeat the whole process for the subtree to the left.

So that's a lot of English to explain what is actually a pretty small amount of code :)

I hope it helps get you started in the right direction.

Good luck,

Doug
0

Data ScientistAuthor Commented:
Thanks Doug,

This is not a homework assignment, just my effort to learn data structures on my own. I'm using a textbook, so that's probably why it smells like homework.

I was trying to not add any methods to the tree implementation class I'm working working with, because in my naivete, I assumed that the implementation from the book i'm reading is complete, and I should be able to use the constructor provided to build my tree. Was that a silly assumption? Is there a way to build the tree just using the constructor I posted above?

thanks so much for helping.
0

IT Business Systems Analyst / Software DeveloperCommented:
I don't care about the order right now
I think you DO need to compare about order, otherwise there is no reason to be even thinking about "binary trees" and you could just add each node as the "left" (or "right") member of the one before it.

Is there a way to build the tree just using the constructor I posted above?
Whether the code that you write (that uses this constructor) is located elsewhere or in a method like Doug is explaining is largely irrelevant. The point is that there is code that needs to be written, ie. obviously there is not just ONE call that can be made to the constructor to build the entire tree, so you need to write "something". So whether that code is in a method as part of the tree implementation or not, doesn't really matter.

Also, one thing that may or may not be obvious is that, just ONE BinaryTree object is not enough to represent the whole tree. The whole tree is actually a series of BinaryTree objects that are connected together, and therefore the constructor HAS to be called multiple times to build all the objects. So, yeah, you need more code to do this creation.

I would follow Doug's advice in his post above, and post back here if you still have further questions!
0

Data ScientistAuthor Commented:
mccarl,

thanks so much. i understand i have to call the constructor more than once. i guess where i got stuck was in a crazy for loop that was building a much bigger tree than what was needed with duplicate nodes all over the place. as far as ordering, i was going to take that leap once i got a handle on just building the tree in the first place - baby steps :)

for tonight, my brain is pixel juice. i will come back to this in the morning and post back.

thanks for helping - really appreciate it.
0

IT Business Systems Analyst / Software DeveloperCommented:
The reason that I say that the order is important, is because an alternative is this...
``````BinaryTree<String> tree = null;
for (String item : data) {
tree = new BinaryTree<String>(item, tree, null);
}
``````
After the above code, "tree" will contain a valid binary tree. It won't be much use to you because a) there is no order to it and b) it is as far "unbalanced" as you can get for a binary tree, BUT it is still a binary tree.

You could also have a more "balanced" tree still with no order in it, but you will be putting more work into doing that than you would be in doing it properly!

But yeah, probably something that you want to be considering with a fresh mind! ;)

(Also, if you want to post the FULL files for the above classes, we can provide pointers on better ways to represent them. Just from the parts of the code that you posted, it doesn't look like it is the most normal way of doing that)
0

Commented:
This is not a homework assignment, just my effort to learn data structures on my own. I'm using a textbook, so that's probably why it smells like homework.

OK that's fair.  Go ahead and have another go at the code and if you get stuck post what you have here and we'll try to help some more.

Doug
0

Data ScientistAuthor Commented:
so I took you guys advice and abandoned my tree in favor of the Binary Search Tree. The example in the book provides an add method that builds the tree, and is essentially what Doug proposed, with the exception of the initial root node. They've done some fancy shenanigans that encapsulate the Node class, so I don't have access to it. However, their add method creates the root if one doesn't exist.

So I got away with not having to do that part of the exercise :). On the plus side, I was able to successfully write the various traversal methods that were missing from the implementation. Yay for me :)

I just have one last question related to the BinaryTree:

Say I want to build an expression tree, wouldn't this be a case for a regular tree, not a search tree? My data would come provided in a certain order, and based on that, I would have to build the tree - not like a search tree where left is smaller, right is bigger...

And why do we have expression trees? Why not just use a stack? (to do postfix calculations, that is)

Thanks :)
0

Commented:
Yes that's right - for an expression tree you need to keep the original order because the order of the operations in the original expression matters.

You are also right that you can just use a stack in some cases instead of an expression tree.  Forth was a classic language that was entirely implemented as a stack - you just kept adding values to the stack and then running calculations by popping the current parameters off the stack.

A tree is generally simpler to conceptualize (since it in some sense looks like the original expression) and allows you to traverse the tree in different orders if you need to.  However, for a given specific traversal ordering (e.g. postfix) you can always convert a tree into a stack and vice versa.

Doug
0

Data ScientistAuthor Commented:
thanks guys - I'll be back :)
0

IT Business Systems Analyst / Software DeveloperCommented:
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.