Java写一个二叉查找树

围巾🧣 2020年03月21日 600次浏览

简介

二叉树成为二叉查找树的性质是，对于树中的每个节点X,它的左子树中所有项的值小于X中的项，而它的右子树中所有项的值大于X中的项。

要求

  • 要有节点类、实现比较器，使得节点可以compareTo，使用泛型表节点数据
  • 成员变量：一个根节点
  • 成员方法：BinarySearchTree、contains、findMin、findMax、insert、remove

代码

  1. public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {

  3.     private BinaryNode<AnyType> root;

  5.     public BinarySearchTree() {
  6.         this.root = null;
  7.     }


  10.     public void makeEmpty() {
  11.         root = null;
  12.     }

  14.     public boolean isEmpty() {
  15.         return root == null;
  16.     }

  18.     public boolean contains(AnyType x) {
  19.         return contains(x, root);
  20.     }

  22.     public AnyType findMin() {
  23.         if (isEmpty()) {
  24.             return null;
  25.         }
  26.         return findMin(root).element;
  27.     }

  29.     public AnyType findMax() {
  30.         if (isEmpty()) {
  31.             return null;
  32.         }
  33.         return findMax(root).element;
  34.     }

  36.     public void insert(AnyType x) {
  37.         root = insert(x, root);
  38.     }

  40.     public void remove(AnyType x) {
  41.         root = remove(x, root);
  42.     }

  44.     public void printTree() {

  46.     }

  48.     /**
  49.      * 内部方法查找子树中的项。
  50.      *
  51.      * @param x 搜索项目
  52.      * @param t 子树的根节点
  53.      * @return 如果项目被发现，则为真;否则为假
  54.      */
  55.     private boolean contains(AnyType x, BinaryNode<AnyType> t) {

  57.         if (t == null) {
  58.             return false;
  59.         }
  60.         int compareResult = x.compareTo(t.element);

  62.         if (compareResult < 0) {
  63.             return contains(x, t.left);
  64.         } else if (compareResult > 0) {
  65.             return contains(x, t.right);
  66.         } else {
  67.             return true;
  68.         }
  69.     }

  71.     /**
  72.      * 递归查找
  73.      *
  74.      * @param t 子树的根节点
  75.      * @return 找到的值
  76.      */
  77.     private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
  78.         if (t == null) {
  79.             return null;
  80.         } else if (t.left == null) {
  81.             return t;
  82.         }
  83.         return findMin(t.left);
  84.     }

  86.     private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
  87.         if (t != null) {
  88.             while (t.right != null) {
  89.                 t = t.right;
  90.             }
  91.         }
  92.         return t;
  93.     }

  95.     /**
  96.      * 内部方法插入到子树中
  97.      *
  98.      * @param x 要插入的项
  99.      * @param t 子树的根节点
  100.      * @return the new root of the subtree
  101.      */
  102.     private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
  103.         if (t == null) {
  104.             return new BinaryNode<>(x, null, null);
  105.         }

  107.         // 对比，-1小于，0相等，1大于
  108.         int compareResult = x.compareTo(t.element);
  109.         if (compareResult < 0) {
  110.             t.left = insert(x, t.left);
  111.         } else if (compareResult > 0) {
  112.             t.right = insert(x, t.right);
  113.         } else { // Duplicate; do nothing

  115.         }
  116.         return t;
  117.     }

  119.     /**
  120.      * 从一颗子树移除
  121.      *
  122.      * @param x 被移除的项
  123.      * @param t 子树的根节点
  124.      * @return 新的值
  125.      */
  126.     private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
  127.         if (t == null) {
  128.             return t;
  129.         }
  130.         int compareResult = x.compareTo(t.element);

  132.         if (compareResult < 0) {
  133.             t.left = remove(x, t.left);
  134.         } else if (compareResult > 0) {
  135.             t.right = remove(x, t.right);
  136.         } else if (t.left != null && t.right != null) {
  137.             t.element = findMin(t.right).element;
  138.             t.right = remove(t.element, t.right);
  139.         } else {
  140.             t = (t.left != null) ? t.left : t.right;
  141.         }
  142.         return t;
  143.     }

  145.     private void printTree(BinaryNode<AnyType> t) {

  147.     }


  150.     private static class BinaryNode<AnyType> {
  151.         AnyType element;
  152.         BinaryNode<AnyType> left;
  153.         BinaryNode<AnyType> right;

  155.         public BinaryNode(AnyType element) {
  156.             this.element = element;
  157.         }

  159.         public BinaryNode(AnyType element, BinaryNode<AnyType> left, BinaryNode<AnyType> right) {
  160.             this.element = element;
  161.             this.left = left;
  162.             this.right = right;
  163.         }
  164.     }
  165. }
上一篇： 插入排序