BinarySearchTree
public class BinarySearchTree {
private Node root;
public BinarySearchTree() {
// TODO Auto-generated constructor stub
root=null;
}
public void insertBST(char data){
Node newNode = new Node();
newNode.data = data;
if(root ==null){
root = newNode;
}else{
Node temp = root;
while(temp != null){
if(newNode.data > temp.data){
if(temp.right == null){
temp.right = newNode;
return;
}else{
temp = temp.right;
}
}else{
if(temp.left==null){
temp.left = newNode;
return;
}else{
temp = temp.left;
}
}
}
}
}
public void printBST(){
inorder(root);
System.out.println();
}
public Node searchBST(char x){
Node temp = root;
while(temp != null){
if(temp.data <x){
temp= temp.right;
}else if(temp.data >x){
temp = temp.left;
}else if(temp.data == x){
break;
}
}
return temp;
}
public void inorder(Node root){
if(root!=null){
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}
public void deleteBST(Node delNode){
if(root ==null){
System.out.println("Tree is empty");
return;
}else{
Node temp = root;
Node parant = root;
while(temp != null){
if(temp.data < delNode.data){
parant = temp;
temp = temp.right;
}else if(temp.data > delNode.data){
parant = temp;
temp = temp.left;
}else{
if(temp.left == null && temp.right == null){
if(parant.left == temp){
parant.left = null;
}else{
parant.right = null;
}
}else if(temp.left == null || temp.right ==null){
if(parant.left==temp){
if(temp.left != null){
parant.left = temp.left;
}else{
parant.left = temp.right;
}
}else{
if(temp.left != null){
parant.right = temp.left;
}else{
parant.right = temp.right;
}
}
}else{
parant = temp;
temp = temp.left;
while(temp.right != null){
parant = temp;
temp = temp.right;
}
delNode.data = temp.data;
if(parant.left == temp){
parant.left = null;
}else{
parant.right = null;
}
}
return;
}
}
}
}
}
Main
public class Main {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.insertBST('G');
bst.insertBST('I');
bst.insertBST('H');
bst.insertBST('D');
bst.insertBST('B');
bst.insertBST('M');
bst.insertBST('N');
bst.insertBST('A');
bst.insertBST('J');
bst.insertBST('E');
bst.insertBST('Q');
System.out.print("\nBinary Tree >>> ");
bst.printBST();
System.out.print("Is There \"A\" ? >>> " );
Node p1 = bst.searchBST('A');
if(p1 != null){
System.out.println("Searching Success! Searched key : " + p1.data );
}else{
System.out.println("Searching fail!! tehre is no A");
}
System.out.print("Is There \"Z\" ? >>> " );
Node p2 = bst.searchBST('Z');
if(p2 != null){
System.out.println("Searching Success! Searched key : " + p2.data );
}else{
System.out.println("Searching fail!! tehre is no Z");
}
bst.deleteBST(p1);
bst.printBST();
p2 = bst.searchBST('I');
bst.deleteBST(p2);
bst.printBST();
p2 = bst.searchBST('M');
bst.deleteBST(p2);
bst.printBST();
p2 = bst.searchBST('D');
bst.deleteBST(p2);
bst.printBST();
}
}
Node
public class Node {
Node left;
Node right;
char data;
public Node() {
// TODO Auto-generated constructor stub
left = null;
right = null;
}
}
'플밍 is 뭔들 > 자료구조' 카테고리의 다른 글
| 05-7 힙의 구현 (0) | 2016.11.25 |
|---|---|
| 05-6 힙 (0) | 2016.11.25 |
| 05-4 이진 탐색 트리 (0) | 2016.11.25 |
| 05-3 이진 트리의 구현 및 순회 (0) | 2016.11.25 |
| 05-2 이진 트리 (0) | 2016.11.25 |
