Solved

how to construct a binary tree from an array of data

Posted on 2013-11-10
10
442 Views
Last Modified: 2013-11-11
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;
        }
    }

Open in new window

and the node:
public Node(E data) {
            this.data = data;
            left = null;
            right = null;
        }

Open in new window

And an array of strings:
String[] data = {"Kyle", "Robert", "Sammy", "Duke", "Shadow", "Fish1", "Fish2", "Fish3"};

Open in new window

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.

somebody please help me... :( (I'm too embarrassed to post what I tried.)

I don't care about the order right now, I just want a complete tree without duplicates.
0
Comment
Question by:Kyle Hamilton
  • 4
  • 3
  • 3
10 Comments
 
LVL 26

Accepted Solution

by:
dpearson earned 334 total points
ID: 39637435
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++) {
  addToTree(root, data[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
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39637457
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
 
LVL 35

Assisted Solution

by:mccarl
mccarl earned 166 total points
ID: 39637584
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
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39637618
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
 
LVL 35

Expert Comment

by:mccarl
ID: 39637665
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);
}

Open in new window

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
What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

 
LVL 26

Expert Comment

by:dpearson
ID: 39637774
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
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39638947
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
 
LVL 26

Assisted Solution

by:dpearson
dpearson earned 334 total points
ID: 39639764
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
 
LVL 25

Author Closing Comment

by:Kyle Hamilton
ID: 39639868
thanks guys - I'll be back :)
0
 
LVL 35

Expert Comment

by:mccarl
ID: 39640344
Your welcome! :)
0

Featured Post

Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

Join & Write a Comment

Suggested Solutions

Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues unde…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:

747 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

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now