import java.util.*;
class Node{
String nama;
int level;
Node parent,sibling,anak;
linkedList child; // linkedlist yg selevel
public Node(String n){
nama = n;
parent = sibling = anak = null;
child = null;
level = 0;
}
void view(Node berhenti){ // u/ ngeprint anaknya root
// anak root
System.out.println(nama);
// anaknya anak root dst
if(anak!=null){
for(int i=0;i<anak.level;i++)
System.out.print(“ “);
anak.view(anak); // kalo masih ada yang levelnya dibwh anak root, print
}
// sodara anaknya anak root dst
if(sibling!=berhenti && sibling.parent==this.parent){
for(int i=0;i<sibling.level;i++)
System.out.print(“ “);
sibling.view(berhenti);
}
}
}
class linkedList {
Node head,tail;
public linkedList (){
head = tail = null;
}
Node find(String cari){
Node temp=head;
do{
if(temp.nama.contains(cari)){
return temp;
}
temp = temp.sibling;
}while(temp!=head && temp!=null);
return null;
}
void add(Node input){
// u/ nambah linkedlist child
if(head.child==null){
head.child = new linkedList();
head.child.head = input;
head.child.tail = input;
input.sibling = input;
}
else{
Node temp = head.child.head;
while(temp.parent!=input.parent && temp.sibling!=head.child.head)
temp = temp.sibling;
input.sibling = temp.sibling;
temp.sibling = input;
}
// u/ ngehubungin parent dan anaknya
if(input.parent.anak==null)
input.parent.anak = input;
input.level = input.parent.level + 1;
System.out.println(“Berhasil memasukkan “+input.nama+” sebagai anak dari “+input.parent.nama);
}
}
class Tree{
Node root;
public Tree(){
root = null;
}
void insert(String a,String b){
if(b.equals(“”)){ // sbg root
if(root==null){
root = new Node(a);
System.out.println(“Berhasil memasukkan “+a+” sebagai root”);
}
else
System.out.println(“Input Error!!”);
}
else if(root.nama.contains(b)){ // nambah anak root
if(!menikah(root))
return;
Node baru = new Node(a);
baru.parent = root;
baru.level = 1;
if(root.child==null){
root.child = new linkedList(); // nambahnya dg buat linkedlist baru
root.child.head = baru;
root.child.tail = baru;
root.anak = baru;
baru.sibling = baru;
}
else{
root.child.tail.sibling = baru;
baru.sibling = root.child.head;
root.child.tail = baru;
}
System.out.println(“Berhasil memasukkan “+a+” sebagai anak dari “+b);
}
else{ // nambah cucu root dan seterusnya
linkedList temp = findList(b);
Node input = new Node(a);
if(temp != null){
if(!menikah(temp.find(b)))
return;
input.parent = temp.find(b);
temp.add(input); // nambah dari linkedlist
}
else
System.out.println(“Tidak ada anggota keluarga bernama “+b);
}
}
void view(){
if(root==null){
System.out.println(“Belum ada data”);
}
else{
System.out.println(root.nama); // ngeprint root
if(root.anak!=null){
for(int i=0;i<root.anak.level;i++)
System.out.print(“ “);
root.anak.view(root.anak);
}
}
}
linkedList findList (String cari){
linkedList temp = root.child;
while(temp!=null){
if(temp.find(cari)!=null)
return temp;
temp = temp.head.child;
}
return null;
}
void findAll(String nama){
if(root.nama.equals(nama)){
System.out.println(nama+” adalah root”);
}
else{
linkedList temp = findList(nama);
if(temp!=null){
Node p = temp.find(nama);
if(p.sibling==p)
System.out.println(“Tidak ada anggota keluarga yang selevel dengan “+nama);
else{
p = p.sibling;
System.out.print(“Anggota keluarga yang selevel dengan “+nama+” adalah “+p.nama);
while(p.sibling!=temp.find(nama)){
System.out.print(“, “+p.sibling.nama);
p = p.sibling;
}
}
}
else
System.out.println(“Tidak ada anggota keluarga bernama “+nama);
System.out.println();
}
}
void relation(String a,String b){
linkedList temp = findList(a);
linkedList temp2 = findList(b);
if(temp==null || temp2==null){
if(!(root.nama.contains(a) || root.nama.contains(b))){
System.out.println(“Input Error !!”);
return;
}
}
Node satu=null,dua=null;
//kalo salah satunya root
if(temp==null){
satu = root;
dua = temp2.find(b);
}
else if(temp2==null){
dua = root;
satu = temp.find(a);
}
//kalo dua-duanya bukan root
else{
satu = temp.find(a);
dua = temp2.find(b);
}
if(satu!=null && dua!=null){
// dikondisikan satu paling muda(levelnya besar)
if(dua.level>satu.level){
Node s = satu;
satu = dua;
dua = s;
}
if(satu.level == dua.level){
if(satu.parent==dua.parent)
System.out.println(a+” adalah saudara kandung “+b);
else System.out.println(a+” adalah saudara sepupu “+b);
}
else{
int selisih = satu.level – dua.level;
if(selisih==1){
if(satu.parent==dua)
System.out.println(dua.nama+” adalah orangtua dari “+satu.nama);
else System.out.println(satu.nama+” adalah keponakan “+dua.nama);
}
else if(selisih==2){
System.out.println(satu.nama+” adalah cucu “+dua.nama);
}
else if(selisih==3){
System.out.println(satu.nama+” adalah cicit “+dua.nama);
}
else{
System.out.println(satu.nama+” adalah canggah “+dua.nama);
}
}
}
}
void marry(String a,String b){
linkedList temp = findList(a);
Node m = null;
if(temp==null){
if(root.nama.equals(a)){
m = root;
}
else{
System.out.println(“Input error !!”);
return;
}
}
else
m = temp.find(a);
m.nama = m.nama + ” ” + b;
System.out.println(“cie..cie.. , akhirnya “+a+” nikah juga sama si “+b);
}
boolean menikah(Node cek){
StringTokenizer st = new StringTokenizer(cek.nama);
if(st.countTokens()!=2){
System.out.println(cek.nama+” belum menikah !!”);
return false;
}
return true;
}
}
public class SilsilahKeluargaKlp76{
public static void main(String[] args){
Scanner input = new Scanner (System.in);
String perintah;
Tree silsilah = new Tree();
StringTokenizer st;
while(true){
System.out.print(“command >> “);
perintah = input.nextLine();
while(perintah.length()<10)
perintah = perintah + ” “;
if(perintah.substring(0,6).equalsIgnoreCase(“insert”)){
st = new StringTokenizer(perintah.substring(7));
if(st.countTokens()==1){
silsilah.insert(st.nextToken(),”");
}
else{
silsilah.insert(st.nextToken(),st.nextToken());
}
}
else if(perintah.substring(0,4).equalsIgnoreCase(“view”)){
System.out.println();
silsilah.view();
System.out.println();
}
else if(perintah.substring(0,8).equalsIgnoreCase(“relation”)){
st = new StringTokenizer(perintah.substring(9));
silsilah.relation(st.nextToken(),st.nextToken());
}
else if(perintah.substring(0,8).equalsIgnoreCase(“find_all”)){
st = new StringTokenizer(perintah.substring(9));
silsilah.findAll(st.nextToken());
}
else if(perintah.substring(0,5).equalsIgnoreCase(“marry”)){
st = new StringTokenizer(perintah.substring(6));
silsilah.marry(st.nextToken(),st.nextToken());
}
else
System.out.println(“Nginput yang bener donkZzz!!!”);
}
}
}
