Kulas_Code20

Binary Search Tree

Dec 6th, 2021
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.87 KB | None | 0 0
  1. /**
  2.  * Binary Search Tree
  3.  */
  4. public class BST {
  5.     //attributes
  6.     private Object item; //data container
  7.     private BST left,right,parent;
  8.    
  9.     //constructor
  10.     public BST(Object item) { this.item = item; }
  11.     public BST()            {}
  12.    
  13.     //setters
  14.     public void setItem(Object item)    { this.item = item; }
  15.     public void setLeft(BST left)       { this.left = left; }
  16.     public void setRight(BST right)     { this.right = right; }
  17.     public void setParent(BST parent)   { this.parent = parent; }
  18.    
  19.     //setters
  20.     public Object getItem()     { return item; }
  21.     public BST getLeft()        { return left; }
  22.     public BST getRight()       { return right; }
  23.     public BST getParent()      { return parent; }
  24.    
  25.     public BST addNode(Object item, BST root) {
  26.         //create a new node(tree)
  27.         BST node = new BST(item);
  28.             if(root == null) root = node;
  29.             else {
  30.                 Comparable c =  (Comparable)root.getItem();
  31.                 if(c.compareTo(item) > 0) {
  32.                     root.left = addNode(item, root.getLeft()); //recursive call
  33.                 }
  34.                 if(c.compareTo(item) <= 0) {
  35.                     root.right = addNode(item, root.getRight());
  36.                 }
  37.             }
  38.         return root; //return the updated root
  39.     }
  40.    
  41.     public void preOder(BST root) {
  42.         if(root != null) {
  43.             System.out.print(root.getItem()); //Logical marker
  44.             preOder(root.getLeft());
  45.             preOder(root.getRight());
  46.         }
  47.     }
  48.  
  49.     public void inOder(BST root) {
  50.         if(root != null) {
  51.             inOder(root.getLeft());
  52.             System.out.print(root.getItem()); //Logical marker
  53.             inOder(root.getRight());
  54.         }
  55.     }
  56.    
  57.     public void postOder(BST root) {
  58.         if(root != null) {
  59.             postOder(root.getLeft());
  60.             postOder(root.getRight());
  61.             System.out.print(root.getItem()); //Logical marker
  62.         }
  63.     }
  64.    
  65.     public void levelOder(BST root) {
  66.         java.util.Queue<BST> q = new java.util.LinkedList<BST>();
  67.             q.add(root);
  68.             while(!q.isEmpty()) {
  69.                 BST temp = q.poll();
  70.                 System.out.print(temp.getItem());
  71.                 if(temp.getLeft() != null) {
  72.                     q.add(temp.getLeft());
  73.                 }  
  74.                 if(temp.getRight() != null) {
  75.                     q.add(temp.getRight());
  76.                 }
  77.             }
  78.     }
  79.    
  80.     static public void main(String... args) {
  81.         BST bst = null;
  82.        
  83.         bst = new BST().addNode(new String("6"), bst);
  84.         bst = new BST().addNode(new String("4"), bst);
  85.         bst = new BST().addNode(new String("9"), bst);
  86.         bst = new BST().addNode(new String("7"), bst);
  87.         bst = new BST().addNode(new String("2"), bst);
  88.         bst = new BST().addNode(new String("8"), bst);
  89.         bst = new BST().addNode(new String("5"), bst);
  90.         bst = new BST().addNode(new String("0"), bst);
  91.         bst = new BST().addNode(new String("3"), bst);
  92.         bst = new BST().addNode(new String("1"), bst);
  93.         bst = new BST().addNode(new String("6"), bst);
  94.        
  95.         System.out.print("Pre-Order: ");
  96.         new BST().preOder(bst);
  97.         System.out.print("\nIn-Order: ");
  98.         new BST().inOder(bst);
  99.         System.out.print("\nPost-Order: ");
  100.         new BST().postOder(bst);
  101.         System.out.print("\nLevel-Order: ");
  102.         new BST().levelOder(bst);
  103.        
  104.     }
  105.  
  106. }//End of the class
Advertisement
Add Comment
Please, Sign In to add comment