dsa

Data Structures & Algorithms - Spring 2018
Log | Files | Refs | README

MyBinarySearchTreePlus.java (3437B)

      1 package lab11;
      2 
      3 public class MyBinarySearchTreePlus <T extends KeyedItem<KT>,KT extends Comparable<? super KT>> extends MyBinarySearchTree<T,KT> implements BSTPInterface<T,KT> {
      4 
      5     public int getHeight() {
      6         int height = 0;
      7         if (root  != null) {
      8             height += getHeight(root);
      9         }
     10         return height;
     11     }
     12     private int getHeight(TreeNode<T> treeNode){
     13         if (treeNode == null) {
     14             return 0;
     15         }
     16         int ls = getHeight(treeNode.getLeftChild());
     17         int rs = getHeight(treeNode.getRightChild());
     18         if (ls > rs) {
     19             return 1 + ls;
     20         }
     21         else {
     22             return 1 + rs;
     23         }
     24     }
     25 
     26     public int getSize() {
     27         int size = 0;
     28         if (root != null) {
     29             size += getSize(root);
     30         }
     31         return size;
     32     }
     33 
     34     private int getSize(TreeNode<T> treeNode) {
     35         if (treeNode == null) {
     36             return 0;
     37         }
     38         int ls = getSize(treeNode.getLeftChild());
     39         int rs = getSize(treeNode.getRightChild());
     40         return ls + rs + 1;
     41 
     42     }
     43 
     44     public String toStringInorder() {
     45         String result ="";
     46         if (root != null) {
     47             result += toStringInorder(root);
     48         }
     49         return result;
     50     }
     51     private String toStringInorder(TreeNode<T> treeNode) {
     52         if (treeNode == null) {
     53             return "";
     54         }
     55         String result = "";
     56         result += toStringInorder(treeNode.getLeftChild());
     57         result += treeNode.getItem().getKey() + " ";
     58         result += toStringInorder(treeNode.getRightChild());
     59         return result;
     60     }
     61 
     62     public String toStringPreorder() {
     63         String result = "";
     64         if (root != null) {
     65             result += toStringPreorder(root);
     66         }
     67         return result;
     68     }
     69     private String toStringPreorder(TreeNode<T> treeNode) {
     70         if (treeNode == null) {
     71             return "";
     72         }
     73         String result = "";
     74         result += treeNode.getItem().getKey() + " ";
     75         result += toStringInorder(treeNode.getLeftChild());
     76         result += toStringInorder(treeNode.getRightChild());
     77         return result;
     78     }
     79 
     80     public String toStringPostorder() {
     81         String result = "";
     82         if (root != null) {
     83             result += toStringPostorder(root);
     84         }
     85         return result;
     86     }
     87     private String toStringPostorder(TreeNode<T> treeNode) {
     88         if (treeNode == null) {
     89             return "";
     90         }
     91         String result = "";
     92         result += toStringInorder(treeNode.getLeftChild());
     93         result += toStringInorder(treeNode.getRightChild());
     94         result += treeNode.getItem().getKey() + " ";
     95         return result;
     96     }
     97 
     98     public MyBinarySearchTreePlus<T , KT> getCopyOfTree()
     99     {
    100         MyBinarySearchTreePlus<T , KT> tree = new MyBinarySearchTreePlus<>();
    101         return getCopyOfTree(root, tree);
    102 
    103     }
    104     private MyBinarySearchTreePlus<T,KT> getCopyOfTree(TreeNode<T> treeNode, MyBinarySearchTreePlus<T, KT> copyTree) {
    105         if (treeNode != null) {
    106             copyTree.insert(treeNode.getItem());
    107             getCopyOfTree(treeNode.getLeftChild(), copyTree);
    108             getCopyOfTree(treeNode.getRightChild(), copyTree);
    109         }
    110         return copyTree;
    111     }
    112 // returns a new tree containing a copy of the original tree
    113 // with the same structure. Note: the new tree should not have
    114 // any shared nodes with the original.(recursive implementation)
    115 }