構建二叉搜索樹在Java中

Question

我試圖構建在Java中這二叉搜索樹： 這裏是我的鏈接二叉搜索樹實現類：

/** 
* LinkedBinarySearchTree implements the BinarySearchTreeADT interface 
* with links. 
* 
* @author Java Foundations 
* @version 4.0 
*/ 
public class LinkedBinarySearchTree<T> extends LinkedBinaryTree<T> 
             implements BinarySearchTreeADT<T> 
{ 
    /** 
    * Creates an empty binary search tree. 
    */ 
    public LinkedBinarySearchTree() 
    { 
     super(); 
    } 

    /** 
    * Creates a binary search with the specified element as its root. 
    * 
    * @param element the element that will be the root of the new binary 
    *  search tree 
    */ 
    public LinkedBinarySearchTree(T element) 
    { 
     super(element); 

     if (!(element instanceof Comparable)) 
      throw new NonComparableElementException("LinkedBinarySearchTree"); 
    } 

    /** 
    * Adds the specified object to the binary search tree in the 
    * appropriate position according to its natural order. Note that 
    * equal elements are added to the right. 
    * 
    * @param element the element to be added to the binary search tree 
    */ 
    public void addElement(T element) 
    { 
     if (!(element instanceof Comparable)) 
      throw new NonComparableElementException("LinkedBinarySearchTree"); 

     Comparable<T> comparableElement = (Comparable<T>)element; 

     if (isEmpty()) 
      root = new BinaryTreeNode<T>(element); 
     else 
     { 
      if (comparableElement.compareTo(root.getElement()) < 0) 
      { 
       if (root.getLeft() == null) 
        this.getRootNode().setLeft(new BinaryTreeNode<T>(element)); 
       else 
        addElement(element, root.getLeft()); 
      } 
      else 
      { 
       if (root.getRight() == null) 
        this.getRootNode().setRight(new BinaryTreeNode<T>(element)); 
       else 
        addElement(element, root.getRight()); 
      } 
     } 
     modCount++; 
    } 

    /** 
    * Adds the specified object to the binary search tree in the 
    * appropriate position according to its natural order. Note that 
    * equal elements are added to the right. 
    * 
    * @param element the element to be added to the binary search tree 
    */ 
    private void addElement(T element, BinaryTreeNode<T> node) 
    { 
     Comparable<T> comparableElement = (Comparable<T>)element; 

     if (comparableElement.compareTo(node.getElement()) < 0) 
     { 
      if (node.getLeft() == null) 
       node.setLeft(new BinaryTreeNode<T>(element)); 
      else 
       addElement(element, node.getLeft()); 
     } 
     else 
     { 
      if (node.getRight() == null) 
       node.setRight(new BinaryTreeNode<T>(element)); 
      else 
       addElement(element, node.getRight()); 
     } 
    } 


    /** 
    * Removes the first element that matches the specified target 
    * element from the binary search tree and returns a reference to 
    * it. Throws a ElementNotFoundException if the specified target 
    * element is not found in the binary search tree. 
    * 
    * @param targetElement the element being sought in the binary search tree 
    * @throws ElementNotFoundException if the target element is not found 
    */ 
    public T removeElement(T targetElement) 
            throws ElementNotFoundException 
    { 
     T result = null; 

     if (isEmpty()) 
      throw new ElementNotFoundException("LinkedBinarySearchTree"); 
     else 
     { 
      BinaryTreeNode<T> parent = null; 
      if (((Comparable<T>)targetElement).equals(root.element)) 
      { 
       result = root.element; 
       BinaryTreeNode<T> temp = replacement(root); 
       if (temp == null) 
        root = null; 
       else 
       { 
        root.element = temp.element; 
        root.setRight(temp.right); 
        root.setLeft(temp.left); 
       } 

       modCount--; 
      } 
      else 
      {     
       parent = root; 
       if (((Comparable)targetElement).compareTo(root.element) < 0) 
        result = removeElement(targetElement, root.getLeft(), parent); 
       else 
        result = removeElement(targetElement, root.getRight(), parent); 
      } 
     } 

     return result; 
    } 

    /** 
    * Removes the first element that matches the specified target 
    * element from the binary search tree and returns a reference to 
    * it. Throws a ElementNotFoundException if the specified target 
    * element is not found in the binary search tree. 
    * 
    * @param targetElement the element being sought in the binary search tree 
    * @param node the node from which to search 
    * @param parent the parent of the node from which to search 
    * @throws ElementNotFoundException if the target element is not found 
    */ 
    private T removeElement(T targetElement, BinaryTreeNode<T> node, BinaryTreeNode<T> parent) 
    throws ElementNotFoundException 
    { 
     T result = null; 

     if (node == null) 
      throw new ElementNotFoundException("LinkedBinarySearchTree"); 
     else 
     { 
      if (((Comparable<T>)targetElement).equals(node.element)) 
      { 
       result = node.element; 
       BinaryTreeNode<T> temp = replacement(node); 
       if (parent.right == node) 
        parent.right = temp; 
       else 
        parent.left = temp; 

       modCount--; 
      } 
      else 
      {     
       parent = node; 
       if (((Comparable)targetElement).compareTo(node.element) < 0) 
        result = removeElement(targetElement, node.getLeft(), parent); 
       else 
        result = removeElement(targetElement, node.getRight(), parent); 
      } 
     } 

     return result; 
    } 

    /** 
    * Returns a reference to a node that will replace the one 
    * specified for removal. In the case where the removed node has 
    * two children, the inorder successor is used as its replacement. 
    * 
    * @param node the node to be removed 
    * @return a reference to the replacing node 
    */ 
    private BinaryTreeNode<T> replacement(BinaryTreeNode<T> node) 
    { 
     BinaryTreeNode<T> result = null; 

     if ((node.left == null) && (node.right == null)) 
      result = null; 

     else if ((node.left != null) && (node.right == null)) 
      result = node.left; 

     else if ((node.left == null) && (node.right != null)) 
      result = node.right; 

     else 
     { 
      BinaryTreeNode<T> current = node.right; 
      BinaryTreeNode<T> parent = node; 

      while (current.left != null) 
      { 
       parent = current; 
       current = current.left; 
      } 

      current.left = node.left; 
      if (node.right != current) 
      { 
       parent.left = current.right; 
       current.right = node.right; 
      } 

      result = current; 
     } 

     return result; 
    } 

    /** 
    * Removes elements that match the specified target element from 
    * the binary search tree. Throws a ElementNotFoundException if 
    * the specified target element is not found in this tree. 
    * 
    * @param targetElement the element being sought in the binary search tree 
    * @throws ElementNotFoundException if the target element is not found 
    */ 
    public void removeAllOccurrences(T targetElement) 
        throws ElementNotFoundException 
    { 
     removeElement(targetElement); 

     try 
     { 
      while (contains((T)targetElement)) 
       removeElement(targetElement); 
     } 

     catch (Exception ElementNotFoundException) 
     { 
     } 
    } 

    /** 
    * Removes the node with the least value from the binary search 
    * tree and returns a reference to its element. Throws an 
    * EmptyCollectionException if this tree is empty. 
    * 
    * @return a reference to the node with the least value 
    * @throws EmptyCollectionException if the tree is empty 
    */ 
    public T removeMin() throws EmptyCollectionException 
    { 
     T result = null; 

     if (isEmpty()) 
      throw new EmptyCollectionException("LinkedBinarySearchTree"); 
     else 
     { 
      if (root.left == null) 
      { 
       result = root.element; 
       root = root.right; 
      } 
      else 
      { 
       BinaryTreeNode<T> parent = root; 
       BinaryTreeNode<T> current = root.left; 
       while (current.left != null) 
       { 
        parent = current; 
        current = current.left; 
       } 
       result = current.element; 
       parent.left = current.right; 
      } 

      modCount--; 
     } 

     return result; 
    } 

    /** 
    * Removes the node with the highest value from the binary 
    * search tree and returns a reference to its element. Throws an 
    * EmptyCollectionException if this tree is empty. 
    * 
    * @return a reference to the node with the highest value 
    * @throws EmptyCollectionException if the tree is empty 
    */ 
    public T removeMax() throws EmptyCollectionException 
    { 

     T result = null; 

     if (isEmpty()) 
       throw new EmptyCollectionException ("binary tree"); 
     else 
     { 
      if (root.right == null) 
      { 
       result = root.element; 
       root = root.left; 
      } //if 
      else 
      { 
       BinaryTreeNode<T> parent = root; 
       BinaryTreeNode<T> current = root.right; 

       while (current.right != null) 
       { 
        parent = current; 
        current = current.right; 
       } //while 

       result = current.element; 
       parent.right = current.left; 
       } //else 

      modCount--; 
     } //else 

     return result; 
    } 

    /** 
    * Returns the element with the least value in the binary search 
    * tree. It does not remove the node from the binary search tree. 
    * Throws an EmptyCollectionException if this tree is empty. 
    * 
    * @return the element with the least value 
    * @throws EmptyCollectionException if the tree is empty 
    */ 
    public T findMin() throws EmptyCollectionException 
    { 

     T result = null; 

     if (isEmpty()) 
      throw new EmptyCollectionException ("binary tree"); 
     else 
     { 
      BinaryTreeNode<T> current = root; 

      while (current.left != null) 
       current = current.left; 

      result = current.element; 
     } //else 

     return result; 
    } 

    /** 
    * Returns the element with the highest value in the binary 
    * search tree. It does not remove the node from the binary 
    * search tree. Throws an EmptyCollectionException if this 
    * tree is empty. 
    * 
    * @return the element with the highest value 
    * @throws EmptyCollectionException if the tree is empty 
    */ 
    public T findMax() throws EmptyCollectionException 
    { 
     T result = null; 

     if (isEmpty()) 
       throw new EmptyCollectionException ("binary tree"); 
     else 
     { 
      BinaryTreeNode<T> current = root; 

      while (current.right != null) 
       current = current.right; 

      result = current.element; 
     } //else 

     return result; 

    } 

    /** 
    * Returns a reference to the specified target element if it is 
    * found in the binary tree. Throws a NoSuchElementException if 
    * the specified target element is not found in this tree. 
    * 
    * @param targetElement the element being sought in the binary tree 
    * @throws ElementNotFoundException if the target element is not found 
    */ 
    public T find(T targetElement) throws ElementNotFoundException 
    { 

     BinaryTreeNode<T> current = root; 
     BinaryTreeNode<T> temp = current; 


     if (!(current.element.equals(targetElement)) && (current.left !=null)&&(((Comparable)current.element).compareTo(targetElement) > 0)) 
     current = findNode(targetElement, current.left); 

     else if (!(current.element.equals(targetElement)) && (current.right != null)) 
     current = findNode(targetElement, current.right); 

     if (!(current.element.equals(targetElement))) 
      throw new ElementNotFoundException ("binarytree"); 

     return current.element; 
    } 

    /** 
    * Returns the left subtree of the root of this tree. 
    * 
    * @return a link to the left subtree of the tree 
    */ 
    public LinkedBinarySearchTree<T> getLeft() 
    { 
     if (root == null) 
      throw new EmptyCollectionException("getLeft failed - the tree is empty"); 
     LinkedBinarySearchTree <T> result = new LinkedBinarySearchTree<T>(); 
     result.root = root.getLeft(); 
     return result; 
    } 

    /** 
    * Returns the right subtree of the root of this tree. 
    * 
    * @return a link to the right subtree of the tree 
    */ 
    public LinkedBinarySearchTree<T> getRight() 
    { 

     if (root == null) 
      throw new EmptyCollectionException("getLeft failed - the tree is empty"); 
     LinkedBinarySearchTree <T> result = new LinkedBinarySearchTree<T>(); 
     result.root = root.getRight(); 
     return result; 
    } 

    /** 
    * Returns a reference to the specified target element if it is 
    * found in this tree. 
    * 
    * @param targetElement the element being sought in the tree 
    * @param next the tree node to begin searching on 
    */ 
    private BinaryTreeNode<T> findNode(T targetElement, BinaryTreeNode<T> next) 
    { 
     BinaryTreeNode<T> current = next; 
     if (!(next.element.equals(targetElement)) && (next.left !=null) &&(((Comparable)next.element).compareTo(targetElement) > 0)) 
     next = findNode(targetElement, next.left); 
     else if (!(next.element.equals(targetElement)) && (next.right != null)) 
     next = findNode(targetElement, next.right);      

    return next; 
    } 

    /*balances the binary search tree so that it maintains 
    * the maximum difference of the path lengths of the 
    * left and right children as not more than one*/ 
    public void balance() { 
     //verify if balance factor of the root of the tree is -2 
     if(getBalanceFactor(root) == -2) { 
      //verify if balance factor of left child of tree root is 1 
      if(getBalanceFactor(root.left) == 1) 
       root = leftRightRotation(root); 
      else 
       root = rightRotation(root); 

     } 
     //verify if balance factor of tree root is 2 
     else if(getBalanceFactor(root) == 2) { 
      //verify if balance factor of right child of tree root is -1 
      if(getBalanceFactor(root.right) == -1) { 
       root = rightLeftRotation(root); 
      } 
      else 
       root = leftRotation(root); 
     } 
    } 

    /*performs right rotation and left rotation, then returns new root*/ 
    private BinaryTreeNode<T> rightLeftRotation(BinaryTreeNode<T> current) { 
     current.right = rightRotation(current.right); 

     current = leftRotation(current); 

     return current; 
    } 

    /*performs left rotation then right rotation then returns new root*/ 
    private BinaryTreeNode<T> leftRightRotation(BinaryTreeNode<T> current) { 
     current.left = leftRotation(current.left); 

     current = rightRotation(current); 

     return current; 
    } 

    /*returns new root after performing right rotation of specified node*/ 
    private BinaryTreeNode<T> rightRotation(BinaryTreeNode<T> current) { 

     BinaryTreeNode<T> newRoot = current.left; 
     BinaryTreeNode<T> temp = newRoot.right; 

     newRoot.right = current; 

     current.left = temp; 

     return newRoot; 
    } 

    //returns new root after performing left rotation of specified node 
    private BinaryTreeNode<T> leftRotation(BinaryTreeNode<T> current) { 
     BinaryTreeNode<T> newRoot = current.right; 
     BinaryTreeNode<T> temp = newRoot.left; 

     newRoot.left = current; 

     current.right = temp; 

     return newRoot; 
    } 

    //returns difference between path lengths of heights of left and right sides of root 
    private int getBalanceFactor(BinaryTreeNode<T> current) { 
     int leftHeight = getHeight(current.left); 

     int rightHeight = getHeight(current.right); 

     return(rightHeight - leftHeight); 
    } 

    //returns the height of the specified node 
    private int getHeight(BinaryTreeNode<T> newRoot) { 
     if(newRoot == null) 
      return 0; 
     else 
      return 1 + Math.max(getHeight(newRoot.left), getHeight(newRoot.right)); 

    } 

} 

