天天看点
返回

数据结构与算法系列——二叉查找树

数据结构与算法系列（1）

    • 1、查找树ADT——二叉查找树
      • 1.1 类的整体定义
      • 1.2 节点定义 BinaryNode
      • 1.2 判断是否存在 contains()
      • 1.3 插入元素 insert()
      • 1.4 删除元素 remove()
      • 1.5 测试代码
      • 1.6 完整代码 BinarySearchTree

1、查找树ADT——二叉查找树

性质：对于二叉查找树中的任意节点X，它的左子树中所有项中的值小于X中的项，而它的右子树中所有项中的值大于X中的项。

平均深度：O(log N)

数据结构与算法系列——二叉查找树

1.1 类的整体定义 

/**
 * @ClssName：BinarySearchTree.java
 * @Description：
 * @createtime：2021/4/9 3:38 下午
 * @author：Joker
 */
public class BinarySearchTree<T extends Comparable<? super T>> {
    public static class BinaryNode<T> {
        // ... ...
    }

    private BinaryNode<T> root;

    public BinarySearchTree() {
        root = null;
    }

    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(T t) {
        // ... ...
    }

    public T findMin() {
        // ... ...
    }

    public T findMax() {
        // ... ...
    }

    public void insert(T t) {
        // ... ...
    }

    public void remove(T t) {
        // ... ...
    }

    public void printTree() {
        // ... ...
    }
}

1.2 节点定义 BinaryNode 

public static class BinaryNode<T> {
    T element;
    BinaryNode<T> left;
    BinaryNode<T> right;

    BinaryNode(T element) {
      this.element = element;
    }

    BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
      this.element = element;
      this.left = left;
      this.right = right;
    }
}

1.2 判断是否存在 contains()

利用递归查找是否包含元素，很简单 
private boolean contains(T t, BinaryNode<T> node) {
  // 边界验证
  if (node == null) {
    return false;
  }

  int compareResult = t.compareTo(node.element);
  if (compareResult > 0) {
    return contains(t, node.right);
  } else if (compareResult < 0) {
    return contains(t, node.left);
  } else {
    return true;
  }
}

1.3 插入元素 insert()

递归遍历，(插入元素比节点值)小了往左，大了往右，直到遇到叶子节点 
public void insert(T t) {
  this.root = insert(t, root);
}

private BinaryNode<T> insert(T t, BinaryNode<T> node) {
  if (node == null) {
    return new BinaryNode<T>(t);
  }

  int compare = t.compareTo(node.element);
  if (compare < 0) {
    node.left = insert(t, node.left);
  } else if (compare > 0) {
    node.right = insert(t, node.right);
  } else {
    // 相同元素，什么都不做
  }

  return node;
}

1.4 删除元素 remove()

  1. 如果删除的节点是树叶，则直接删除即可
  2. 如果删除的节点有一个子节点，则可以操作此节点的父节点的指向此节点的子节点，以达到删除的目的
  3. 如果删除的节点有两个子节点，则从右子树中获取到最小的值，取代需要删除的节点值，然后直接删除右子树最小的值即可。 
public void remove(T t) {
  	this.root = remove(t, root);
}

private BinaryNode<T> remove(T t, BinaryNode<T> node) {
    if (node == null) {
      return node;
    }

    int compareResult = t.compareTo(node.element);
    if (compareResult < 0) {
      node.left = remove(t, node.left);
    } else if (compareResult > 0) {
      node.right = remove(t, node.right);
    } else if (node.left != null && node.right != null) {
      // 当删除的节点存在左右双子树的时候，取其子树最小的元素与其交换，然后删除最小的元素（转换成删除非双子节点）
      node.element = findMin(node.right).element;
      node.right = remove(node.element, node.right);
    } else {
      node = (node.left != null) ? node.left : node.right;
    }

    return node;
}

1.5 测试代码 

public class BinarySearchTreeTest {
    @Test
    public void test() {
        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
        binarySearchTree.insert(6);
        binarySearchTree.insert(2);
        binarySearchTree.insert(5);
        binarySearchTree.insert(7);
        binarySearchTree.insert(9);
        binarySearchTree.insert(1);
        binarySearchTree.insert(3);

        System.out.println("===>" + binarySearchTree.contains(7));
        binarySearchTree.remove(2);
        System.out.println("===>" + binarySearchTree.contains(2));
        System.out.println("===>" + binarySearchTree.contains(1));

    }
}

