Advertisement
iNoobAvicena

Height of Tree II

Nov 27th, 2020
104
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.LinkedList;
  2. import java.util.List;
  3. import java.util.Scanner;
  4.  
  5. class Node<T> {
  6.     T data;
  7.     LinkedList<Node> childs;
  8.    
  9.     public Node(T data) {
  10.         this.data = data;
  11.         this.childs = new LinkedList<Node>();
  12.     }
  13.    
  14.     public T getData(){
  15.         return this.data;
  16.     }
  17. }
  18.  
  19. public class Tree<T> {
  20.     Node root;
  21.    
  22.     public Tree(Node node) {
  23.         root = node;
  24.     }
  25.    
  26.     public Tree(T data) {
  27.         root = new Node(data);
  28.     }
  29.  
  30.     public boolean isEmpty() {
  31.         return root == null;
  32.     }
  33.    
  34.     public void add(T dataParent, T data) {
  35.         Node node = getNode(root, dataParent);
  36.         if (node != null)
  37.             node.childs.add(new Node(data));
  38.         else
  39.             System.out.println("Node Parent tidak ditemukan");
  40.     }
  41.    
  42.     public Node getNode(Node node, T data) {
  43.         if (node.data == data) return node;
  44.        
  45.         for(Object currNode : node.childs) {
  46.             Node returnNode = getNode((Node) currNode, data);
  47.             if (returnNode != null) return returnNode;
  48.         }
  49.         return null;
  50.     }
  51.    
  52.     public int height(Node current){
  53.         //LENGKAPI
  54.         int tinggi = 0;
  55.         int hitung;
  56.         LinkedList <Node> isi = new LinkedList<Node>();
  57.         isi.push(root);
  58.         while (true) {
  59.             hitung = isi.size();
  60.             if (hitung == 0) {
  61.                 return tinggi - 1;
  62.             } else {
  63.                 tinggi++;
  64.             }
  65.             while (hitung > 0) {
  66.                 Node x = isi.peek();
  67.                 isi.remove();
  68.                 for (Object currNode : x.childs) {
  69.                     if ((Node) currNode == null) {
  70.                         break;
  71.                     } else {
  72.                         isi.add((Node) currNode);
  73.                     }
  74.                 }
  75.                 hitung--;
  76.             }
  77.         }
  78.     }
  79.     public void access() {
  80.         System.out.print(root.data);
  81.         access(root, "  ");
  82.     }
  83.    
  84.     private void access(Node node, String space) {        
  85.         System.out.println("");
  86.         for(Object currNode : node.childs) {
  87.             System.out.print(space + "->" + ((Node) currNode).getData());            
  88.             access((Node) currNode, space + "  ");
  89.         }
  90.        
  91.         return;
  92.     }
  93.    
  94.     public static void main(String[] args) {
  95.         Scanner in = new Scanner(System.in);
  96.         int n = in.nextInt();
  97.         int rt = in.nextInt();
  98.         Tree pohon = new Tree(new Node(rt));
  99.         for (int i = 0; i < n-1; i++) {
  100.             int p = in.nextInt();
  101.             int nd = in.nextInt();
  102.             pohon.add(p, nd);
  103.         }
  104.         pohon.access();
  105.         System.out.println("Ketinggian = " + pohon.height(pohon.root));
  106.     }
  107. }
Advertisement
RAW Paste Data Copied
Advertisement