Minggu, 18 April 2010

Java pohon biner

class Simpul{
char info;
Simpul next;
Jalur arc;

Simpul(){
}
}

class Jalur{
int info;
Jalur next;
Simpul node;

Jalur(){
}
}

class Graph{
Simpul first;

Graph(){
}

/*--------------------------*/

void createEmpty(){

first = null;

}

/*--------------------------*/

void addSimpul(char c){


Simpul node;
node = new Simpul();

node.info = c;
node.next = null;
node.arc = null;

if(first == null){
/*jika graph kosong*/
first = node;
}
else{
/*menambahkan simpul baru pada akhir graph*/
Simpul last = first;

while(last.next != null){
last = last.next;
}

last.next = node;

}

}

/*--------------------------*/

void addJalur(Simpul tujuan, int beban, Simpul awal){


Jalur arc;
arc = new Jalur();

arc.info = beban;
arc.next = null;
arc.node = tujuan;

if(awal.arc == null){
/*jika list jalur kosong*/
awal.arc = arc;
}
else{
/*menambahkan jalur baru pada akhir list jalur*/
Jalur last = awal.arc;

while(last.next != null){
last = last.next;
}

last.next = arc;

}

}

/*--------------------------*/

void delSimpul(char c){


Simpul elmt = first;

if(elmt != null){

Simpul prec = null;

/*mencari simpul yang akan dihapus*/
boolean ketemu = false;
while((elmt != null) && (ketemu == false)){
if(elmt.info == c){
ketemu = true;
}
else{
prec = elmt;
elmt = elmt.next;
}
}

if(ketemu == true){
if(prec == null){
/*hapus simpul pertama*/
first = elmt.next;
}
else{
if(elmt.next == null){
/*hapus simpul terakhir*/
prec.next = null;
}
else{
/*hapus simpul di tengah*/
prec.next = elmt.next;
elmt.next = null;
}
}

}
else{
System.out.println("tidak ada simpul dengan info karakter masukan");
}
}
else{
System.out.println("tidak ada simpul dengan info karakter masukan");
}

}

/*--------------------------*/

Simpul findSimpul(char c){


Simpul hasil = null;
Simpul node = first;

boolean ketemu = false;
while((node != null) && (ketemu == false)){
if(node.info == c){
hasil = node;
ketemu = true;
}
else{
node = node.next;
}
}

return hasil;

}

/*--------------------------*/

void delJalur(char ctujuan, Simpul awal){

Jalur arc = awal.arc;

if(arc != null){

Jalur prec = null;

/*mencari jalur yang akan dihapus*/
boolean ketemu = false;
while((arc != null) && (ketemu == false)){
if(arc.node.info == ctujuan){

ketemu = true;
}
else{
prec = arc;
arc = arc.next;
}
}

if(ketemu == true){
if(prec == null){
/*hapus simpul pertama*/
awal.arc = arc.next;
}
else{
if(arc.next == null){
/*hapus jalur terakhir*/
prec.next = null;
}
else{
/*hapus jalur di tengah*/
prec.next = arc.next;
arc.next = null;
}
}

}
else{
System.out.println("tidak ada jalur dengan simpul tujuan");
}
}
else{
System.out.println("tidak ada jalur dengan simpul tujuan");
}

}

/*--------------------------*/

void printGraph(){

Simpul node = first;

if(node != null){

while(node != null){

System.out.println("simpul : " + node.info);
Jalur arc = node.arc;

while(arc != null){

System.out.println(" - ada jalur ke simpul : " + arc.node.info + " dengan beban : " + arc.info);

arc = arc.next;

}

node = node.next;

}
}
else{
System.out.println("graph kosong");
}

}

/*--------------------------*/
}

/*--------------------------*/

class CobaGraph{

public static void main(String[] args) {

Graph G = new Graph();

G.createEmpty();
G.addSimpul('A');
G.addSimpul('B');
G.addSimpul('C');
G.addSimpul('D');
G.addSimpul('E');
G.addSimpul('F');

Simpul begin = G.findSimpul('A');
Simpul end = G.findSimpul('B');
if((begin != null) && (end != null)){
G.addJalur(end, 3, begin);
}

begin = G.findSimpul('B');
end = G.findSimpul('D');
if((begin != null) && (end != null)){
G.addJalur(end, 3, begin);
}

end = G.findSimpul('E');
if((begin != null) && (end != null)){
G.addJalur(end, 7, begin);
}

begin = G.findSimpul('C');
end = G.findSimpul('A');
if((begin != null) && (end != null)){
G.addJalur(end, 3, begin);
}

begin = G.findSimpul('D');
if((begin != null) && (end != null)){
G.addJalur(end, 8, begin);
}

end = G.findSimpul('C');
if((begin != null) && (end != null)){
G.addJalur(end, 3, begin);
}

begin = G.findSimpul('E');
end = G.findSimpul('D');
if((begin != null) && (end != null)){
G.addJalur(end, 4, begin);
}

end = G.findSimpul('B');
if((begin != null) && (end != null)){
G.addJalur(end, 4, begin);
}

begin = G.findSimpul('F');
end = G.findSimpul('D');
if((begin != null) && (end != null)){
G.addJalur(end, 2, begin);
}
System.out.println("================");
G.printGraph();
System.out.println("\n================");
begin = G.findSimpul('A');
if(begin != null){
G.delJalur('B', begin);
}

System.out.println("================");
System.out.println("setelah dihapus");
G.printGraph();
System.out.println("\n================");
}
}