1.6 完整代码 BinarySearchTree 

package com.tree.adt;
/**
 * @ClssName：BinarySearchTree.java
 * @Description：
 * @createtime：2021/4/9 3:38 下午
 * @author：Joker
 */
public class BinarySearchTree<T extends Comparable<? super T>> {
    public static class BinaryNode<T> {
        T element;
        BinaryNode<T> left;
        BinaryNode<T> right;

        BinaryNode(T element) {
            this.element = element;
        }

        BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }

    private BinaryNode<T> root;

    public BinarySearchTree() {
        root = null;
    }

    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(T t) {
        return contains(t, root);
    }

    public T findMin() {
        if (isEmpty()) {
            return null;
        }

        return findMin(root).element;
    }

    public T findMax() {
        if (isEmpty()) {
            return null;
        }

        return findMax(root).element;
    }

    public void insert(T t) {
        this.root = insert(t, root);
    }

    public void remove(T t) {
        this.root = remove(t, root);
    }

    public void printTree() {
        printTree(root);
    }

    private BinaryNode<T> insert(T t, BinaryNode<T> node) {
        if (node == null) {
            return new BinaryNode<T>(t);
        }

        int compare = t.compareTo(node.element);
        if (compare < 0) {
            node.left = insert(t, node.left);
        } else if (compare > 0) {
            node.right = insert(t, node.right);
        } else {
            // do nothing
        }

        return node;
    }

    /**
     * 查找二叉树的最大值一定在右子树上
     *
     * @param node 初始节点
     * @return
     */
    private BinaryNode<T> findMax(BinaryNode<T> node) {
        if (node == null) {
            return null;
        } else if (node.right == null) {
            return node;
        }

        return findMax(node.right);
    }

    /**
     * 查找二叉树的最小值一定在左子树上
     *
     * @param node 初始节点
     * @return
     */
    private BinaryNode<T> findMin(BinaryNode<T> node) {
        if (node == null) {
            return null;
        } else if (node.left == null) {
            return node;
        }

        return findMax(node.left);
    }

    private void printTree(BinaryNode<T> node) {}

    /**
     * 1. 如果删除的节点是树叶，则直接删除即可
     * 2. 如果删除的节点有一个子节点，则可以操作此节点的父节点的指向此节点的子节点，以达到删除的目的
     * 3. 如果删除的节点有两个子节点，则从右子树中获取到最小的值，取代需要删除的节点值，然后直接删除右子树最小的值即可。
     *
     * @param t
     * @param node
     * @return
     */
    private BinaryNode<T> remove(T t, BinaryNode<T> node) {
        if (node == null) {
            return node;
        }

        int compareResult = t.compareTo(node.element);
        if (compareResult < 0) {
            node.left = remove(t, node.left);
        } else if (compareResult > 0) {
            node.right = remove(t, node.right);
        } else if (node.left != null && node.right != null) {
            // 当删除的节点存在左右双子树的时候，取其子树最小的元素与其交换，然后删除最小的元素（转换成删除非双子节点）
            node.element = findMin(node.right).element;
            node.right = remove(node.element, node.right);
        } else {
            node = (node.left != null) ? node.left : node.right;
        }

        return node;
    }

    /**
     * 使用递归查找是否包含元素，很简单
     *
     * @param t
     * @param node
     * @return
     */
    private boolean contains(T t, BinaryNode<T> node) {
        // 边界验证
        if (node == null) {
            return false;
        }

        int compareResult = t.compareTo(node.element);
        if (compareResult > 0) {
            return contains(t, node.right);
        } else if (compareResult < 0) {
            return contains(t, node.left);
        } else {
            return true;
        }
    }
}
本文根据《数据结构与算法分析：Java语言描述（原书第3版）.[美]Mark Allen Weiss》进行代码编写，如有什么问题，欢迎留言
数据结构-树 算法 数据结构 二叉树 java 平衡二叉树
上一篇: Leetcode-标签为Tree 110. Balanced Binary Tree
下一篇: 数据结构之平衡二叉树（AVL树）

继续阅读