Advertisement
Guest User

Untitled

a guest
Sep 15th, 2019
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.41 KB | None | 0 0
  1. public class DLLToBST {
  2.     public static Node head = null;
  3.     public static Node tail = null;
  4.     public static int size = 0;
  5.     public Node root;
  6.  
  7.     public void add(int data) {
  8.         Node n = new Node(data);
  9.         if (head == null) {
  10.             head = n;
  11.             tail = n;
  12.         } else {
  13.             head.prev = n;
  14.             n.next = head;
  15.             head = n;
  16.         }
  17.         size++;
  18.     }
  19.  
  20.     public Node dLLtoBST(int size) {
  21.         if (size <= 0) {
  22.             return null;
  23.         }
  24.         Node left = dLLtoBST(size / 2);
  25.         Node root = head;
  26.         root.prev = left;
  27.         head = head.next;
  28.         root.next = dLLtoBST(size-(size / 2)-1);
  29.         return root;
  30.     }
  31.  
  32.     public void inOrder(Node root) {
  33.         if (root != null) {
  34.             inOrder(root.prev);
  35.             System.out.print(" " + root.data);
  36.             inOrder(root.next);
  37.         }
  38.     }
  39.  
  40.     public void printDLL(Node head) {
  41.         Node curr = head;
  42.         while (curr != null) {
  43.             System.out.print(" " + curr.data);
  44.             curr = curr.next;
  45.         }
  46.         System.out.println();
  47.     }
  48.  
  49.     public static void main(String args[]) {
  50.         DLLToBST r = new DLLToBST();
  51.         r.add(9);
  52.         r.add(8);
  53.         r.add(7);
  54.         r.add(6);
  55.         r.add(5);
  56.         r.add(4);
  57.         r.add(3);
  58.         r.add(2);
  59.         r.add(1);
  60.         Node h = head;
  61.         System.out.println("DLL is : ");
  62.         r.printDLL(h);
  63.         Node x = r.dLLtoBST(size);
  64.         System.out.println("Inorder traversal of contructed BST");
  65.         r.inOrder(x);
  66.     }
  67. }
  68.  
  69. class Node {
  70.     int data;
  71.     Node next;
  72.     Node prev;
  73.  
  74.     public Node(int data) {
  75.         this.data = data;
  76.         this.next = null;
  77.         this.prev = null;
  78.     }
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement