Arbre de recherche binaire - Implémentation Java

Question

J'écris un programme qui utilise un arbre de recherche binaire pour stocker des données. Dans un programme précédent (sans rapport), j'ai pu implémenter une liste chaînée en utilisant un arbre de recherche binaire. mise en œuvre fourni avec Java SE6. Existe-t-il quelque chose de similaire pour un arbre de recherche binaire, ou dois-je "partir de zéro" ?

Answer 1

---

Voici l'implémentation complète de l'arbre de recherche binaire en Java insert, search, countNodes, traversal, delete, empty, maximum & minimum node, find parent node, print all leaf node, get level, get height, get depth, print left view, mirror view.

---

import java.util.NoSuchElementException;
import java.util.Scanner;

import org.junit.experimental.max.MaxCore;

class BSTNode {

    BSTNode left = null;
    BSTNode rigth = null;
    int data = 0;

    public BSTNode() {
        super();
    }

    public BSTNode(int data) {
        this.left = null;
        this.rigth = null;
        this.data = data;
    }

    @Override
    public String toString() {
        return "BSTNode [left=" + left + ", rigth=" + rigth + ", data=" + data + "]";
    }

}

class BinarySearchTree {

    BSTNode root = null;

    public BinarySearchTree() {

    }

    public void insert(int data) {
        BSTNode node = new BSTNode(data);
        if (root == null) {
            root = node;
            return;
        }

        BSTNode currentNode = root;
        BSTNode parentNode = null;

        while (true) {
            parentNode = currentNode;
            if (currentNode.data == data)
                throw new IllegalArgumentException("Duplicates nodes note allowed in Binary Search Tree");

            if (currentNode.data > data) {
                currentNode = currentNode.left;
                if (currentNode == null) {
                    parentNode.left = node;
                    return;
                }
            } else {
                currentNode = currentNode.rigth;
                if (currentNode == null) {
                    parentNode.rigth = node;
                    return;
                }
            }
        }
    }

    public int countNodes() {
        return countNodes(root);
    }

    private int countNodes(BSTNode node) {
        if (node == null) {
            return 0;
        } else {
            int count = 1;
            count += countNodes(node.left);
            count += countNodes(node.rigth);
            return count;
        }
    }

    public boolean searchNode(int data) {
        if (empty())
            return empty();
        return searchNode(data, root);
    }

    public boolean searchNode(int data, BSTNode node) {
        if (node != null) {
            if (node.data == data)
                return true;
            else if (node.data > data)
                return searchNode(data, node.left);
            else if (node.data < data)
                return searchNode(data, node.rigth);
        }
        return false;
    }

    public boolean delete(int data) {
        if (empty())
            throw new NoSuchElementException("Tree is Empty");

        BSTNode currentNode = root;
        BSTNode parentNode = root;
        boolean isLeftChild = false;

        while (currentNode.data != data) {
            parentNode = currentNode;
            if (currentNode.data > data) {
                isLeftChild = true;
                currentNode = currentNode.left;
            } else if (currentNode.data < data) {
                isLeftChild = false;
                currentNode = currentNode.rigth;
            }
            if (currentNode == null)
                return false;
        }

        // CASE 1: node with no child
        if (currentNode.left == null && currentNode.rigth == null) {
            if (currentNode == root)
                root = null;
            if (isLeftChild)
                parentNode.left = null;
            else
                parentNode.rigth = null;
        }

        // CASE 2: if node with only one child
        else if (currentNode.left != null && currentNode.rigth == null) {
            if (root == currentNode) {
                root = currentNode.left;
            }
            if (isLeftChild)
                parentNode.left = currentNode.left;
            else
                parentNode.rigth = currentNode.left;
        } else if (currentNode.rigth != null && currentNode.left == null) {
            if (root == currentNode)
                root = currentNode.rigth;
            if (isLeftChild)
                parentNode.left = currentNode.rigth;
            else
                parentNode.rigth = currentNode.rigth;
        }

        // CASE 3: node with two child
        else if (currentNode.left != null && currentNode.rigth != null) {

            // Now we have to find minimum element in rigth sub tree
            // that is called successor
            BSTNode successor = getSuccessor(currentNode);
            if (currentNode == root)
                root = successor;
            if (isLeftChild)
                parentNode.left = successor;
            else
                parentNode.rigth = successor;
            successor.left = currentNode.left;
        }

        return true;
    }

