版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/9155e2e9e8c1
前言
如果查找的数据集是有序的线性表，并且是顺序存储的，查找可以用折半查找、插值查找、斐波那契查找算法（详细算法见：有序表查找（折半、插值、斐波那契查找））等实现。但是正是因为他们是顺序的，所以在插入和删除操作中需要耗费大量时间，也就是说这些算法适合静态查找（只有查找操作），不适合动态查找（不仅有查找操作还有插入删除等操作）。而二叉搜索树正适合动态查找。
定义
二叉搜索树又称为二叉排序树，它或者是空树，或者是具有下列性质的二叉树：
- 如果它的左子树不为空，那么左子树的所有节点都小于根节点的值；
- 如果它的右子树不为空，那么右子树的所有节点都大于根节点的；
- 它的左、右子树也分别是二叉搜索树.
二叉树是递归定义的数据结构，其中序遍历是递增的有序序列。
操作
1. 插入
插入节点的过程是：若原二叉查找树为空，则直接插入；否则，若关键字 k 小于根节点关键字，则插入到左子树中，若关键字 k 大于根节点关键字，则插入到右子树中。注意每次插入的节点必是叶节点。
2. 删除
二叉查找树的删除操作是相对复杂一点，它要按 3 种情况来处理：
- 若被删除节点 t 是叶子节点，则直接删除，不会破坏二叉排序树的性质；
- 若节点 t 只有左子树或只有右子树，则让 t 的子树成为 t 父节点的子树，替代 t 的位置；
- 若节点 t 既有左子树，又有右子树，则用 t 的直接前驱或者直接后继代替 t，然后从二叉查找树中删除这个后继，这样就转换成了第一或第二种情况。
3. 查找
查找是从根节点开始，若二叉树非空，将给定值与根节点的关键字比较，若相等，则查找成功；若不等，则当给定值小于根节点关键字时，在根节点的左子树中查找，否则在根节点的右子树中查找。
其查找平均时间复杂度为O(logn)，但是最差情况为插入的节点是有序的，则该二叉搜索树会变成左斜树(或者右斜树或者可以理解为“链表”)，即最差时间复杂度为O(n)，故而查找性能不是严格意义上的O(logn)，不稳定。
Java实现
public class SortedBinaryTree<E> {
private Node<E> root; // 根节点
private int size; // 二叉树元素个数
/**
* 二叉树节点
*/
private static class Node<E> {
E element; // 节点元素
Node<E> lChild; // 左孩子
Node<E> rChild; // 右孩子
public Node(E element) {
this(element, null, null);
}
public Node(E element, Node<E> lChild, Node<E> rChild) {
this.element = element;
this.lChild = lChild;
this.rChild = rChild;
}
}
public SortedBinaryTree(List<E> elements) {
for (E e : elements) {
add(e);
}
}
public SortedBinaryTree(E[] elements) {
for (E e : elements) {
add(e);
}
}
public SortedBinaryTree() {
}
/**
* 判断当前元素是否存在于树中
*
* @param element
* @return
*/
public boolean contains(E element) {
return search(root, element);
}
/**
* 递归搜索,查找当前以curRoot为根节点的树中element存在与否
*
* @param curRoot
* @param element
* @return
*/
@SuppressWarnings("unchecked")
private boolean search(Node<E> curRoot, E element) {
if (curRoot == null)
return false;
Comparable<? super E> e = (Comparable<? super E>) element;
int cmp = e.compareTo(curRoot.element);
if (cmp > 0) {
// 查找的元素大于当前根节点对应的元素,向右走
return search(curRoot.rChild, element);
} else if (cmp < 0) {
// 查找的元素小于当前根节点对应的元素,向左走
return search(curRoot.lChild, element);
} else {
// 查找的元素等于当前根节点对应的元素,返回true
return true;
}
}
/**
* 非递归搜索,查找当前以curRoot为根节点的树中的element是否存在
*
* @param curRoot
* 二叉排序树的根节点
* @param element
* 被搜索的元素
* @param target
* target[0]指向查找路径上最后一个节点: 如果当前查找的元素存在,则target[0]指向该节点
* @return
*/
@SuppressWarnings("unchecked")
private boolean find(Node<E> curRoot, E element, Node<E>[] target) {
if (curRoot == null)
return false;
Node<E> tmp = curRoot;
Comparable<? super E> e = (Comparable<? super E>) element;
while (tmp != null) {
int cmp = e.compareTo(tmp.element);
target[0] = tmp;
if (cmp > 0) {
// 查找的元素大于当前节点对应的元素,向右走
tmp = tmp.rChild;
} else if (cmp < 0) {
// 查找的元素小于当前节点对应的元素,向左走
tmp = tmp.lChild;
} else {
// 查找的元素等于当前根节点对应的元素,返回true
return true;
}
}
return false;
}
/**
* 向二叉排序树中添加元素,如果当前元素已经存在,则添加失败,返回false,如果当前元素不存在,则添加成功,返回true
*
*/
@SuppressWarnings("unchecked")
public boolean add(E element) {
if (root == null) {
root = new Node<E>(element);
size++;
return true;
}
Node<E>[] target = new Node[1];
if (!find(root, element, target)) {
// 当前元素不存在,插入元素
// 此时target节点即为需要插入的节点的父节点
Comparable<? super E> e = (Comparable<? super E>) element;
int cmp = e.compareTo(target[0].element);
Node<E> newNode = new Node<E>(element);
if (cmp > 0) {
// 插入的元素大于target指向的节点元素
target[0].rChild = newNode;
} else {
// 插入的元素小于target指向的节点元素
target[0].lChild = newNode;
}
size++;
return true;
}
return false;
}
/**
* 删除二叉排序树中的元素,如果当前元素不存在,则删除失败,返回false;如果当前元素存在,则删除该元素,重构二叉树,返回true
*
* @param element
* @return
*/
@SuppressWarnings("unchecked")
public boolean remove(E element) {
Node<E>[] target = new Node[1];
if (find(root, element, target)) {
// 被删除的元素存在,则继续执行删除操作
remove(target[0]);
return true;
}
return false;
}
/**
* 释放当前节点
*
* @param node
*/
private void free(Node<E> node) {
node.element = null;
node.lChild = null;
node.rChild = null;
node = null;
}
/**
* 删除二叉排序树中指定的节点
*
* @param node
*/
private void remove(Node<E> node) {
Node<E> tmp;
if (node.lChild == null && node.rChild == null) {
// 当前node为叶子节点,删除当前节点,则node = null;
node = null;
} else if (node.lChild == null && node.rChild != null) {
// 如果被删除的节点左子树为空,则只需要重新连接其右子树
tmp = node;
node = node.rChild;
free(tmp);
} else if (node.lChild != null && node.rChild == null) {
// 如果被删除的节点右子树为空,则只需要重新连接其左子树
tmp = node;
node = node.lChild;
free(tmp);
} else {
// 当前被删除的节点左右子树均存在,不为空
// 找到离当前node节点对应元素且最近的节点target(左子树的最右边节点 或者 右子树最左边节点)
// 将node节点元素替换成target节点的元素,将target节点删除
tmp = node; // tmp是target的父节点
Node<E> target = node.lChild; // 找到左子树最大子树
while (target.rChild != null) { // 在左子树中进行右拐
tmp = target;
target = target.rChild;
}
node.element = target.element; // node.element元素替换为target.element
if (tmp == node) {
// tmp == node 说明没有在左子树中进行右拐,也就是node节点的左孩子没有右孩子,
// 需要重新连接tmp节点左孩子
tmp.lChild = target.lChild;
} else {
// tmp != node, 进行了右拐,那么将重新连接tmp的右子树,将target.lChild赋值给tmp.rChild
tmp.rChild = target.lChild;
}
// 释放节点
free(target);
}
// 删除成功,size--;
size--;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size() == 0;
}
public List<E> preOrderTraverse() {
List<E> list = new ArrayList<E>();
preOrderTraverse(root, list);
return list;
}
private void preOrderTraverse(Node<E> curRoot, List<E> list) {
if (curRoot == null)
return;
E e = curRoot.element;
list.add(e);
preOrderTraverse(curRoot.lChild, list);
preOrderTraverse(curRoot.rChild, list);
}
public List<E> inOrderTraverse() {
List<E> list = new ArrayList<E>();
inOrderTraverse(root, list);
return list;
}
private void inOrderTraverse(Node<E> curRoot, List<E> list) {
if (curRoot == null)
return;
inOrderTraverse(curRoot.lChild, list);
list.add(curRoot.element);
inOrderTraverse(curRoot.rChild, list);
}
public List<E> postOrderTraverse() {
List<E> list = new ArrayList<E>();
postOrderTraverse(root, list);
return list;
}
private void postOrderTraverse(Node<E> curRoot, List<E> list) {
if (curRoot == null)
return;
inOrderTraverse(curRoot.lChild, list);
inOrderTraverse(curRoot.rChild, list);
list.add(curRoot.element);
}
/**
* 返回中序遍历结果
*/
@Override
public String toString() {
return inOrderTraverse().toString();
}
public static void main(String[] args) {
Integer[] elements = new Integer[] { 62, 88, 58, 47, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 48, 50 };
SortedBinaryTree<Integer> tree = new SortedBinaryTree<Integer>(elements);
System.out.println(tree);
System.out.println(tree.contains(93));
System.out.println(tree.size());
System.out.println(tree.remove(47));
System.out.println(tree.preOrderTraverse());
System.out.println(tree.size());
}
}
Github地址
SortedBinaryTree
