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



New paste | Download | Show/Hide line no. | Copy text to clipboard
  1. import java.util.List;
  2.  
  3. public class BinaryNode<T extends Comparable<? super T> > {
  4.         private T data;
  5.         private BinaryNode<T> right;
  6.         private BinaryNode<T> left;
  7.  
  8.         // TODO: initialisation
  9.         // O(1)
  10.         public BinaryNode(T data) {
  11.                 this.data = data;
  12.                 right = null;
  13.                 left = null;
  14.         }
  15.  
  16.         // TODO: on retourne la donnee voulue
  17.         // O(1)
  18.         public T getData() {
  19.                 return data;
  20.         }
  21.  
  22.         // TODO: on ajoute une nouvelle donnee au bon endroit
  23.         // O(log(n))
  24.         public void insert(T item) {
  25.                 if ( item.compareTo( data ) > 0){
  26.                         if ( right == null)
  27.                                 right = new BinaryNode<T>(item);
  28.                         else
  29.                                 right.insert( item );
  30.                    
  31.                 }
  32.                 else {
  33.                         if ( left == null )
  34.                                 left = new BinaryNode<T>(item);
  35.                         else
  36.                                 left.insert( item );
  37.                 }
  38.         }
  39.  
  40.         // TODO: est-ce que l'item fais partie du noeuds courant
  41.         // O(log(n))
  42.         public boolean contains(T item) {
  43.                 if ( item.equals( data ) )
  44.                         return true;
  45.                 if ( item.compareTo( data ) > 0){
  46.                         if ( right != null )
  47.                                 return right.contains( item );
  48.                 }
  49.                 else{
  50.                         if ( left != null )
  51.                                 return left.contains( item );
  52.                 }
  53.                 return false;
  54.         }
  55.  
  56.         // TODO: on retourne la maximale de l'arbre
  57.         // O(n)
  58.         public int getHeight() {
  59.                 int rightHeight = 0, leftHeight = 0;
  60.                
  61.                 if ( right != null)
  62.                         rightHeight = right.getHeight() + 1;
  63.  
  64.                 if ( left !=  null )
  65.                         leftHeight = left.getHeight() + 1;
  66.                
  67.                 return ( leftHeight > rightHeight)? leftHeight : rightHeight;
  68.         }
  69.  
  70.         // TODO: l'ordre d'insertion dans la liste est l'ordre logique
  71.         // de manière que le plus petit item sera le premier inseré
  72.         // O(n)
  73.         public void fillListInOrder(List<BinaryNode<T>> result) {
  74.                 if(left != null)
  75.                         left.fillListInOrder(result);
  76.  
  77.                 result.add(this);
  78.  
  79.                 if(right != null)
  80.                         right.fillListInOrder(result);
  81.                                
  82.                                
  83.         }
  84. }



  • Recent Pastes