Java实现二叉排序树

package glut.bean; import java.util.ArrayList; import java.util.List; public class SortedTree { private List<Number> arr; private Node root; private boolean allowTheSameNumber = false; /** * 不能使用默认构造器 */ private SortedTree() { // TODO Auto-generated constructor stub } /** * 必须给定一个List,且list不能为空 * * @param arr */ public SortedTree(List<Number> arr) { this.arr = arr; if (!arr.isEmpty()) { root = new Node(); root.parent = null; root.leftChild = null; root.rightChild = null; createSortedTree(); } else { try { throw new Exception("Array is empty"); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } } /** * 必须给定一个List,且list不能为空 * * @param arr * @param allowTheSameNumber * 是否允许重复数字(建议false).true:allow ;false: not allow */ public SortedTree(List<Number> arr, boolean allowTheSameNumber) { this.arr = arr; this.allowTheSameNumber = allowTheSameNumber; if (!arr.isEmpty()) { root = new Node(); root.parent = null; root.leftChild = null; root.rightChild = null; createSortedTree(); } else { try { throw new Exception("Array is empty"); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } } /** * 以下参数都是通过createSortedTree方法的for循环获取 * * @param value * @param curNode * @param index */ private void build(Number value, Node curNode, int index) { // 向左转 if (value.doubleValue() < curNode.value.doubleValue()) { // 如果没有左节点,就创建 if (curNode.leftChild == null) { curNode.leftChild = createNewNode(value, curNode, index, true); return; } // 有就继续遍历 build(value, curNode.leftChild, index); // 向右转 } else if (value.doubleValue() > curNode.value.doubleValue()) { // 如果没有右节点,就创建 if (curNode.rightChild == null) { curNode.rightChild = createNewNode(value, curNode, index, false); return; } // 有就继续遍历 build(value, curNode.rightChild, index); // 相同的值 } else { if (!allowTheSameNumber) { try { throw new Exception("has the same number"); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } // 如果允许相同的值,则将它放在右子树 } else { // 如果没有右节点,就创建 if (curNode.rightChild == null) { curNode.rightChild = createNewNode(value, curNode, index, false); return; } // 有就继续遍历 build(value, curNode.rightChild, index); } } } /** * * @param value * @param curNode * 当前节点 * @param index * 下标 * @param isLeftChild * 是否为左节点 * @return 新创建的节点 */ private Node createNewNode(Number value, Node curNode, int index, boolean isLeftChild) { Node newNode = new Node(); newNode.value = value; // 将当前节点作为新建节点的双亲节点 newNode.parent = curNode; newNode.index = index; newNode.isLeftChild = isLeftChild; return newNode; } private void createSortedTree() { // 默认将arr中第一个元素放到根 root.value = arr.get(0); root.index = 0; for (int i = 1; i < arr.size(); i++) { build(arr.get(i), root, i); } } /** * * @param value * 给定的值 * @return 给定的值在arr中的下标 */ public int indexOf(Number value) { Node targetNode = find(value, root); return targetNode == null ? -1 : targetNode.index; } /** * * @param value * 给定的值 * @return 给定的值的节点 */ public Node get(Number value) { return find(value, root); } /** * * @param value查找的值 * @param curNode * 第一个查找的节点(默认为根节点) * @return如果存在指定值的节点,返回.否则返回null */ private Node find(Number value, Node curNode) { if (curNode != null) { if (value.doubleValue() < curNode.value.doubleValue()) { return find(value, curNode.leftChild); } else if (value.doubleValue() > curNode.value.doubleValue()) { return find(value, curNode.rightChild); } else { return curNode; } } else { return null; } } /** * * * @return 排序后的数组(重复的数字只显示一次) */ public List<Number> getSortedArray() { // newArr用于存放升序排列后的数组 List<Number> newArr = new ArrayList<Number>(); midTraversal(root, newArr); return newArr; } // 中序遍历二叉排序树会得到升序的数组 private void midTraversal(Node curNode, List<Number> newArr) { // TODO Auto-generated method stub // 如果没有左子树,意味着遍历到头了 if (curNode.leftChild == null) { // 直接把该店的值添加到数组里 newArr.add(curNode.value); // 如果有左子树,继续遍历 } else { midTraversal(curNode.leftChild, newArr); // 并且在遍历完后将该节点的值添加到数组里 newArr.add(curNode.value); } // 最后遍历右子树 if (curNode.rightChild != null) { midTraversal(curNode.rightChild, newArr); } } /** * * @param value * 要添加的值 */ public void insert(Number value) { // 先将值添加到list里 arr.add(value); // 进行插入操作 build(value, root, arr.size() - 1); } /** * 删除给定的值的第一次出现的节点 * * @param value * 要删除的值 */ public void delete(Number value) { // 先看看有没有这个节点 Node targetNode = find(value, root); // 如果没有这个节点,抛出找不到的异常 if (targetNode == null) { try { throw new Exception("specified value not found"); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } // 如果有这个节点 // 当该节点拥有2个子节点 if (targetNode.leftChild != null && targetNode.rightChild != null) { // 可以从目标节点的左子树中找到最大的值,来替换目标节点(也可以通过右子数) // maxNodeOfLeft: the max value node of the left tree of the target Node maxNodeOfLeft = findLeftMaxNode(targetNode); // 将左子树中最大的节点的值和下标放到目标节点中 targetNode.value = maxNodeOfLeft.value; targetNode.index = maxNodeOfLeft.index; // leftChildOfMaxNode:the left child of the max node Node leftChildOfMaxNode = maxNodeOfLeft.leftChild; Node parent = maxNodeOfLeft.parent; if (leftChildOfMaxNode != null) { // 进行节点连接操作 leftChildOfMaxNode.parent = parent; connected(maxNodeOfLeft, leftChildOfMaxNode, parent); } else { // 进行节点连接操作 connected(maxNodeOfLeft, null, parent); } maxNodeOfLeft = null; // 如果无子节点 } else if (targetNode.leftChild == null && targetNode.rightChild == null) { // 进行节点连接操作 Node parent = targetNode.parent; connected(targetNode, null, parent); targetNode = null; // 如果只有一个子节点 } else { Node targetNodeLeftChild = targetNode.leftChild; Node parent = targetNode.parent; // 如果目标节点没有左子树 if (targetNodeLeftChild == null) { // 那它肯定有右子树 Node targetNodeRightChild = targetNode.rightChild; // 进行节点连接操作 targetNodeRightChild.parent = parent; connected(targetNode, targetNodeRightChild, parent); } else { // 进行节点连接操作 targetNodeLeftChild.parent = parent;