写在前面
最近一直在专心学习数据结构，刚好看到树这一章。之前大一学习的数据结构是以C语言为基础的，然而当时也没有好好听讲，现在也是比较后悔，通过接下来的这段时间准备好好学习一下树的知识，也通过博客来记录一下对于其中的理解。
概述
先简单介绍一下树以及二叉树的概念。
树的概念
每一棵子树的根都是根root的儿子，而根root是每一棵子树的根的父亲。没有儿子的节点称为树叶。具有相同父亲的节点为兄弟。
在上图中，节点A是根，节点E有一个父亲A并且有一个儿子I，每一个节点可以有多个儿子，因此节点L有儿子M、N、P。没有其中节点B、J、K、M、N、P、I、F都没有儿子，因此它们都是树叶。节点M、N、P拥有共同的父亲，所有它们是兄弟。
对于一棵树而言，某个节点的深度为该节点到根中间连线的数目，因此图中根A的深度为0，节点G的深度为2。某个节点的高为该节点到它所能到达最远的一片树叶的长，所以一棵树所有的树叶的高都是0。一棵树的高等于它的根的高，一棵树的深度等于它的最深的树叶的深度。该深度总是等于这棵树的高。
二叉树的概念
二叉树的每个结点最多有两个子节点，所以我们可以直接它到两个子节点的链。以及它还应该拥有一个element元素用来存储在该节点的数据。
class BinaryTreeNode<T>{
T element;
BinaryTreeNode<T> left; //左孩子
BinaryTreeNode<T> right; //右孩子
}
二叉查找树的概念
上图中只有左边的树是二叉查找树，右边的树不是。右边的树的根节点的值为6，而它的左子树中有一个节点的值为7。
在二叉查找树中我们会使用到一个排序的接口，这个接口就是Comparable。我们将会使用到该接口来进行树中项的比较来确定它们之间的关系。
代码详解
该代码块中将会有以下类和方法：
- 类
BinaryTreeNode，该类用于创建每一个结点。 - 方法
makeEmpty，将树置为空树。 - 方法
isEmpty，判断是否为空树。 - 方法
contains，判断树中是否包含某元素。 - 方法
findMin，查找树中最小值。 - 方法
findMax，查找树中最大值。 - 方法
insert，在树中合适位置插入元素。 - 方法
remove，移除树中某元素。 - 方法
printTree，打印该二叉查找树。
/**
* @author: zhangocean
* @Date: 2018/10/7 12:44
*/
public class BinarySearchTree<T extends Comparable<? super T>> {
private BinaryTreeNode<T> root;
public BinarySearchTree() {
root = null;
}
public void makeEmpty(){
root = null;
}
public boolean isEmpty(){
return root == null;
}
public boolean contains(T element){
return contains(element, root);
}
private boolean contains(T element, BinaryTreeNode<T> root){
//基准条件
if(root == null){
return false;
}
int compareResult = element.compareTo(root.element);
if(compareResult > 0){
return contains(element, root.right);
} else if (compareResult < 0){
return contains(element, root.left);
} else {
return true;
}
}
/**
* 查找树中最小值
*/
public T findMin(){
if(isEmpty()){
try {
throw new Exception("树为空");
} catch (Exception e) {
e.printStackTrace();
}
}
return (T) findMin(root).element;
}
private BinaryTreeNode findMin(BinaryTreeNode root){
if(root == null){
return null;
}else if (root.left == null){
return root;
}
return findMin(root.left);
}
/**
* 查找最大值
*/
public T findMax() throws Exception {
if(isEmpty()){
throw new Exception("树为空");
}
return (T) findMax(root).element;
}
private BinaryTreeNode findMax(BinaryTreeNode root){
if(root == null){
return null;
}else if (root.right == null){
return root;
}
return findMin(root.right);
}
/**
* 插入节点
*/
public void insert(T element){
root = insert(element, root);
}
private BinaryTreeNode<T> insert(T element, BinaryTreeNode<T> root){
if(root == null){
return new BinaryTreeNode<>(element, null, null);
}
int compareResult = element.compareTo(root.element);
if(compareResult > 0){
root.right = insert(element, root.right);
} else if (compareResult < 0){
root.left = insert(element, root.left);
}
return root;
}
/**
* 删除节点
*/
public void remove(T element){
root = remove(element, root);
}
private BinaryTreeNode<T> remove(T element, BinaryTreeNode<T> root){
//未找到需要删除的节点
if(root == null){
return null;
}
int compareResult = element.compareTo(root.element);
if(compareResult > 0){
root.right = remove(element, root.right);
} else if (compareResult < 0){
root.left = remove(element, root.left);
} else if (root.left != null && root.right != null){
//将该节点替换为其右子树中的最小项的值
root.element = (T) findMin(root.right).element;
//移除该右子树中的最小项节点
root.right = remove(root.element, root.right);
} else {
root = root.left != null ? root.left : root.right;
}
return root;
}
/**
* 打印该二叉查找树
*/
public void printTree(){
if(isEmpty()){
System.out.println("空树");
} else {
printTree(root);
System.out.println("");
}
}
private void printTree(BinaryTreeNode<T> root){
if(root != null){
printTree(root.left);
System.out.print(root.element + " ");
printTree(root.right);
}
}
private class BinaryTreeNode<T>{
T element;
BinaryTreeNode<T> left;
BinaryTreeNode<T> right;
public BinaryTreeNode(T element) {
this.element = element;
left = null;
right = null;
}
public BinaryTreeNode(T element, BinaryTreeNode<T> left, BinaryTreeNode<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
}
}
通过调用第二个重载的contains方法，我们可以判断该树中是否有我们需要的元素element。首先我们通过compareTo方法获得需要比较的元素和当前所处位置节点的值的大小，然后通过递归调用搜查子树中的元素。注意使用递归时一定要确认基准条件的设置，不然就会陷入死递归而无法自拔，这里我们的基准条件就是代码27行所示。
在查找最大值以及最小值方法中我们根据二叉查找树的性质，即树中的每个节点X，它的左子树中所有项的值小于X中的值，而它的右子树中所有项的值大于X中的值可以很容易的找出树中的极值。
其中插入节点很简单可以通过代码理解。但是当我们进行节点的删除时会涉及到三种情况：
- 当删除的节点是树叶时，直接删除。
- 当删除的节点有一个儿子时，直接调整该节点的父亲与儿子的链即可删除该节点。
- 当删除的节点有两个儿子时，一般的删除策略是用该节点右子树中的最小的节点的值代替该节点的数据，并将那个最小的节点删除。因为该最小的节点一定没有左孩子，所以很容易remove。具体删除过程可看下图：
下面我们进行测试环节：
public static void main(String[] args) {
Random random = new Random(100);
BinarySearchTree<Integer> tree = new BinarySearchTree<>();
tree.printTree();
for(int i=0;i<10;i++){
tree.insert(random.nextInt(100));
}
tree.printTree();
tree.makeEmpty();
tree.printTree();
}
这里测试我们首先创建一个空树，然后使用随机数往树中添加元素，再清空该树，输出结果如下所示。
空树
13 15 23 36 50 66 74 88 91
空树
总结
我们这里所讲解的二叉查找树，它的时间复杂度为(log N)。因为我们用常数时间在树中降低了一层，这样一来，对其进行操作的树大致减少一半左右的时间。因此，所欲操作的运行时间都是O(d)，其中d是包含所访问的项的节点的深度。至于其他的树我也会在之后的博客中写到。