    private BSTNode getSuccessor(BSTNode deleteNode) {

        BSTNode successor = null;
        BSTNode parentSuccessor = null;
        BSTNode currentNode = deleteNode.left;

        while (currentNode != null) {
            parentSuccessor = successor;
            successor = currentNode;
            currentNode = currentNode.left;
        }

        if (successor != deleteNode.rigth) {
            parentSuccessor.left = successor.left;
            successor.rigth = deleteNode.rigth;
        }

        return successor;
    }

    public int nodeWithMinimumValue() {
        return nodeWithMinimumValue(root);
    }

    private int nodeWithMinimumValue(BSTNode node) {
        if (node.left != null)
            return nodeWithMinimumValue(node.left);
        return node.data;
    }

    public int nodewithMaximumValue() {
        return nodewithMaximumValue(root);
    }

    private int nodewithMaximumValue(BSTNode node) {
        if (node.rigth != null)
            return nodewithMaximumValue(node.rigth);
        return node.data;
    }

    public int parent(int data) {
        return parent(root, data);
    }

    private int parent(BSTNode node, int data) {
        if (empty())
            throw new IllegalArgumentException("Empty");
        if (root.data == data)
            throw new IllegalArgumentException("No Parent node found");

        BSTNode parent = null;
        BSTNode current = node;

        while (current.data != data) {
            parent = current;
            if (current.data > data)
                current = current.left;
            else
                current = current.rigth;
            if (current == null)
                throw new IllegalArgumentException(data + " is not a node in tree");
        }
        return parent.data;
    }

    public int sibling(int data) {
        return sibling(root, data);
    }

    private int sibling(BSTNode node, int data) {
        if (empty())
            throw new IllegalArgumentException("Empty");
        if (root.data == data)
            throw new IllegalArgumentException("No Parent node found");

        BSTNode cureent = node;
        BSTNode parent = null;
        boolean isLeft = false;

        while (cureent.data != data) {
            parent = cureent;
            if (cureent.data > data) {
                cureent = cureent.left;
                isLeft = true;
            } else {
                cureent = cureent.rigth;
                isLeft = false;
            }
            if (cureent == null)
                throw new IllegalArgumentException("No Parent node found");
        }
        if (isLeft) {
            if (parent.rigth != null) {
                return parent.rigth.data;
            } else
                throw new IllegalArgumentException("No Sibling is there");
        } else {
            if (parent.left != null)
                return parent.left.data;
            else
                throw new IllegalArgumentException("No Sibling is there");
        }
    }

    public void leafNodes() {
        if (empty())
            throw new IllegalArgumentException("Empty");
        leafNode(root);
    }

    private void leafNode(BSTNode node) {
        if (node == null)
            return;
        if (node.rigth == null && node.left == null)
            System.out.print(node.data + " ");
        leafNode(node.left);
        leafNode(node.rigth);
    }

    public int level(int data) {
        if (empty())
            throw new IllegalArgumentException("Empty");
        return level(root, data, 1);
    }

    private int level(BSTNode node, int data, int level) {
        if (node == null)
            return 0;
        if (node.data == data)
            return level;
        int result = level(node.left, data, level + 1);
        if (result != 0)
            return result;
        result = level(node.rigth, data, level + 1);
        return result;
    }

    public int depth() {
        return depth(root);
    }

    private int depth(BSTNode node) {
        if (node == null)
            return 0;
        else
            return 1 + Math.max(depth(node.left), depth(node.rigth));
    }

