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



  • Recent Pastes