数据结构 (一) 数组实现一个简单的 ArrayList
数据结构 (二) 链表实现 LinkedList
数据结构 (三) 用两种方式简单实现栈
数据结构 (四) 栈和队列的简单应用
数据结构 (五) 用两种方式简单实现队列
数据结构 (六) 二分搜索树(Binary Search Tree)(下)
数据结构 (七) 两种方式实现 set
定义
简单来说二分搜索树是具有以下行的二叉树
1. 若任意节点的左子树不空, 则左子树上所有节点的值均小于它的根节点的值;
2. 若任意节点的右子树不空, 则右子树上所有节点的值均大于它的根节点的值;
3. 任意节点的左, 右子树也分别为二叉查找树;
4. 没有键值相等的节点.
二分搜索树
二分搜索树是比较重要的一种数据结构, 应用也比较广泛, 希望大家多学习, 多理解, 多应用.
实现
下边我简单实现了一下二分搜索树, 话不多说, 直接上源码.
- import java.util.Stack;
- public class BST<E extends Comparable<E>> {
- private class Node {
- public E e;
- public Node left, right;
- public Node(E e) {
- this.e = e;
- left = null;
- right = null;
- }
- }
- private Node root;
- private int size;
- public BST() {
- root = null;
- size = 0;
- }
- public int size() {
- return size;
- }
- public boolean isEmpty() {
- return size == 0;
- }
- // 向二分搜索树中添加新的元素 e
- public void add(E e) {
- root = add(root, e);
- }
- // 向以 node 为根的二分搜索树中插入元素 e, 递归算法
- // 返回插入新节点后二分搜索树的根
- private Node add(Node node, E e) {
- if (node == null) {
- size++;
- return new Node(e);
- }
- if (e.compareTo(node.e) <0)
- node.left = add(node.left, e);
- else if (e.compareTo(node.e)> 0)
- node.right = add(node.right, e);
- return node;
- }
- // 看二分搜索树中是否包含元素 e
- public boolean contains(E e) {
- return contains(root, e);
- }
- // 看以 node 为根的二分搜索树中是否包含元素 e, 递归算法
- private boolean contains(Node node, E e) {
- if (node == null)
- return false;
- if (e.compareTo(node.e) == 0)
- return true;
- else if (e.compareTo(node.e) <0)
- return contains(node.left, e);
- else // e.compareTo(node.e)> 0
- return contains(node.right, e);
- }
- // 二分搜索树的前序遍历
- public void preOrder() {
- preOrder(root);
- }
- // 前序遍历以 node 为根的二分搜索树, 递归算法
- private void preOrder(Node node) {
- if (node == null)
- return;
- System.out.println(node.e);
- preOrder(node.left);
- preOrder(node.right);
- }
- // 二分搜索树的中序遍历
- public void inOrder() {
- inOrder(root);
- }
- // 中序遍历以 node 为根的二分搜索树, 递归算法
- private void inOrder(Node node) {
- if (node == null)
- return;
- inOrder(node.left);
- System.out.println(node.e);
- inOrder(node.right);
- }
- // 二分搜索树的后序遍历
- public void postOrder() {
- postOrder(root);
- }
- // 后序遍历以 node 为根的二分搜索树, 递归算法
- private void postOrder(Node node) {
- if (node == null)
- return;
- postOrder(node.left);
- postOrder(node.right);
- System.out.println(node.e);
- }
- private void preOrderNR() {
- Stack<Node> stack = new Stack<>();
- stack.push(root);
- while (!stack.isEmpty()) {
- if (root.left != null)
- stack.push(root.left);
- if (root.right != null)
- stack.push(root.right);
- }
- }
- // 效果和 minimum 是一样的这个是非递归的实现, 那个是递归的实现.
- public E minNum() {
- if (size == 0) {
- throw new IllegalArgumentException("bst is empty");
- }
- Node node = root;
- while (node.left != null) {
- node = node.left;
- }
- return node.e;
- }
- /**
- * 递归的方式实现找到二分搜索树的最小值.
- *
- * @return 返回二分搜索树最小节点的值
- */
- public E mininum() {
- if (size == 0) {
- throw new IllegalArgumentException("bst is empty");
- }
- return mininum(root).e;
- }
- /**
- * 以 node 为节点的二分搜索树的最小节点.
- *
- * @param node
- * @return
- */
- private Node mininum(Node node) {
- if (node.left == null)
- return node;
- return mininum(node.left);
- }
- // 从二分搜索树种删除最小值所在的接点, 并返回最小接点的值.
- public E removeMin() {
- E ret = mininum();
- root = removeMin(root);
- return ret;
- }
- // 删除以 node 为根的二分搜索树的最小节点
- // 返回删除节点后新的二分搜索树的根
- private Node removeMin(Node node) {
- if (node.left == null) {
- Node right = node.right;
- node.right = null;
- size--;
- return right;
- }
- node.left = removeMin(node.left);
- return node;
- }
- public E maxNum(){
- if (size == 0) {
- throw new IllegalArgumentException("bst is empty");
- }
- Node node = root;
- while (node.right != null) {
- node = node.right;
- }
- return node.e;
- }
- public E maxmum() {
- if (size == 0) {
- throw new IllegalArgumentException("bst is empty");
- }
- return maxmum(root).e;
- }
- private Node maxmum(Node node) {
- if (node.right == null)
- return node;
- return maxmum(node.right);
- }
- /**
- * 删除二分搜索树最大值的节点.
- *
- * @return
- */
- public E removeMax() {
- E ret = maxmum();
- removeMax(root);
- return ret;
- }
- private Node removeMax(Node node) {
- if (node.left == null) {
- Node right = node.right;
- node.right = null;
- size--;
- return right;
- }
- node.left = removeMax(node);
- return node;
- }
- /**
- * 从二分搜索树中删除元素为 e 的节点.
- *
- * @param e
- */
- public void remove(E e) {
- root = remove(root, e);
- }
- // 删除以 node 为根的二分搜索树中元素为 e 的节点, 递归算法
- // 返回删除节点后二分搜索树的根
- private Node remove(Node node, E e) {
- if (node == null)
- return null;
- if (e.compareTo(node.e) <0) {
- node.left = remove(node.left, e);
- return node;
- } else if (e.compareTo(node.e)> 0) {
- node.right = remove(node.right, e);
- return node;
- } else {// e == node.e
- if (node.left == null) {
- Node right = node.right;
- node. right = null;
- size--;
- return right;
- }
- if (node.right == null) {
- Node left = node.left;
- node.left = null;
- size--;
- return left;
- }
- Node successor = minimum(node.right);
- successor.right = removeMin(node.right);
- successor.left = node.left;
- node.left = node.right = null;
- return successor;
- }
- }
- @Override
- public String toString() {
- StringBuilder res = new StringBuilder();
- generateString(root, 0, res);
- return res.toString();
- }
- // 生成以 node 为根节点, 深度为 depth 的描述二叉树的字符串
- private void generateString(Node node, int depth, StringBuilder res) {
- if (node == null) {
- res.append(generateDepthString(depth) + "null\n");
- return;
- }
- res.append(generateDepthString(depth) + node.e + "\n");
- generateString(node.left, depth + 1, res);
- generateString(node.right, depth + 1, res);
- }
- private String generateDepthString(int depth) {
- StringBuilder res = new StringBuilder();
- for (int i = 0; i < depth; I++)
- res.append("--");
- return res.toString();
- }
- }
解析
首先大家可以看到我们的泛型与之前的不太一样, 这里必须是可以比较的泛型, 因为二分搜索树是按照大小来排列的, 内部有序. 下边我们一一来介绍他的方法.
Binary Search Tree
add
这里我们用的是递归的实现, 所以我们先来看一下结束的条件, 就是当前的节点是空的时候, 极限情况就是这个二分搜索树是空的, 那么插入一个元素, 只需要把这个节点插入到当前节点上, 并且给 size 加一就可以, 下边就是就是递归的具体条件了, 如果他比当前节点小的话, 那么那么就去他的左子树去处理, 如果比当前节点大的话就去他的右子树去处理, 因为当前出是不存在键值相同的节点, 所以就这样去遍历直到找到合适的位置, 这样就完成了二分搜索树的插入工作. 如上边的图, 我们插入 11, 比根节点小, 去左子树比较, 比 18 这个节点小, 再去他的左子树比较, 比 10 大, 去右子树, 10 这个节点右叶子节点是空的, 所以直接插入到那个位置就可以了.
contains
这里我们也是用的递归的方法实现的, 同样的道理我们也是找一下结束的条件, 当前的节点为空的时候说明走到结束了也没有找到相同的值的节点, 所以返回 false, 下边就是判断如果当前节点与传入的元素相同则返回 true; 如果比当前节点的值小则去左子树去遍历; 如果比当前节点值大则去右子树遍历. 这样查找的方法也结束了.
miniNum
查找最小数, 因为二分搜索树的特点就是左子树肯定比当前节点小, 所以找最小值只需要找左下角的叶子节点就可以了, 所以我们只需要遍历左子树直到左子树的左叶子节点是空的, 就放回这个节点就可以了. 上边的图可以看到, 最左边的是最小值, 就是 10.
maxmum
这个方法跟上边的方法思想是一样的所以这里不做过多的解释了.
minNum
这里是用循环的方式实现的删除最小节点的元素, 就是一直看左子树, 知道左子树为空的时候就是他的最小值.
maxNum
这个方法和上边的方法是一样的, 我们这里也不做过多的解释了.
remove.PNG
removeMin
这里用递归的方式去寻找的, 所以要找结束条件, 就是到最小值了, 所以这个节点左叶子节点为空, 然后我们获取右叶子节点, 保存的临时变量里, 然后把这个节点的右叶子节点置为 null,size 减一, 返回右叶子节点, 如果不是空那么就继续找这个节点的左子树.
removeMax
这个方法的思想和上边的是相同的.
今天我们先分析这些方法, 下次我们分析剩下的那几个方法. 希望大家多多关注与支持.
来源: http://www.jianshu.com/p/356355a18561