I am trying to implement a breadth first search tree. I need to be able to go up and down the tree, and on each layer there can be varying amounts of nodes on each one. My problem is I've never made a tree before, and i don't know how they are implemented. can anyone get me headed in the right direction?
bobrien314
- 2 Contributors
- forum1 Reply
- 5 Views
- 9 Years Discussion Span
- comment Latest Post by BestJewSinceJC
BestJewSinceJC 700
I got this off of another forum, from what I remember of Data Structures, it is the correct information on how to do a breadth first search of a tree. Their directions indicate that the tree is Binary (only has two nodes), but you can use the same algorithm on your tree, just add every node from left to right. As it says, it uses a queue to store the nodes during the breadth first search. You should make a random tree on paper and apply this algorithm to see how it works.
1. Add root node to queue if not null
2. Check if queue is empty, if not remove first item from queue which will be the root node initially and store it in a variable called currentnode
3. Print the value currentnode
4. If currentnode has leftnode, add leftnode to end of queue
5. If currentnode has rightnode, add rightnode to end of queue
6. Processing of currentnode finished, jump to step 2, rinse and repeat
Oh, and if you don't know how to make a tree, you can do so by making a 'Node' class that has two items: The data that is at the current node (this might just be an Integer), and an ArrayList of the child nodes. You'll have to implement an 'addNode' and a 'removeNode' method, maybe more methods.