常见的数据结构与算法，Java语言实现.zip

package com.sinjinsong.datastructure.tree; import java.util.*; /** * Java实现二叉查找树 使用递归的操作一般设置两个方法，一个方法是public的（用于调用的），一个方法是private（实际递归的） * * @author New Song */ public class BinarySearchTree<E extends Comparable<E>> implements Cloneable { private TreeNode<E> root; // 用于使用先序遍历字符串建树 // 用于输出从根节点到各个叶子结点的所有路径 private static int index = -1; public BinarySearchTree() { } public BinarySearchTree(TreeNode<E> root) { this.root = root; } // 在node结点下创建子树，node初始值为root，在查找过程中变为root的子节点 // 如果root为空，那么root的值为data // 否则就向下查找，直至找到合适的位置，创建新结点，赋值为data // 不存在node的值等于data的情况，如果相等就没有插入的必要了 public void createCharBiTree(TreeNode<E> node, E data) { if (root == null) { root = new TreeNode<E>(data); } else { if (data.compareTo(node.val) < 0) { if (node.left == null) { node.left = new TreeNode<E>(data); } else { createCharBiTree(node.left, data); } } else { if (node.right == null) { node.right = new TreeNode<E>(data); } else { createCharBiTree(node.right, data); } } } } // 插入一个结点 public void insert(E data) { root = insert(root, data); // 注意结果要赋值，否则在调完第二个insert方法后node就回收了，没有把结果赋给root // 调用的时候将一个null赋给了node，即使node后来不为null了也没法把引用重新赋给root } // 也是需要递归进行查找的，递归地找到合适位置后插入，不允许有重复元素 private TreeNode<E> insert(TreeNode<E> node, E data) { if (node == null) { node = new TreeNode<>(data); } else { if (data.compareTo(node.val) < 0) { node.left = insert(node.left, data); } else if (data.compareTo(node.val) > 0) { node.right = insert(node.right, data); } } return node; } public TreeNode<E> search(E data) { return search(root, data); } // 查找一个结点，使用递归 // 如果data即为当前结点的值，则返回当前结点 // 如果data小于当前结点，那么递归查找当前结点的左子树 // 否则，递归查找当前结点的右子树 private TreeNode<E> search(TreeNode<E> node, E data) { if (node == null) { return null; } int res = data.compareTo(node.val); if (res > 0) { return search(node.right, data); } else if (res < 0) { return search(node.left, data); } else { return node; } } // 删除一个结点 public void delete(E data) { root = delete(root, data); } private TreeNode<E> delete(TreeNode<E> node, E data) { if (node == null) { return null; } int res = data.compareTo(node.val); if (res > 0) { node.right = delete(node.right, data); } else if (res < 0) { node.left = delete(node.left, data); // 删除一个结点不仅包括将自己赋为null，而且其父节点也要将其左子树/右子树赋为null // 以下为找到的情况 // 如果找到的结点既没有左子树又没有右子树，那么直接设为null // 如果只有左子树或只有右子树，那么将当前结点赋值为不为空的那一个子树 // 如果都有，那么找到当前结点的右子树中值最小的那个结点，删除它（因为它一定没有左子树，所以采用第二种删除策略即可） // 然后将当前结点赋值为最小值 } else if (node.left != null && node.right != null) { // 进行一次删除，删除的是以node的右子树为根节点，值为min的这个结点 // 包含了结点只有左子树或右子树或都没有的情况 node.val = findMin(node.right).val; node.right = delete(node.right, node.val); } else { node = node.left == null ? node.right : node.left; } return node; } // 返回当前子树中的值最小的那个结点 private TreeNode<E> findMin(TreeNode<E> node) { if (node == null) { return null; } while (node.left != null) { node = node.left; } return node; } private TreeNode<E> findMax(TreeNode<E> node) { if (node == null) { return null; } while (node.right != null) { node = node.right; } return node; } public boolean isEmpty() { return root == null; } // 后序遍历二叉树的深度 public int depth() { return depth(root); } private int depth(TreeNode<E> curr) { if (curr == null) { return 0; // 空树深度为0，递归结束，开始返回 } else { // 这种情况实际上包含了两种情况：一种是叶子结点，此时返回的是1；另一种是非叶子结点，返回的是较深子树的深度+1 // 综合起来就是每遇到叶子结点，深度就加1，得到子树的深度，最后加上根节点的深度1 int leftDepth = depth(curr.left); int rightDepth = depth(curr.right); return leftDepth > rightDepth ? (leftDepth + 1) : (rightDepth + 1); } } /** * 非递归求深度，采用层序遍历的方式 * * @return */ public int depthNoRec() { TreeNode<E> curr; Deque<TreeNode<E>> queue = new ArrayDeque<>(); queue.add(root); int depth = 0; while (!queue.isEmpty()) { int levelSize = queue.size(); // 一层进行遍历,queue的长度即为该层节点个数 for (int i = 0; i < levelSize; i++) { curr = queue.poll(); if (curr.left != null) { queue.add(curr.left); } if (curr.right != null) { queue.add(curr.right); } } depth++; } return depth; } // 二叉树的结点个数 public int size() { return size(root); } private int size(TreeNode<E> subTree) { if (subTree == null) { return 0; } else { int leftSubTreeSize = size(subTree.left); int rightSubTreeSize = size(subTree.right); return leftSubTreeSize + rightSubTreeSize + 1; } } public int sizeOfLevel(int k) { return sizeOfLevel(root, k); } /** * 第k层节点个数就是第k-1层的孩子数 * k==0时，返回1 * * @param curr * @param k * @return */ private int sizeOfLevel(TreeNode<E> curr, int k) { if (curr == null) { throw new NullPointerException(); } if (k < 0) { throw new IllegalArgumentException(); } if (k == 0) { return 1; } else { return sizeOfLevel(curr.left, k - 1) + sizeOfLevel(curr.right, k - 1); } } public TreeNode<E> parent(TreeNode<E> curr) { if (curr == null) { return null; } return parent(root, curr); } /** * 先序遍历 * * @param root * @param curr * @r