Home.... | log in.... | Pub my question! | Sign-up....

Java-index >> Java Essentials >> Java Programming

I need help on how to do this BST

a /\ bc / \/ de f\ gand I want it to be | a | b | c | d | e | f | g | 012345 6in an array list, how would I traverse this tree so I can get this arraylist

[231 byte] By [aditya15417a] at [2007-11-27 0:58:37]

«« jsp:include and encoding
»» Deployment to remote Sun App Server

# 1

google Level-order traversal algorithm http://en.wikipedia.org/wiki/Tree_traversal

java_2006a at 2007-7-11 23:32:36 >

top of Java-index,Java Essentials,Java Programming...

# 2

This is not an ordered binary tree. Therefore your solution could be to sort all the nodes in the tree (would require removing and then readding them all) or reiterating over your tree and removing nodes as you find the greatest & least

tjacobs01a at 2007-7-11 23:32:36 >

# 3

say that I have a tree which is already sorted( binary search tree). then what must I do?

aditya15417a at 2007-7-11 23:32:36 >

# 4

Have you studied the Wikipedia article linked in this thread? http://forum.java.sun.com/thread.jspa?threadID=5160067

DrLaszloJamfa at 2007-7-11 23:32:36 >

# 5

I think the level order traversal will work,right?

aditya15417a at 2007-7-11 23:32:36 >

# 6

Yes. In a tree, level-order and breadth-first mean the same thing.

DrLaszloJamfa at 2007-7-11 23:32:36 >

# 7

// Return all keys in this OrderedMap as an ArrayList of Ks.

// The first element in the ArrayList must be key that precedes all other keys.

// The last element must be key that follows all other keys.

public ArrayList<K> keysAsList()

that is actually the method that I have to make, so will the level-order work?

aditya15417a at 2007-7-11 23:32:36 >

# 8

That requirement is incomplete, because it only constrains the first and

last elements. I would think that returning a list where the elements

are totally ordered would be best. This is not required here, but seems

like commonsense to me., since the whole point to a BST is its ordering.

You should already know how to traverse a BST to visit the nodes in order:

http://en.wikipedia.org/wiki/Binary_search_tree

DrLaszloJamfa at 2007-7-11 23:32:36 >

# 9

Yeah it's already a BST so I won't have to order it again. My instructor says to use the in-order method. But then if I use the in-order method wouldn't the first value of the arraylist be a leaf instead of the value in the root?

public ArrayList keysAsList() {

ArrayList result = new ArrayList();

keysAsList(root);

return result;

}

public void keysAsList(TreeNode t){

keysAsList(t.left);

result.add(t.data);

keysAsList(t.right);

}

will this work?

aditya15417a at 2007-7-11 23:32:37 >

# 10

> My instructor says to use the in-order method.

> But then if I use the in-order method wouldn't the

> first value of the arraylist be a leaf instead of the

> value in the root?

I think you are confused about what a BST looks like. Here is the example

from the Wikipedia article:

[url #" style="display: block; background-image: url('http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/150px-Binary_search_tree.svg.png'); width: 150px; height: 125px] [/url]

In a BST, the root does not necessarily contain the least element. Instead, the invariant is that for each node, its value is greater than all the values

in its left subtree and less than all the values in its right subtree.

A breadth-first traversal of this tree yields: [8, 3, 10, 1, 6, 14, 4, 7, 13]

An inorder traversal yields: [1, 3, 4, 6, 7, 8, 10, 13, 14]

DrLaszloJamfa at 2007-7-11 23:32:37 >

# 11

> will this work?Do you have access to a compiler?

DrLaszloJamfa at 2007-7-11 23:32:37 >

# 12

yeah so I think based on the assignment that I have, which is :

The first element in the ArrayList must be key that precedes all other keys.

The last element must be key that follows all other keys.

the in order would be right, correct? Because on the example above 1 preceedes all other values?

My instructor also says that the root value will be somewhere around the size of the arraylist/2

And I don't have an access to a compiler, I am at the library now

aditya15417a at 2007-7-11 23:32:37 >

# 13

Yes, your instructor is correct. Use an inorder traversal. Forget the breadth-first traversal. As for your code, when you compile it, you will see your error.

DrLaszloJamfa at 2007-7-11 23:32:37 >

# 14

if you don't mind could you tell me where the error is? is it because that result is defined in a separated method

aditya15417a at 2007-7-11 23:32:37 >

# 15

cannot find symbolsymbol : variable resultlocation: class Treeresult.add(t.data);^

DrLaszloJamfa at 2007-7-21 19:57:28 >

# 16

so then where should I put this result variable?outside the method and inside a class? should I declare it as a private variable inside the class

aditya15417a at 2007-7-21 19:57:28 >

# 17

public void keysAsList(TreeNode t)add it as a second parameter to this method.

DrLaszloJamfa at 2007-7-21 19:57:28 >

# 18

thanks it helped a lot! I am sorry if I were asking lots of stupid questions

aditya15417a at 2007-7-21 19:57:28 >

# 19

> thanks it helped a lot! I am sorry if I were asking> lots of stupid questionsNo problem. That's what the forums are here for.

DrLaszloJamfa at 2007-7-21 19:57:28 >

# 20

> I think you are confused about what a BST looks like.

> Here is the example

> from the Wikipedia article:

Hmmm...as far as I can recall that is the first time that I have ever seen the ability to be able to post pictures used in a way to help clarify an actual technical discussion.

jschella at 2007-7-21 19:57:28 >

# 21

I apologize. It won't happen again.[url #" style="display: block; background-image: url(' http://mondomonkey.com/MondoMonkeyWhiteHand.jpg'); width: 623px; height: 284px] [/url]

DrLaszloJamfa at 2007-7-21 19:57:28 >

Java programming resources: FAQs, tutorials, compiler and browser download sites, documentation, books lists, IDEs, etc.

I need help on how to do this BST

Java Essentials New Topic

Java Essentials Hot Topic

Java Essentials

All Classified