    public int height() {
        return height(root);
    }

    private int height(BSTNode node) {
        if (node == null)
            return 0;
        else
            return 1 + Math.max(height(node.left), height(node.rigth));
    }

    public void leftView() {
        leftView(root);
    }

    private void leftView(BSTNode node) {
        if (node == null)
            return;
        int height = height(node);

        for (int i = 1; i <= height; i++) {
            printLeftView(node, i);
        }
    }

    private boolean printLeftView(BSTNode node, int level) {
        if (node == null)
            return false;

        if (level == 1) {
            System.out.print(node.data + " ");
            return true;
        } else {
            boolean left = printLeftView(node.left, level - 1);
            if (left)
                return true;
            else
                return printLeftView(node.rigth, level - 1);
        }
    }

    public void mirroeView() {
        BSTNode node = mirroeView(root);
        preorder(node);
        System.out.println();
        inorder(node);
        System.out.println();
        postorder(node);
        System.out.println();
    }

    private BSTNode mirroeView(BSTNode node) {
        if (node == null || (node.left == null && node.rigth == null))
            return node;

        BSTNode temp = node.left;
        node.left = node.rigth;
        node.rigth = temp;

        mirroeView(node.left);
        mirroeView(node.rigth);
        return node;
    }

    public void preorder() {
        preorder(root);
    }

    private void preorder(BSTNode node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preorder(node.left);
            preorder(node.rigth);
        }
    }

    public void inorder() {
        inorder(root);
    }

    private void inorder(BSTNode node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.data + " ");
            inorder(node.rigth);
        }
    }

    public void postorder() {
        postorder(root);
    }

    private void postorder(BSTNode node) {
        if (node != null) {
            postorder(node.left);
            postorder(node.rigth);
            System.out.print(node.data + " ");
        }
    }

    public boolean empty() {
        return root == null;
    }

}

