jcreator 2
class node {
int data;
int tinggi;
node pkiri;
node pkanan;
node pinduk;
public node (int dt, int tg, node pki, node pka, node pi) {
this.data= dt;
this.tinggi=tg;
this.pkiri=pki;
this.pkanan=pka;
this.pinduk=pi;
}
}
public class AVLT {
private node root;
public AVLT() {root=null;}
public boolean cariDt(int dt){
node temp=root;
while(temp !=null) {
if(dt==temp.data) return true;
else if(dt< temp.data) temp=temp.pkiri;
else temp=temp.pkanan;
}
return false;
}
public boolean sisipdt(int dt) {
if (root==null) {
root=new node(dt,1,null,null,null);
return true;
}
else {
node temp=root;
node prev=null;
while(temp !=null) {
if(dt== temp.data)return false;
else if (dt< temp.data){
prev=temp;
temp=temp.pkiri;
}
else{
prev=temp;
temp=temp.pkanan;
}
}
temp=new node(dt,1,null,null,prev);
if(dt< prev.data) prev.pkiri=temp;
prev.pkanan=temp;
while(temp !=null) {
if(Math.abs(tinggi(temp.pkiri)-tinggi(temp.pkanan))<=1){
temp.tinggi=Math.max(tinggi(temp.pkiri),tinggi(temp.pkanan))+1;
}
else if(tinggi(temp.pkiri)-tinggi(temp.pkanan)>=2&& tinggi(temp.pkiri.pkiri)>=tinggi(temp.pkiri.pkanan))
{
node parent= temp.pinduk;
node pkiri= temp.pkiri;
temp.pkiri=pkiri.pkanan;
if(temp.pkiri !=null) temp.pkiri.pinduk=temp;
pkiri.pkanan=temp;
temp.pinduk=pkiri;
pkiri.pinduk=parent;
if(parent==null) root=pkiri;
else if(parent.pkiri==temp)parent.pkiri=pkiri;
else parent.pkanan=pkiri;
temp.tinggi=Math.max(tinggi(temp.pkiri),tinggi(temp.pkanan))+1;
temp = pkiri;
temp.tinggi=Math.max(tinggi(temp.pkiri),tinggi(temp.pkanan))+1;
}
//case 2 algoritma AVl
else if(tinggi(temp.pkanan)-tinggi(temp.pkiri)>=2 && tinggi(temp.pkanan.pkanan)>= tinggi(temp.pkanan.pkiri))
{
node parent= temp.pinduk;
node pkanan=temp.pkanan;
temp.pkanan=pkanan.pkiri;
if (temp.pkanan !=null) temp.pkanan.pinduk=temp;
pkanan.pkiri=temp;
temp.pinduk=pkanan;
pkanan.pinduk=parent;
if (parent == null) root=pkanan;
else if(parent.pkanan==temp)
parent.pkanan=pkanan;
else parent.pkiri=pkanan;
temp.tinggi=Math.max(tinggi(temp.pkiri),tinggi(temp.pkanan))+1;
temp=pkanan;
temp.tinggi=Math.max(tinggi(temp.pkiri),tinggi(temp.pkanan)) +1;
}
else if(tinggi(temp.pkiri)-tinggi(temp.pkanan)>=2&& tinggi(temp.pkiri.pkanan)>= tinggi(temp.pkiri.pkiri))
{
node parent=temp.pinduk;
node pkiripkanan=temp.pkiri.pkanan;
temp.pkiri.pkanan=pkiripkanan.pkiri;
if(temp.pkiri.pkanan !=null)
temp.pkiri.pkanan.pinduk=temp.pkiri;
pkiripkanan.pkiri=temp.pkiri;
temp.pkiri.pinduk=pkiripkanan;
temp.pkiri=pkiripkanan.pkanan;
if(temp.pkiri !=null) temp.pkiri.pinduk=temp;
pkiripkanan.pkanan=temp;
temp.pinduk=pkiripkanan;
pkiripkanan.pinduk=parent;
if(parent==null) root=pkiripkanan;
else if (parent.pkiri==temp)
parent.pkiri=pkiripkanan;
else parent.pkanan=pkiripkanan;
temp.tinggi=Math.max(tinggi(temp.pkiri),tinggi(temp.pkanan))+1;
temp=pkiripkanan;
temp.tinggi=Math.max(tinggi(temp.pkiri),tinggi(temp.pkanan))+1;
}
else if (tinggi(temp.pkanan)-tinggi(temp.pkiri)>=2&& tinggi(temp.pkanan.pkiri)>= tinggi(temp.pkanan.pkanan))
{
node parent=temp.pinduk;
node pkananpkiri=temp.pkanan.pkiri;
temp.pkanan.pkiri=pkananpkiri.pkanan;
if(temp.pkanan.pkiri!=null)
temp.pkanan.pkiri.pinduk=temp.pkanan;
pkananpkiri.pkanan=temp.pkanan;
temp.pkanan.pinduk=pkananpkiri;
temp.pkanan=pkananpkiri.pkiri;
if(temp.pkanan !=null)temp.pkanan.pinduk=temp;
pkananpkiri.pkiri=temp;
temp.pinduk=pkananpkiri;
pkananpkiri.pinduk=parent;
if(parent==null) root=pkananpkiri;
else if(parent.pkanan==temp)
parent.pkanan=pkananpkiri;
else parent.pkiri=pkananpkiri;
temp.tinggi=Math.max(tinggi(temp.pkiri),tinggi(temp.pkanan)) +1;
temp=pkananpkiri;
temp.tinggi=Math.max(tinggi(temp.pkiri),tinggi(temp.pkanan)) +1;
}
temp=temp.pinduk;
}
return true;
}
}
public int tinggi() {return root.tinggi;}
private int tinggi(node Node){
if(Node==null) return 0;
else return Node.tinggi;
}
public int jumlahnode(){
return jumlahnode(root);
}
public void inordertraversal(){
inorder(root);
}
private void inorder(node r) {
if (r == null) return ;
inorder(r.pkiri);
System.out.printf("-%d",r.data);
inorder(r.pkanan);
}
private int jumlahnode(node Node){
if(Node==null)return 0;
else
return 1+jumlahnode(Node.pkiri)+jumlahnode(Node.pkanan);
}
public static void main (String[] args) {
AVLT t=new AVLT();
t.sisipdt(3);t.inordertraversal();System.out.println();
t.sisipdt(4);t.inordertraversal();System.out.println();
t.sisipdt(6);t.inordertraversal();System.out.println();
t.sisipdt(5);t.inordertraversal();System.out.println();
t.sisipdt(15);t.inordertraversal();System.out.println();
t.sisipdt(10);t.inordertraversal();System.out.println();
t.sisipdt(20);t.inordertraversal();System.out.println();
t.sisipdt(17);t.inordertraversal();System.out.println();
t.sisipdt(25);t.inordertraversal();System.out.println();
}
}
=======================================================================
TREE
import java.util.Random;
class node {
int data;
node nodekiri;
node nodekanan;
public node(int dt) {
data = dt;
nodekiri= nodekanan=null;
}
public void sisipDt(int dtsisip) {
if (dtsisip<data) {
if (nodekiri==null)
nodekiri=new node(dtsisip);
else nodekiri.sisipDt(dtsisip);
}
else if(dtsisip>data){
if(nodekanan==null)
nodekanan=new node(dtsisip);
else nodekanan.sisipDt(dtsisip);
}
}
}
public class tree {
private node root;
public tree() {
root=null;
}
public void sisipDtNode(int dtsisip) {
if (root==null)
root=new node(dtsisip);
else
root.sisipDt(dtsisip);
}
public void preorderTraversal(){
preorder(root);
}
private void preorder(node Node) {
if(Node ==null)return ;
System.out.printf("%d ", Node.data);
preorder(Node.nodekiri);
preorder(Node.nodekanan);
}
public void inorderTraversal() {
inorder(root);
}
private void inorder(node Node){
if (Node==null) return ;
inorder(Node.nodekiri);
System.out.printf("%d ",Node.data);
inorder(Node.nodekanan);
}
public void postorderTraversal() {
postorder(root);
}
private void postorder(node Node){
if(Node==null)return ;
postorder(Node.nodekiri);
postorder(Node.nodekanan);
System.out.printf("%d ",Node.data);
}
public static void main (String[] args) {
tree tree=new tree();
int nilai;
Random Randomnumber=new Random();
System.out.println("sisip nilai data berikut: ");
//sisipDt 10 bilanga acak dari 0-99 ke dalam tree
for (int i=1; i<=10; i++) {
nilai = Randomnumber.nextInt(100);
System.out.print(nilai+ " ");
tree.sisipDtNode(nilai);
}
System.out.println("\n\npreorder traversal");
tree.preorderTraversal();
System.out.println("n\ninorder traversal");
tree.inorderTraversal();
System.out.println("n\npostorder traversal ");
tree.postorderTraversal();
System.out.println();
}
}
=========================================================================
GRAPH
public class graph {
private class node{
private int data;
private node next;
public node (int dt, node n) {
data = dt;
next= n;
}
public int getDt() {return data;}
public node getnext() {return next;}
}
private node []Node;
private int jnode;
public graph (int n) {
jnode=n;
Node=new node[jnode];
for(int i=0; i<jnode; i++)Node[i]=null;
}
public void addAdj(int head, int adj){
node n=new node(adj,Node[head]);
Node[head]=n;
}
public void cetak(){
for(int i=0; i<jnode; i++){
System.out.println("["+i+"]");
node n=Node[i];
while (n!=null){
System.out.print("->"+n.getDt());
n=n.getnext();
}
System.out.println();
}
}
public static void main (String[] args) {
graph g=new graph(5);
g.addAdj(0,3);
g.addAdj(0,1);
g.addAdj(1,4);
g.addAdj(1,2);
g.addAdj(2,4);
g.addAdj(2,1);
g.addAdj(4,3);
g.cetak();
}
}
0 komentar:
Posting Komentar