The text below is selected, press Ctrl+C to copy to your clipboard. (⌘+C on Mac) No line numbers will be copied.
Guest
BinarySearchTree.java
By Guest on 12th March 2019 11:46:26 PM | Syntax: JAVA | Views: 1



New paste | Download | Show/Hide line no. | Copy text to clipboard
  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.ListIterator;
  4. import java.util.Objects;
  5. import java.util.stream.Collectors;
  6.  
  7. public class BinarySearchTree<T extends Comparable<? super T> > {
  8.  
  9.     private BinaryNode<T> root;
  10.  
  11.     public BinarySearchTree() { }
  12.  
  13.     // TODO: initialisation
  14.     public BinarySearchTree(T item) {
  15.         this.root = new BinaryNode<>(item);
  16.     }
  17.  
  18.     // TODO: on insere un nouvel item a partir de la racine
  19.     // O(log(n))
  20.     public void insert(T item) {
  21.         if (this.root != null)
  22.             this.root.insert(item);
  23.         else
  24.             this.root = new BinaryNode<>(item);
  25.     }
  26.  
  27.     // TODO: est-ce qu'un item fais partie de l'arbre
  28.     // O(log(n))
  29.     public boolean contains(T item) {
  30.         if (this.root != null)
  31.             return this.root.contains(item);
  32.         else
  33.             return false;
  34.     }
  35.  
  36.     // TODO: trouver la hauteur de l'arbre
  37.     // O(n)
  38.     public int getHeight() {
  39.         if (this.root != null)
  40.             return this.root.getHeight();
  41.         else
  42.             return 0;
  43.     }
  44.  
  45.     // TODO: placer dans une liste les items de l'arbre en ordre
  46.     // O(n)
  47.     public List<BinaryNode<T>> getItemsInOrder() {
  48.         List<BinaryNode<T>> list = new ArrayList<BinaryNode<T>>();
  49.  
  50.         if (this.root == null)
  51.             return null;
  52.         else {
  53.             this.root.fillListInOrder(list);
  54.             return list;
  55.         }
  56.     }
  57.  
  58.     // TODO: retourner la liste d'item en String selon le bon format
  59.     // O(n)
  60.     public String toStringInOrder() {
  61.         List<BinaryNode<T>> liste = this.getItemsInOrder();
  62.  
  63.         String string = "[" + String.format("%s", liste.get(0).getData());
  64.  
  65.         for (int i = 1 ; i < liste.size() ; i++)
  66.             string += String.format(", %s", liste.get(i).getData());
  67.  
  68.         string += "]";
  69.  
  70.         return string;
  71.     }
  72. }



  • Recent Pastes