Java数据结构之二叉排序树的实现

public class BinarySearchTree { /** * 外部保存根节点的引用 */ private BinaryTreeNode root; /** * 自定义比较器 */ private Comparator cmp; /** * 树节点的数量 */ private int size; /** * 内部节点对象 * * @param  数据类型 */ public static class BinaryTreeNode { //数据域 E data; //左子节点 BinaryTreeNode left; //右子节点 BinaryTreeNode right; public BinaryTreeNode(E data) { this.data = data; } @Override public String toString() { return data.toString(); } } /** * 指定比较器 * * @param cmp 比较器 */ public BinarySearchTree(Comparator cmp) { this.cmp = cmp; } /** * 空构造器 */ public BinarySearchTree() { } /** * 是否是空树 * * @return true 是 ;false 否 */ public boolean isEmpty() { return size == 0; } /** * 返回节点数 * * @return 节点数 */ public int size() { return size; } /** * 对元素进行比较大小的方法,如果传递了自定义比较器,则使用自定义比较器,否则则需要数据类型实现Comparable接口 * * @param e1 被比较的第一个对象 * @param e2 被比较的第二个对象 * @return 0 相等 ;小于0 e1  e2 */ private int compare(E e1, E e2) { if (cmp != null) { return cmp.compare(e1, e2); } else { return ((Comparable) e1).compareTo(e2); } } /** * 保存遍历出来的节点数据 */ List> str = new ArrayList<>(); /** * 中序遍历,提供给外部使用的api * * @return 遍历的数据 */ public String toInorderTraversalString() { //如果是空树,直接返回空 if (isEmpty()) { return null; } //从根节点开始递归 inorderTraversal(root); //获取遍历结果 String s = str.toString(); str.clear(); return s; } /** * 中序遍历 内部使用的递归遍历方法,借用了栈的结构 * * @param root 节点,从根节点开始 */ private void inorderTraversal(BinaryTreeNode root) { BinaryTreeNode left = getLeft(root); if (left != null) { //如果左子节点不为null,则继续递归遍历该左子节点 inorderTraversal(left); } //添加数据节点 str.add(root); //获取节点的右子节点 BinaryTreeNode right = getRight(root); if (right != null) { //如果右子节点不为null,则继续递归遍历该右子节点 inorderTraversal(right); } } /** * 获取左子节点 * * @param parent 父节点引用 * @return 左子节点或者null--表示没有左子节点 */ public BinaryTreeNode getLeft(BinaryTreeNode parent) { return parent == null ? null : parent.left; } /** * 获取右子节点 * * @param parent 父节点引用 * @return 右子节点或者null--表示没有右子节点 */ public BinaryTreeNode getRight(BinaryTreeNode parent) { return parent == null ? null : parent.right; } /** * 获取根节点 * * @return 根节点 ;或者null--表示空树 */ public BinaryTreeNode getRoot() { return root; } } 

/** * 查找,开放给外部使用的api */ public boolean contains(E e) { return contains(e, root); } /** * 查找,内部调用的方法,从根节点开始查找 * * @param e    要查找的元素 * @param root 节点 * @return false 不存在 true 存在 */ private boolean contains(E e, BinaryTreeNode root) { /*null校验*/ if (root == null) { return false; } /*调用比较的方法*/ int i = compare(e, root.data); /*如果大于0，则说明e>root.date 继续查询右子树*/ if (i > 0) { return contains(e, root.right); /*如果小于0，则说明e

/** * 插入,开放给外部使用的api * * @param e 要插入的元素 */ public void insert(E e) { //返回root,但此时新的节点可能已经被插入进去了 root = insert(e, root); } /** * 插入,开放给外部使用的api * * @param es 要插入的元素的数组,注意,数组元素的顺序存储的位置将会影响二叉排序树的生成 */ public void insert(E[] es) { //返回root,但此时新的节点可能已经被插入进去了 for (E e : es) { root = insert(e, root); } } /** * 插入,内部调用的方法,先从根节点开始递归查找要插入的位置,然后插入 * * @param e    要插入的数据 * @param root 节点 * @return 原节点或者新插入的节点 */ private BinaryTreeNode insert(E e, BinaryTreeNode root) { /*没有查找到,那么直接构建新的节点返回,将会在上一层方法中被赋值给其父节点的某个引用,这个插入的位置肯定是该遍历路径上的最后一点 * 即插入的元素节点肯定是属于叶子节点*/ if (root == null) { size++; return new BinaryTreeNode<>(e); } /*调用比较的方法*/ int i = compare(e, root.data); /*如果大于0，则说明e>root.date 继续查询右子树*/ if (i > 0) { //重新赋值 root.right = insert(e, root.right); /*如果小于0，则说明e

public class BinarySearchTreeTest { BinarySearchTree binarySearchTree = new BinarySearchTree<>(); @Test public void insert() { //首先要插入根节点47，然后是第二层的节点16,73，然后是第三层的节点1,24,59,88，然后是第四层的节点20,35,62,77。 // 每一层内部节点的顺序可以不一致，但是每一层之间的打顺序一定要保持一致，否则虽然中序遍历输出的时候能够正常输出,但是树的结构不能保证。 Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77}; binarySearchTree.insert(es); //中序遍历输出 System.out.println(binarySearchTree.toInorderTraversalString()); //查找某个数据是否存在 System.out.println(binarySearchTree.contains(1)); System.out.println(binarySearchTree.contains(2)); } } 

/** * 查找最小的节点 * * @param root 根节点 * @return 最小的节点 */ private BinaryTreeNode findMin(BinaryTreeNode root) { if (root == null) { return null; /*如果该节点没有左右子节点，那么该节点就是最小的节点，返回*/ } else if (root.left == null) { return root; } /*如果该节点存在左子节点，那么继续向左递归查找*/ return findMin(root.left); } /** * 查找最大的节点 * * @param root 根节点 * @return 最大的节点 */ private BinaryTreeNode findMax(BinaryTreeNode root) { if (root == null) { return null; /*如果该节点没有右子节点，那么该节点就是最大的节点，返回*/ } else if (root.right == null) { return root; } /*如果该节点存在右子节点，那么继续向右递归查找*/ return findMax(root.right); } 

    /** * 删除,开放给外部使用的api * * @param e 要删除的元素 */ public void delete(E e) { //返回root,但此时可能有一个节点已经被删除了 root = delete(e, root); } /** * 删除,内部调用的方法,删除分为三种情况: 1、该节点没有子节点 2、该字节仅有一个子节点 3、该节点具有两个子节点 * * @param e    要删除的数据 * @param root 根节点 * @return 该节点 */ private BinaryTreeNode delete(E e, BinaryTreeNode root) { /*没有查找到,那么什么都不做*/ if (root == null) { return null; } /*调用比较的方法*/ int i = compare(e, root.data); /*如果大于0，则说明e>root.date 继续查询右子树*/ if (i > 0) { //从新赋值 root.right = delete(e, root.right); /*如果小于0，则说明e root, BinaryTreeNode parent) { //如果节点为null，返回 if (root == null) { return null; /*如果节点的左子节点为null,那么该节点就是最小的节点*/ /*1、该最小节点肯定没有左子节点，因为左子节点比父节点小，但是可能有右子节点*/ /*2、此时该节点可能作为某个节点的左子节点，也可能作为原父节点的右子节点（即右子树是一颗右斜树），这里需要分开讨论*/ } else if (root.left == null) { //如果该节点是父节点的右子节点,说明还没进行递归或者第一次递归就找到了最小节点. //那么此时,应该让该节点的父节点的右子节点指向该节点的右子节点,并返回该节点的数据，该节点由于没有了强引用，会被GC删除 if (root == parent.right) { parent.right = root.right; } else { //如果该节点不是父节点的右子节点，说明进行了多次递归。 //那么此时,应该让该节点的父节点的左子节点指向该节点的右子节点,并返回该节点的数据，该节点由于没有了强引用，会被GC删除 parent.left = root.right; } //返回最小节点的数据 return root.data; } //递归调用,注意此时是往左查找 return findAndDeleteMin(root.left, root); } 

public class BinarySearchTreeTest { BinarySearchTree binarySearchTree = new BinarySearchTree<>(); @Test public void test() { //首先要插入根节点47，然后是第二层的节点16,73，然后是第三层的节点1,24,59,88，然后是第四层的节点20,35,62,77。 // 每一层内部节点的顺序可以不一致，但是每一层之间的打顺序一定要保持一致，否则虽然中序遍历输出的时候能够正常输出,但是树的结构不能保证。 Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77}; binarySearchTree.insert(es); //中序遍历输出 System.out.println(binarySearchTree.toInorderTraversalString()); //查找是否存在 System.out.println(binarySearchTree.contains(1)); System.out.println(binarySearchTree.contains(2)); //移除 binarySearchTree.delete(73); //中序遍历输出 System.out.println(binarySearchTree.toInorderTraversalString()); } }