Last active
December 15, 2015 03:39
-
-
Save astkaasa/5196228 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class BinarySearchTree { | |
private TreeNode root; | |
//private int height; | |
public BinarySearchTree() { | |
root = null; | |
} | |
public BinarySearchTree( TreeNode n ) { | |
this.root = n; | |
} | |
public TreeNode getRoot() { | |
return this.root; | |
} | |
public BinarySearchTree getLeftTree() { | |
return new BinarySearchTree( this.root.getLeft() ); | |
} | |
public BinarySearchTree getRightTree() { | |
return new BinarySearchTree( this.root.getRight() ); | |
} | |
public void BSTTraverse() { | |
if ( this.root != null ) { | |
this.getLeftTree().BSTTraverse(); | |
System.out.print( this.root.getValue() ); | |
System.out.print( "->" ); | |
this.getRightTree().BSTTraverse(); | |
} | |
} | |
public void BSTInsert( TreeNode n ) { | |
TreeNode x = this.root; | |
TreeNode y = null; | |
while ( x!= null ) { | |
y = x; | |
if ( n.getValue() < x.getValue() ) | |
x = x.getLeft(); | |
else x = x.getRight(); | |
} | |
n.setParent( y ); | |
if ( y == null ) | |
this.root = n; | |
else if ( n.getValue() < y.getValue() ) | |
y.setLeft( n ); | |
else y.setRight( n ); | |
} | |
public TreeNode TreeMinimum() { | |
TreeNode x = this.root; | |
while ( x.getLeft() != null ) | |
x = x.getLeft(); | |
return x; | |
} | |
public TreeNode TreeMaximum() { | |
TreeNode x = this.root; | |
while ( x.getRight() != null ) | |
x = x.getRight(); | |
return x; | |
} | |
//recursive TreeSearch method | |
/*public TreeNode TreeSearch( int val ) { | |
if ( this.root == null || val == this.root.getValue() ) | |
return this.root; | |
if ( val < this.root.getValue() ) | |
return this.getLeftTree().TreeSearch( val ); | |
else return this.getRightTree().TreeSearch( val ); | |
}*/ | |
//iterative TreeSearch method | |
public TreeNode TreeSearch( int val ) { | |
TreeNode x = this.root; | |
while ( x != null && val != x.getValue() ) { | |
if ( val < x.getValue() ) | |
x = x.getLeft(); | |
else x = x.getRight(); | |
} | |
return x; | |
} | |
public void TransPlant( TreeNode u, TreeNode v ) { | |
if ( u.getParent() == null ) | |
this.root = v; | |
else if ( u == u.getParent().getLeft() ) | |
u.getParent().setLeft( v ); | |
else u.getParent().setRight( v ); | |
if ( v != null ) | |
v.setParent( u.getParent() ); | |
} | |
public void TreeDelete( TreeNode z ) { | |
if ( z.getLeft() == null ) | |
this.TransPlant( z, z.getRight() ); | |
else if ( z.getRight() == null ) | |
this.TransPlant( z, z.getLeft() ); | |
else { | |
TreeNode y = ( new BinarySearchTree( z.getRight() ) ).TreeMinimum(); | |
if ( y.getParent() != z ) { | |
this.TransPlant( y, y.getRight() ); | |
y.setRight( z.getRight() ); | |
y.getRight().setParent( y ); | |
} | |
this.TransPlant( z, y ); | |
y.setLeft( z.getLeft() ); | |
y.getLeft().setParent( y ); | |
} | |
} | |
public int Height( BinarySearchTree t ) { | |
if ( t.root == null ) | |
return 0; | |
else return ( Math.max( Height( t.getLeftTree() ), Height( t.getRightTree() ) ) + 1 ); | |
} | |
public boolean isBalanced() { | |
if ( this.root == null ) | |
return true; | |
if ( Math.abs( Height( this.getLeftTree() ) - Height( this.getRightTree() ) ) > 1 ) | |
return false; | |
else return ( this.getLeftTree().isBalanced() && this.getRightTree().isBalanced() ); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class BSTTest { | |
public static void main( String[] args ) { | |
BinarySearchTree t = new BinarySearchTree(); | |
t.BSTInsert( new TreeNode( 50 ) ); | |
t.BSTInsert( new TreeNode( 17 ) ); | |
t.BSTInsert( new TreeNode( 12 ) ); | |
t.BSTInsert( new TreeNode( 23 ) ); | |
t.BSTInsert( new TreeNode( 19 ) ); | |
t.BSTInsert( new TreeNode( 14 ) ); | |
t.BSTInsert( new TreeNode( 9 ) ); | |
t.BSTInsert( new TreeNode( 72 ) ); | |
t.BSTInsert( new TreeNode( 54 ) ); | |
t.BSTInsert( new TreeNode( 67 ) ); | |
t.BSTInsert( new TreeNode( 76 ) ); | |
t.BSTTraverse(); | |
System.out.println(); | |
t.TreeDelete( t.TreeSearch( 50 ) ); | |
t.BSTTraverse(); | |
System.out.println(); | |
if ( t.isBalanced() ) | |
System.out.println( "This tree is balanced." ); | |
else System.out.println( "This tree is not balanced." ); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class TreeNode { | |
private int value; | |
private TreeNode parent; | |
private TreeNode left; | |
private TreeNode right; | |
public TreeNode( int val ) { | |
this.value = val; | |
this.parent = null; | |
this.left = null; | |
this.right = null; | |
} | |
public int getValue() { | |
return value; | |
} | |
public void setValue( int val ) { | |
this.value = val; | |
} | |
public TreeNode getParent() { | |
return this.parent; | |
} | |
public TreeNode getLeft() { | |
return this.left; | |
} | |
public TreeNode getRight() { | |
return this.right; | |
} | |
public void setParent( TreeNode n ) { | |
this.parent = n; | |
} | |
public void setLeft( TreeNode n ) { | |
this.left = n; | |
} | |
public void setRight( TreeNode n ) { | |
this.right = n; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment