/**
* @author Ilham Yuliantoro 105090600111029
*/
import java.util.Scanner;
class Node {
int Data;
Node AnakKiri;
Node Anakkanan;
}
class Tree{
public Node root;
public Tree(){
root=null;
}
public void insert (int d){
Node NodeBaru= new Node();
NodeBaru.Data=d;
if(root==null)
root=NodeBaru;
else{
Node current=root;
Node parent;
while(true){
parent=current;
if(d
current=current.AnakKiri;
if (current==null){
parent.AnakKiri=NodeBaru;
return;
}
}
else{
current=current.Anakkanan;
if (current==null){
parent.Anakkanan=NodeBaru;
return;
}
}
}
}
}
public boolean delete(int x){
Node current=root;
Node parent=root;
boolean Kiri = true;
if (root!=null){
while (current!=null){
if (x==current.Data){
if(root.Data==current.Data){
Node succes=getSuccessor(current);
succes.AnakKiri=current.AnakKiri;
succes.Anakkanan=current.Anakkanan;
root=succes;
}
else
if(Kiri)
if(current.Anakkanan!=null&¤t.AnakKiri!=null){
Node succes=getSuccessor(current);
succes.AnakKiri=current.AnakKiri;
succes.Anakkanan=current.Anakkanan;
parent.AnakKiri=succes;
}
else if(current.AnakKiri!=null)
parent.AnakKiri=current.AnakKiri;
else if(current.Anakkanan!=null)
parent.AnakKiri=current.Anakkanan;
else
parent.AnakKiri=null;
else
if(current.Anakkanan!=null&¤t.AnakKiri!=null){
Node succes=getSuccessor(current);
succes.AnakKiri=current.AnakKiri;
succes.Anakkanan=current.Anakkanan;
parent.Anakkanan=succes;
}
else if(current.AnakKiri!=null)
parent.Anakkanan=current.AnakKiri;
else if(current.Anakkanan!=null)
parent.Anakkanan=current.Anakkanan;
else
parent.Anakkanan=null;
break;
}
else if (current.Data
parent=current;
Kiri=false;
current=current.Anakkanan;
}
else {
parent=current;
Kiri=true;
current=current.AnakKiri;
}
}
if(current.AnakKiri==null && current.Anakkanan==null){
if(current==root)
root=null;
else if (Kiri)
parent.AnakKiri=null;
else
parent.Anakkanan=null;
}
else if(current.Anakkanan==null)
if(current == root)
root = current.AnakKiri;
else if(Kiri)
parent.AnakKiri = current.AnakKiri;
else
parent.Anakkanan = current.Anakkanan;
else if(current.AnakKiri==null)
if(current == root)
root = current.Anakkanan;
else if(Kiri)
parent.AnakKiri = current.Anakkanan;
else
parent.Anakkanan = current.Anakkanan;
else {
Node successor = getSuccessor(current);
if(current == root)
root = successor;
else if(Kiri)
parent.AnakKiri = successor;
else
parent.Anakkanan = successor;
successor.Anakkanan = current.Anakkanan;
}
}
return true;
}
public Node getSuccessor(Node S){
Node successorParent = null;
Node successor = S;
Node current = S.AnakKiri;
while(current != null){
successorParent = successor;
successor = current;
current = current.Anakkanan;
}
if(successor != S.AnakKiri){
successorParent.Anakkanan = successor.AnakKiri;
successor.AnakKiri = S.AnakKiri;
}
return successor;
}
public int Find_Min(){
Node current = root;
int min=0;
while (current != null){
min=current.Data;
current=current.AnakKiri;
}
return min;
}
public int Find_Max(){
Node current = root;
int max=0;
while (current!= null){
max=current.Data;
current=current.Anakkanan;
}
return max;
}
public boolean find(int x){
Node current = root;
while(current!= null){
if (current.Data==x)
return true;
if(x < current.Data)
current = current.AnakKiri;
else
current = current.Anakkanan;
}
return false;
}
public void swap(int a,int b){
if(find(a)){
delete(a);
insert(b);
}
}
public void inOrder(Node z){
if(z != null){
inOrder(z.AnakKiri);
System.out.print(z.Data + " ");
inOrder(z.Anakkanan);
}
}
}
public class Tree_Ilham {
public static void main (String[] args){
Scanner input = new Scanner (System.in);
Tree TheTree = new Tree();
int arr[]={10,85,15,70,20,60,30,50,65,80,90,40,5,55};
System.out.println("Inserting : ");
for(int i=0;i<14;i++){
System.out.print(arr[i]+ " ");
TheTree.insert(arr[i]);
}
System.out.println();
System.out.println();
System.out.print("Tree (InOrder) : ");
TheTree.inOrder(TheTree.root);
System.out.println();
int pil;
do{
System.out.println("");
System.out.println("Menu Operasi :");
System.out.println("1. Maximum Data Tree");
System.out.println("2. Minimum Data Tree");
System.out.println("3. Searching Data Tree");
System.out.println("4. Swap Data Tree");
System.out.println("0. Keluar");
System.out.print("Masukkan Pilihan :");
pil=input.nextInt();
switch(pil){
case 1 :System.out.println("Maksimum: "+TheTree.Find_Max());break;
case 2 :System.out.println("Minimum : "+TheTree.Find_Min());break;
case 3 :{
System.out.print("Inputkan Data yang akan Dicari :");
int x=input.nextInt();
System.out.println("Searching "+x+" :"+TheTree.find(x));
break;
}
case 4 :{
System.out.print("Inputkan Data yang akan Ditukar :");
int a=input.nextInt();
System.out.print("Inputkan Data Penukaran :");
int b=input.nextInt();
System.out.println("Penukaran nilai "+a+" dengan "+b+":");
TheTree.swap(a,b);
TheTree.inOrder(TheTree.root);
System.out.println("");
break;
}
}
}while (pil!=0);
}
}
0 komentar:
Posting Komentar