一、二叉查找树（BTS）
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
定义:
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。
查找
步骤：若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。
查找复杂
1、定义节点
class Node {
//节点值
int val;
//左子节点引用
Node leftChild;
//右子节点引用
Node rightChild;
}
2、插入
首先执行查找算法，找出被插结点的父亲结点。
判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
若二叉树为空。则首先单独生成根结点。
private Node root;
public void insert(int data) {
Node newNode = new Node();
newNode.val = data;
if(root == null) {
//如果是第一个节点，也就是根节点为null,直接创建一个新的节点即可
root = newNode;
} else {
Node current = root;
//current节点的父节点
Node parent;
//循环查找插入的位置
while(true) {
parent = current;
//如果插入的值小于当前节点的值，从左子树查找
if(data < current.val) {
current = current.leftChild;
//直到当前节点为null
if(current == null) {
//设置当前节点的父节点的左子节点为新创建的节点
parent.leftChild = newNode;
return;
}
}
//如果插入的值大于当前节点的值，从左子树查找
else if (data > current.val) {
current = current.rightChild;
//直到当前节点为null
if(current == null) {
//设置当前节点的父节点的右子节点为新创建的节点
parent.rightChild = newNode;
return;
}
} else {
// 相等
return;
}
}// end of while(true)
}
}
3、查找
public Node find(int value) {
Node current = root;
while(current.val != value) {
if(value < current.val) {
current = current.leftChild;
} else {
current = current.rightChild;
}
if(current == null) {
return null;
}
}
return current;
}
4、删除
public boolean delete(int value) {
Node current = root;
Node parent = root;
boolean isLeft = false;
boolean isRight = false;
//查找所要删除的节点的左子节点还是右子节点
while(current.val != value) {
parent = current;
isLeft = false;
isRight = false;
if(value < current.val) {
current = current.leftChild;
isLeft = true;
}
else {
current = current.rightChild;
isRight = true;
}
}
//不存在该值
if(current == null) {
return false;
}
//是叶子节点，不存在子节点
if((current.leftChild == null)
&& (current.rightChild == null)) {
System.out.println("是叶子节点，不存在子节点");
if(isLeft) {
//如果是左子节点，设父节点的左子节点为null
parent.leftChild = null;
}
else if(isRight) {
//如果是右子节点，设父节点的右子节点为null
parent.rightChild = null;
}
return true;
}
//存在左子节点
else if((current.leftChild != null)
&& (current.rightChild == null)) {
System.out.println("不是叶子节点，存在左子节点");
if(isLeft) {
parent.leftChild = current.leftChild;
}
else if(isRight) {
parent.rightChild = current.leftChild;
}
current = null;
return true;
}
//存在右子节点
else if((current.leftChild == null)
&& (current.rightChild != null)) {
System.out.println("不是叶子节点，存在右子节点");
if(isLeft) {
parent.leftChild = current.rightChild;
}
else if(isRight) {
parent.rightChild = current.rightChild;
}
current = null;
return true;
}
//左右子节点都存在
else {
System.out.println("不是叶子节点，存在左右子节点");
if(isLeft) {
parent.leftChild = current.rightChild;
Node currentLeft = current.rightChild;
Node parentLeft = currentLeft;
while(currentLeft != null) {
parentLeft = currentLeft;
currentLeft = currentLeft.leftChild;
}
parentLeft.leftChild = current.leftChild;
current = null;
}
else if(isRight) {
parent.rightChild = current.rightChild;
Node currentLeft = current.rightChild;
Node parentLeft = currentLeft;
while(currentLeft != null) {
parentLeft = currentLeft;
currentLeft = currentLeft.leftChild;
}
parentLeft.leftChild = current.leftChild;
current = null;
}
return true;
}
}
5、打印
public void printTree(Node head) {
System.out.println("-----------------\r\nBinary Tree:");
printInOrder(head, 0, "Root-", 8);
System.out.println();
}
public void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.rightChild, height + 1, "R-", len);
String val = to + head.val;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val;// + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.leftChild, height + 1, "L-", len);
}
public String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
存在的问题
二叉搜索树插入时是按照一定规则进行插入的，因此在中序遍历时获得的数据是有序的，比如下面查找35，只需要比较３次就可以获得结果，因此插入或者查找的效率还是比较高的。
但是存在的一个问题是，如果插入的数据是单调变化的，那就变成了线性链表，最后导致查找效率降低。
因此，也就出现了其他更好的二叉树数据结构，比如红黑树，红黑树是一种平衡的二叉树。
