In computer science, a binary search tree, which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:
wikipedia Article
/**
* @author rajeevan
*/
public class BinaryTree <Key extends Comparable<? super Key>> {
private Node root;
class Node{
private Key value;
private Node left;
private Node right;
public Node(Key key){
this.value=key;
}
public Node(Key key,Node left,Node right){
this(key);
this.left=left;
this.right=right;
}
@Override
public String toString(){
return "value="+value+ " left="+left+" right="+right;
}
public void setLeft(Node left){
this.left=left;
}
public void setRight(Node right){
this.right=right;
}
public void setValue(Key value){
this.value=value;
}
public Node getRight(){
return right;
}
public Node getLeft(){
return left;
}
public Key getValue(){
return value;
}
}
//create new binary tree starting with the root value
public BinaryTree(Key value){
this.root =new Node(value);
}
//create new binary tree with empty root
public BinaryTree(){
}
//add a value to the binary Tree
public void addValue(Key value){
this.root=insertValue(value, root);
}
private Node insertValue(Key value,Node node){
int compare=node.getValue().compareTo(value);
if(compare==0){
return node;
}else if(compare>0){
if(node.getLeft()!=null){
node.setLeft(insertValue(value, node.getLeft()));
}else{
node.setLeft(new Node(value));
}
}else if(compare<0){
if(node.getRight()!=null){
node.setRight(insertValue(value, node.getRight()));
}else{
node.setRight(new Node(value));
}
}
return node;
}
//search the tree for a value
public boolean searchTree(Key value){
return this.searchTree(value,root);
}
private boolean searchTree(Key value,Node node){
if(node==null){
return false;
}
if(node.getValue().equals(value)){
return true;
}else if(node.getValue().compareTo(value)<0){
return searchTree(value,node.getRight());
}else if(node.getValue().compareTo(value)>0){
return searchTree(value, node.getLeft());
}else{
return false;
}
}
public Key findMin() {
return this.findMin(root);
}
private Key findMin(Node node){
if(node.getLeft()==null){
return node.getValue();
}else{
return findMin(node.getLeft());
}
}
//return the minimum value of the tree
public Key findMax() {
return this.findMax(root);
}
private Key findMax(Node node){
if(node.getRight()==null){
return node.getValue();
}else{
return findMax(node.getRight());
}
}
public void removeValue(Key value){
this.removeValue(value,root);
}
private Node removeValue(Key value,Node node){
if(node.getValue().compareTo(value)>0){
node=removeValue(value,node.getLeft());
}else if(node.getValue().compareTo(value)<0){
node=removeValue(value,node.getRight());
}else if(node.getLeft()!=null&& node.getRight()!=null){
Key max=this.findMax(node.getLeft());
node.setValue(max);
node.setLeft(this.removeValue(max,node.getLeft())) ;
}else{
if(node.getLeft()==null&&node.getRight()==null){
node=null;
}else{
Key k=node.getLeft()==null?node.getRight().getValue():node.getLeft().getValue();
node.setValue(k);
}
}
return node;
}
}
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
wikipedia Article
/**
* @author rajeevan
*/
public class BinaryTree <Key extends Comparable<? super Key>> {
private Node root;
class Node{
private Key value;
private Node left;
private Node right;
public Node(Key key){
this.value=key;
}
public Node(Key key,Node left,Node right){
this(key);
this.left=left;
this.right=right;
}
@Override
public String toString(){
return "value="+value+ " left="+left+" right="+right;
}
public void setLeft(Node left){
this.left=left;
}
public void setRight(Node right){
this.right=right;
}
public void setValue(Key value){
this.value=value;
}
public Node getRight(){
return right;
}
public Node getLeft(){
return left;
}
public Key getValue(){
return value;
}
}
//create new binary tree starting with the root value
public BinaryTree(Key value){
this.root =new Node(value);
}
//create new binary tree with empty root
public BinaryTree(){
}
//add a value to the binary Tree
public void addValue(Key value){
this.root=insertValue(value, root);
}
private Node insertValue(Key value,Node node){
int compare=node.getValue().compareTo(value);
if(compare==0){
return node;
}else if(compare>0){
if(node.getLeft()!=null){
node.setLeft(insertValue(value, node.getLeft()));
}else{
node.setLeft(new Node(value));
}
}else if(compare<0){
if(node.getRight()!=null){
node.setRight(insertValue(value, node.getRight()));
}else{
node.setRight(new Node(value));
}
}
return node;
}
//search the tree for a value
public boolean searchTree(Key value){
return this.searchTree(value,root);
}
private boolean searchTree(Key value,Node node){
if(node==null){
return false;
}
if(node.getValue().equals(value)){
return true;
}else if(node.getValue().compareTo(value)<0){
return searchTree(value,node.getRight());
}else if(node.getValue().compareTo(value)>0){
return searchTree(value, node.getLeft());
}else{
return false;
}
}
public Key findMin() {
return this.findMin(root);
}
private Key findMin(Node node){
if(node.getLeft()==null){
return node.getValue();
}else{
return findMin(node.getLeft());
}
}
//return the minimum value of the tree
public Key findMax() {
return this.findMax(root);
}
private Key findMax(Node node){
if(node.getRight()==null){
return node.getValue();
}else{
return findMax(node.getRight());
}
}
public void removeValue(Key value){
this.removeValue(value,root);
}
private Node removeValue(Key value,Node node){
if(node.getValue().compareTo(value)>0){
node=removeValue(value,node.getLeft());
}else if(node.getValue().compareTo(value)<0){
node=removeValue(value,node.getRight());
}else if(node.getLeft()!=null&& node.getRight()!=null){
Key max=this.findMax(node.getLeft());
node.setValue(max);
node.setLeft(this.removeValue(max,node.getLeft())) ;
}else{
if(node.getLeft()==null&&node.getRight()==null){
node=null;
}else{
Key k=node.getLeft()==null?node.getRight().getValue():node.getLeft().getValue();
node.setValue(k);
}
}
return node;
}
}