BSTJun19
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
class Node{
private int value;
private Node left;
private Node right;
public Node(int value){
this.value= value;
}
public int getValue(){
return this.value;
}
public void setValue(int value){
this.value=value;
}
public Node getRight(){
return this.right;
}
public Node getLeft(){
return this.left;
}
public void setRight(Node right){
this.right= right;
}
public void setLeft(Node left){
this.left= left;
}
}
//BinarySearchTree implementation
class Main {
private Node root;
public Main(int rootValue){
this.root= new Node(rootValue);
}
/*public void insertRecursive(int value){
if (value == null){
System.out.println("Cannot insert a null value");
return;
}
/*if (this.root == null){
this.root= new Node(value);
return;
}
if (value < this.root.getValue()){
insertRecursive(this.root.getLeft());
}
if (value > this.root.getValue()){
insertRecursive(this.root.getRight());
}
}*/
public void insertIterative(int value){
Node currentNode = null;
if (this.root ==null){
this.root= new Node(value);
}else {
currentNode = this.root;
}
while (currentNode != null){
if (value < currentNode.getValue()){
if (currentNode.getLeft() != null){
currentNode = currentNode.getLeft();
} else {
currentNode.setLeft(new Node(value));
return;
}
}
if (value > currentNode.getValue()){
if (currentNode.getRight() != null){
currentNode = currentNode.getRight();
} else {
currentNode.setRight(new Node(value));
return;
}
}
}
}
public void lookupIterative(int value){
Node currentNode = this.root;
while (currentNode != null){
if (value == currentNode.getValue()){
System.out.println("Found a match for "+value);
return;
}
if (value < currentNode.getValue()){
if (currentNode.getLeft() != null){
currentNode = currentNode.getLeft();
} else {
currentNode.setLeft(new Node(value));
return;
}
}
if (value > currentNode.getValue()){
if (currentNode.getRight() != null){
currentNode = currentNode.getRight();
} else {
currentNode.setRight(new Node(value));
return;
}
}
}
}
public Node getRoot(){
return this.root;
}
public String traverse(Node node){
String tree = ""+node.getValue();
tree += node.getLeft() != null ? " L:"+ traverse(node.getLeft()) : "";
tree += node.getRight() != null ? " R:"+ traverse(node.getRight()) : "";
return tree;
}
public ArrayList<Node> breathFirstSearchR(Queue<Node> queue, ArrayList<Node> nodesList){
if (queue.isEmpty()){
return nodesList;
}
Node currentNode = queue.poll();
nodesList.add(currentNode);
if (currentNode.getLeft() != null){
queue.add(currentNode.getLeft());
}
if (currentNode.getRight() != null){
queue.add(currentNode.getRight());
}
return breathFirstSearchR(queue, nodesList);
}
public static void main(String[] args) {
Main bst= new Main(9);
bst.insertIterative(4);
bst.insertIterative(20);
bst.insertIterative(1);
bst.insertIterative(6);
bst.insertIterative(15);
bst.insertIterative(170);
bst.lookupIterative(170);
//System.out.println(bst.traverse(bst.getRoot()));
Queue<Node> queue=new LinkedList<Node>();
queue.add(bst.getRoot());
ArrayList<Node> nodesList= bst.breathFirstSearchR(queue, new ArrayList<Node>());
System.out.println("Nodes list: "+nodesList.size());
for (Node node : nodesList){
System.out.print(node.getValue() + " ");
}
}
}
Java
INFO