package treeplay.tree;
import java.util.LinkedList;
import java.util.List;
import static java.lang.Math.max;
public class SimpleBstTree implements Tree {
@Override
public void add(int value) {
insert(value);
}
@Override
public boolean contains(int value) {
return find(value);
}
private static class Node {
private int value;
private Node leftChild;
private Node rightChild;
public Node(int v) {
this.value = v;
}
@Override
public String toString() {
return "Node={" + this.value + "}";
}
}
private Node root;
private boolean isEmpty() {
return this.root == null;
}
public void insert(int value) {
var node = new Node(value);
if (isEmpty()) {
this.root = node;
return;
}
var current = root;
while (true) {
if (value < current.value) {
if (current.leftChild == null) {
current.leftChild = node;
break;
}
current = current.leftChild;
} else {
if (current.rightChild == null) {
current.rightChild = node;
break;
}
current = current.rightChild;
}
}
}
public boolean find(int value) {
var current = root;
while (current != null) {
if (value < current.value) {
current = current.leftChild;
} else if (value > current.value) {
current = current.rightChild;
} else {
return true;
}
}
return false;
}
private void traversePreOrder(Node root) {
if (root == null) {
return;
}
System.out.print(root.value + " -> ");
traversePreOrder(root.leftChild);
traversePreOrder(root.rightChild);
}
private void traverseInOrder(Node root) {
if (root == null) {
return;
}
traverseInOrder(root.leftChild);
System.out.print(root.value + " -> ");
traverseInOrder(root.rightChild);
}
public void traversePreOrderPrint() {
traversePreOrder(root);
System.out.println();
}
public void traverseInOrderPrint() {
traverseInOrder(root);
System.out.println();
}
@Override
public int height() {
return height(root);
}
private int height(Node root) {
if (root == null) return -1;
if (root.leftChild == null && root.rightChild == null) {
return 0;
}
return max(height(root.leftChild), height(root.rightChild)) + 1;
}
public int minimum() {
if (root == null) {
throw new IllegalStateException();
}
var current = root;
while (current != null) {
if (current.leftChild == null) {
return current.value;
}
current = current.leftChild;
}
return Integer.MIN_VALUE;
}
private boolean isLeaf(Node node) {
return node.leftChild == null && node.rightChild == null;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) return false;
if (obj instanceof SimpleBstTree) {
return equals(((SimpleBstTree) obj).root, this.root);
}
return false;
}
private boolean equals(Node first, Node second) {
if (first == null && second == null) return true;
if (first != null && second != null) {
return first.value == second.value
&& first.leftChild == second.leftChild
&& first.rightChild == second.rightChild;
}
return false;
}
public boolean isBinarySearchTree() {
return isBinarySearchTree(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isBinarySearchTree(Node root, int min, int max) {
if (root == null) return true;
if (root.value < min || root.value > max) {
return false;
}
return isBinarySearchTree(root.leftChild, min, root.value - 1)
&& isBinarySearchTree(root.rightChild, root.value, max);
}
private List<Integer> getNodesAtDistance(int distance) {
var list = new LinkedList<Integer>();
printNodesAtDistance(root, distance, list);
return list;
}
public void printNodesAtDistance(Node root, int distance, List<Integer> list) {
if (root == null) return;
if (distance == 0) {
list.add(root.value);
return;
}
printNodesAtDistance(root.leftChild, distance - 1, list);
printNodesAtDistance(root.rightChild, distance - 1, list);
}
public void levelOrderTraversePrint() {
var h = height();
for(int i=0;i<=h;++i) {
var list = getNodesAtDistance(i);
for(var value:list) {
System.out.print(value+" ->");
}
System.out.println();
}
}
}
import treeplay.tree.SimpleBstTree;
public class Main {
public static void main(String[] args) {
var tree = new SimpleBstTree();
tree.add(-1);
tree.add(41);
tree.add(-100);
tree.add(-100);
tree.add(-100);
tree.traverseInOrderPrint();
System.out.println(
tree.find(3)
);
System.out.println(tree.height());
System.out.println(tree.minimum());
System.out.println(tree.isBinarySearchTree());
tree.levelOrderTraversePrint();
}
}
Processed:
0.018, SQL:
9