public class BinarySearchTreeTest {
    public static void main(String[] l) {
        System.out.println("Weleome to Binary Search Tree");
        Scanner scanner = new Scanner(System.in);
        boolean yes = true;
        BinarySearchTree tree = new BinarySearchTree();
        do {
            System.out.println("\n1. Insert");
            System.out.println("2. Search Node");
            System.out.println("3. Count Node");
            System.out.println("4. Empty Status");
            System.out.println("5. Delete Node");
            System.out.println("6. Node with Minimum Value");
            System.out.println("7. Node with Maximum Value");
            System.out.println("8. Find Parent node");
            System.out.println("9. Count no of links");
            System.out.println("10. Get the sibling of any node");
            System.out.println("11. Print all the leaf node");
            System.out.println("12. Get the level of node");
            System.out.println("13. Depth of the tree");
            System.out.println("14. Height of Binary Tree");
            System.out.println("15. Left View");
            System.out.println("16. Mirror Image of Binary Tree");
            System.out.println("Enter Your Choice :: ");
            int choice = scanner.nextInt();
            switch (choice) {
            case 1:
                try {
                    System.out.println("Enter Value");
                    tree.insert(scanner.nextInt());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 2:
                System.out.println("Enter the node");
                System.out.println(tree.searchNode(scanner.nextInt()));
                break;

            case 3:
                System.out.println(tree.countNodes());
                break;

            case 4:
                System.out.println(tree.empty());
                break;

            case 5:
                try {
                    System.out.println("Enter the node");
                    System.out.println(tree.delete(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }

            case 6:
                try {
                    System.out.println(tree.nodeWithMinimumValue());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 7:
                try {
                    System.out.println(tree.nodewithMaximumValue());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 8:
                try {
                    System.out.println("Enter the node");
                    System.out.println(tree.parent(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 9:
                try {
                    System.out.println(tree.countNodes() - 1);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 10:
                try {
                    System.out.println("Enter the node");
                    System.out.println(tree.sibling(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 11:
                try {
                    tree.leafNodes();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }

            case 12:
                try {
                    System.out.println("Enter the node");
                    System.out.println("Level is : " + tree.level(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 13:
                try {
                    System.out.println(tree.depth());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 14:
                try {
                    System.out.println(tree.height());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 15:
                try {
                    tree.leftView();
                    System.out.println();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 16:
                try {
                    tree.mirroeView();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            default:
                break;
            }
            tree.preorder();
            System.out.println();
            tree.inorder();
            System.out.println();
            tree.postorder();
        } while (yes);
        scanner.close();
    }
}

Answer 2

Voici l'implémentation de l'arbre de recherche binaire

public class BST<Key extends Comparable<Key>,Value>{

   private Node root;

   private class Node{
       private Key key;
       private Value val;
       private Node left, right;
       private int N;

       public Node(Key key,Value val,int N)
       {   this.key = key; this.val=val; this.N=N;}
   }
   public int size(){
      return size(root);
   }
   public int size(Node x){
      if(x==null)  return 0;
      else
          return x.N;
   }
   public Value get(Key key){
        return get(root,key);
   }
   private Value get(Node x, Key key){
       if(x==null) return null;
       int cmp = key.compareTo(x.key);
       if (cmp<0) return get(x.left,key);
       else if (cmp<0) return get(x.right,key);
       else return x.val;
   }
   public Node put(Key key,Value val){
       return root = put(root,Key,val);
   }
   private Node put(Node x, Key key, Value val){
       if(x==null ) return new Node(key ,val,1);
       int cmp =key.compareTo(x.key);
       if(cmp<0) x.left= put(x.left,key,val);
       else if(cmp>0)  x.right= put(x.right,key,val);
       else x.val=val;
       x.N=size(x.left)+size(x.right)+1;
       return x;   
    }  

   public Key min(){
       return min(root).key;
   }
   private Node min(Node x){
       if(x.left==null) return x;
       return min(x.left);
   }
    public Key max(){
       return max(root).key;//min() changed to max()
   }
    private Node max(Node x){
       if(x.right==null) return x;
       return max(x.right);
   }
   public Key select(int k){
       return select(root,k).key;
   }
   private Node select(Node x,int k)
   {
       if(x==null)return null;//conditinoal equals
       int t=size(x.left);
       if(t>k) return(x.left,k);
       else if(t<k) return(x.right,k-t-1);
       else    return x;
   } 
   public int rank(Key key,Node x)
   {  return rank(key,root);   }
   private int rank(Key key,Node x){
      if(x==null) return 0;
      int cmp =key.compareTo(x.key);
      if(cmp<0) return rank(key,x.left);
      else if(cmp>0) return 1+size(x.left)+rank(key,x.right);
      else   return size(x.left);
   }
   public void deleteMin(){
      root= deleteMin(root);
   }
   private Node deleteMin(Node x){
      if(x.left==null) return x.right;
      x.left=deleteMin(x.left);
      x.N =size(x.left)+size(x.right)+1;
      return x;
   }

   public void deleteMax(){
      root= deleteMax(root);//recursive call deleteMax()
   }
   private Node deleteMax(Node x){
      if(x.right==null) return x.left;
      x.right=deleteMax(x.right);
      x.N =size(x.right)+size(x.left)+1;
      return x;
   }

   public void delete(Key key){
      root=delete(root,key)
   }
   private Node delete(Node x,Key key){
      if(x==null) return null;
      int cmp = key.compareTo(x.key);
      if(cmp<0)x.left = delete(x.left,key);
      else if(cmp>0) x.right= delete(x.right,key);
      else{
          if(x.right==null) return x.left;
          if(x.left==null) return x.right;
          Node t =x;
          x=min(t.right);
          x.right=deleteMin(t.right);
          x.left=t.left;
      }
    x.N=size(x.left)+size(x.right)+1;
    return x;
   }

}