levelorder(root)
q = empty queue
q.enqueue(root)
while not q.emptydo
node := q.dequeue()
visit(node)
if node.left ≠null
q.enqueue(node.left)
if node.right ≠null
q.enqueue(node.right)
and how would I put all the values here instead of in queue it's in an arraylist?
That's not C++. Think of it as pseudo code.
What trouble are you having translating it into Java? -- it seems pretty straightforward.
And q can be any datatype that implements a FIFO queue. If you feel
you must, you could do that with an ArrayList, although a LinkedList
seems more natural. What difference does it make? q is a temporary
structure used to drive the algorithm.
> what do you mean the data structure is empty?
The algorithm is mainly a loop: while not q.empty do
After this loop, the testcondition must be false, so q.empty is true.
> here queue has ability to deque and enque, how about for arraylist?
Yes. Take a look at the List API. You can add elements on one end and remove
them from the order. But again, why are you so insistent about ArrayList?
What difference does it make?
http://java.sun.com/javase/6/docs/api/java/util/List.html
> because the assignment says so.
The assignment says "use a ArrayList" to perform a level-order (or breath-first)
traversal of a tree?
> what it means by visit root
I think you mean visit(node). Clearly, this is an algorithm to traverse a tree.
What should it do at each node? Method visit represents that action. So
visit is whatever you want it to be. What do you want your traversal to do?
Define visit accordingly.
> because the assignment says so. and I dont really get
> here on the pseudocode of what it means by visit root
This looks to me like a breadth first traversal of a binary tree, using a queue as a helper.
It has two elements involved: iteration (this is everything that has to do with the queue), and "visiting", which is the operation you perform on each node of the tree.
Try googling for the "Visitor" design pattern. That should help you understand what's going on here.
- Adam
> well no actually it didn't say that, so I just use
> the queue and store the data elemets in the ArrayList
> right? the queue is only a helper to get the
> results...... What data structure should I use with a
> queue
You haven't been clear in this thread, but I think what you are
trying to express is that you want the traversal to generate a list
of nodes, stored in the order of their traversal. You could certainly
use any class that implements List for that. As for q, any class that
implements List or Queue will work for that, too.
As I mentioned in the other thread, your requirement "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" can be satisfied by more than one type
of traversal. Why did you choose this particular one?
OK, an example:
We have the following tree:e
/ \
/\
cf
/ \\
bdg
/
a
And we have your (borrowed) pseudo code:levelorder(root)
q = empty queue
q.enqueue(root)
while not q.empty do
node := q.dequeue()
visit(node)
if node.left ≠ null
q.enqueue(node.left)
if node.right ≠ null
q.enqueue(node.right)
Now, when you call levelorder(root), where root = node e, this is what happens:levelorder('e') {// contents of queue
new queue// [ ]
queue.enqueue('e')// ['e']
while(queue is not empty) {
node = queue.dequeue() = 'e'// [ ]
if('e'.left is not null) {
queue.enqueue('c')// ['c']
}
if('e'.right is not null) {
queue.enqueue('f')// ['c', 'f']
}
// The end of the while here, but since
// the queue is not empty, we continue
node = queue.dequeue() = 'c'// ['f']
if('c'.left is not null) {
queue.enqueue('b')// ['f', 'b']
}
if('c'.right is not null) {
queue.enqueue('d')// ['f', 'b', 'd']
}
// The end of the while here, but since
// the queue is not empty, we continue
node = queue.dequeue() = 'f'// ['b', 'd']
if('f'.left is not null) {
-
}
if('f'.right is not null) {
queue.enqueue('g')// ['b', 'd', 'g']
}
// The end of the while here, but since
// the queue is not empty, we continue
node = queue.dequeue() = 'b'// ['d', 'g']
if('b'.left is not null) {
queue.enqueue('a')// ['d', 'g', 'a']
}
if('b'.right is not null) {
-
}
// The end of the while here, but since
// the queue is not empty, we continue
node = queue.dequeue() = 'd'// ['g', 'a']
if('d'.left is not null) {
-
}
if('d'.right is not null) {
-
}
// The end of the while here, but since
// the queue is not empty, we continue
node = queue.dequeue() = 'g'// ['a']
if('g'.left is not null) {
-
}
if('g'.right is not null) {
-
}
// The end of the while here, but since
// the queue is not empty, we continue
node = queue.dequeue() = 'a'// [ ]
if('a'.left is not null) {
-
}
if('a'.right is not null) {
-
}
// The queue is empty, stop looping
}
}
Now if you look at the order of the dequeue sequence, you'll see the level-order traversal of the tree. Now when you dequeue each node from your queue, you could put those nodes inside an ArrayList (which seems what you're after).
Good luck.
Woops! I just realized something is wrong here. If this is your requirement:
// 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.
Then a level-order (breadth-first) traversal is incorrect.
Consider this BST:
[url #" style="display: block; background-image: url('http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/300px-Binary_search_tree.svg.png'); width: 300px; height: 250px] [/url]
A level-order traversal will generate the list: [8, 3, 10, 1, 6, 14, 4, 7, 13]
where you need a traversal that satisfies [1, ?, ?, ?, ?, ?, ?,?, 14],
for example [1, 3, 4, 6, 7, 8, 10, 13, 14]. Now what traversal satisfies that?
Take a look at the article on BST again: http://en.wikipedia.org/wiki/Binary_search_tree
> well no actually it didn't say that, so I just use
> the queue and store the data elemets in the ArrayList
> right? the queue is only a helper to get the
> results...... What data structure should I use with a
> queue
You could use a LinkedList. It's easy because it implements the Queue interface. You add elements at the end (enque) and pick them up at the front (deque).
Where it says visit(node) you just add the node to an ArrayList. When the algoritm finishes the node order in the ArralyList will be breath-first.
> Again, if the current thread is about this
> assignment:
> http://forum.java.sun.com/thread.jspa?threadID=5160317
>
> You may want to reconsider using a level-order
> (breadth-first) traversal
> of a BST, because it will give you the wrong
> answer.
Why is the breath-first order wrong?
> Why is the breath-first order wrong?
Please see reply #14 in this thread. If the tree is a BST, the root doesn't
contain the least element. The left-most node does, so a breadth-first
search will not visit the least element first, as required by the OP (assuming
his two threads are about the same thing).
> > Why is the breath-first order wrong?
>
> Please see reply #14 in this thread. If the tree is a
> BST, the root doesn't
> contain the least element. The left-most node does,
> so a breadth-first
> search will not visit the least element first, as
> required by the OP (assuming
> his two threads are about the same thing).
Well if it's a BST and the OP wants to visit the nodes in sorted order he should do a standard recursive in-order search.
> True. But the OP has been stuck on this problem for
> some time
> and has started numerous threads asking variations on
> the same question.
> I keep pointing to the BST article that has a
> traversal section,
> but I don't know if it has clicked or sunk in, to mix
> metaphors.
And even at other forums,
http://www.codeguru.com/forum/showthread.php?t=420637
He seems to have adopted the annoying strategy of not wanting to clearly understand and present his own problem. Instead he reposts other people's attemts to understand him in the hope that they might know more than he does about what he wants. -:)
> ...
> And even at other forums,
>
> http://www.codeguru.com/forum/showthread.php?t=420637
>
> He seems to have adopted the annoying strategy of not
> wanting to clearly understand and present his own
> problem. Instead he reposts other people's attemts to
> understand him in the hope that they might know more
> than he does about what he wants. -:)
Makes one wonder what the real assignment is...
; )