這裏是我的驅動程序在我的utlimate目標是從圖像創建二叉搜索樹上面，平衡它，測試它是否平衡：

import java.util.*; 
import java.io.*; 


public class IsHeightBalanced { 

    public static void main(String[] args) { 

     LinkedBinarySearchTree<int> tree = new LinkedBinarySearchTree<int>; 

     tree.addElement(13); 
     tree.addElement(7); 
     tree.addElement(15); 
     tree.addElement(5); 
     tree.addElement(10); 
     tree.addElement(3); 


    } 

} 

現在我只是想構建二叉搜索樹從這裏的圖片和T他行

LinkedBinarySearchTree<int> tree = new LinkedBinarySearchTree<int>(); 

是給我像「插入尺寸來完成引用類型」

這是爲什麼做出這樣的錯誤錯誤？我在正確的軌道上創建上圖中的二叉搜索樹嗎？謝謝。

Answer 1

您無法實例化具有原始類型的泛型類型。 爲例

考慮下面的參數化類型：

class Pair<K, V> { 

    private K key; 
    private V value; 

    public Pair(K key, V value) { 
     this.key = key; 
     this.value = value; 
    } 

    // ... 
} 

當創建一對對象，你不能代替原始類型的類型參數K或V：

Pair<int, char> p = new Pair<>(8, 'a'); // compile-time error 

你可以只用非原始類型替換類型參數K和V：

Pair<Integer, Character> p = new Pair<>(8, 'a'); 

注意，Java編譯器autoboxes 8 Integer.valueOf（8）和 'a' 到字符（ 'A'）：

Pair<Integer, Character> p = new Pair<>(Integer.valueOf(8), new Character('a'));