1. 概念
一棵二叉搜索树具有如下特征：
①节点的左子树只包含小于当前节点的数
② 节点的右子树只包含大于当前节点的数
③所有左子树和右子树自身必须也是二叉搜索树
若输出二叉搜索树的中序遍历序列，则这个序列是非递减（非递增）有序的
图1：节点有：A,B,C,D,E,F,G 叶子结点: D,E,F,G 其中结点A又被称为根节点。
结点A,B,C分别都有两个子节点，所以他们的度为2，叶子结点D,E,F,G的度为0。
图2：只是比图1多了一个结点T,他同样也是叶子结点，因为A多了一个子节点，所以A结点的度为3，它就不能被称为二叉树。
2. 性质
- 性质1：非空二叉树中的叶子结点的数量等于双分支结点（度为2的结点）的数量加1
如图1二叉树结构，双分支结点的数量为3，叶子结点有4个，符合性质1。但是图2不符合该性质。
因为它不是二叉树。
- 性质2：二叉树的第i层上最多有2i-1(i>=1)个节点
图1中DEFG处于第三层，23-1=4个结点，记住这是最多这么多个结点。
- 性质3：高度（或深度）为i的二叉树最多有2i-1(i>=1)个节点，也可以认为高度为i的二叉树有2i-1个结点，那么该二叉树为满二叉树
图1二叉树的高度为3，最多有7个结点。因为图1的二叉树有7个结点，那么类似这种二叉树就叫做满二叉树。
- 性质4：给定n个结点，能够成h(n)种不同的二叉树
二分搜索：从根节点到某一叶子节点的路径搜索过程。其时间复杂度为O(log2n)
3. 算法实现
- 节点类型
/**
* 节点类型
*/
static class Entry<T extends Comparable<T>> {
private T data;//数值域
private Entry<T> left;//左孩子域
private Entry<T> right;//右孩子域
public Entry(T data) {
this(data, null, null);
}
public Entry(T data, Entry<T> left, Entry<T> right) {
this.data = data;
this.left = left;
this.right = right;
}
}
以下操作以递归方式实现：
- 插入操作
/**
* 插入
* @param val
*/
public void insert(T val) {
this.root = insert(this.root, val);
}
private Entry<T> insert(Entry<T> root, T val) {
if (root == null) {
return new Entry<>(val);
}
if (root.data.compareTo(val) > 0) {
root.left = insert(root.left, val);
} else if (root.data.compareTo(val) < 0) {
root.right = insert(root.right, val);
}
return root;
}
- 删除操作
/**
* 删除
* @param val
*/
public void remove(T val) {
this.root = remove(this.root, val);
}
/**
* 递归删除的内部操作
*
* @param root 当前节点
* @param val 需要删除的节点值
* @return
*/
private Entry<T> remove(Entry<T> root, T val) {
if (root == null) {
return null;
}
if (root.data.compareTo(val) > 0) {
//当前节点的值比待删节点的值大，则继续在左子树中寻找
root.left = remove(root.left, val);
} else if (root.data.compareTo(val) < 0) {
//当前节点的值比待删节点的值小，则继续在右子树中寻找
root.right = remove(root.right, val);
} else {
//已找到待删除节点root，考虑有两个孩子的情况--》寻找前驱节点
if (root.left != null && root.right != null) {
//标记待删除节点的前驱节点，(左子树最大节点)
Entry<T> pre = root.left;
while (pre.right != null) {
//使pre指向待删节点的前驱节点
pre = pre.right;
}
//用前驱节点的值覆盖待删除节点的值
root.data = pre.data;
//继续递归寻找待删除节点的前驱节点
root.left = remove(root.left, pre.data);
} else {
if (root.left != null) {
return root.left;
} else if (root.right != null) {
return root.right;
} else {
return null;
}
}
}
return root;
}
- 查询操作
/**
* 查询
* @param val
* @return
*/
public boolean query(T val) {
return query(this.root, val);
}
private boolean query(Entry<T> root, T val) {
if (root == null) {
return false;
}
if (root.data.compareTo(val) > 0) {
return query(root.left, val);
} else if (root.data.compareTo(val) < 0) {
return query(root.right, val);
} else {
return true;
}
}
- 前、中、后序遍历
/**
* 以root指向的节点为起始节点进行前序遍历访问 VLR
* @param root
*/
private void preOrder(Entry<T> root) {
if (root != null) {
System.out.print(root.data + " ");//V
preOrder(root.left);//L
preOrder(root.right);//R
}
}
/**
* 以root指向的节点为起始节点进行中序遍历访问 LVR
* @param root
*/
private void inOrder(Entry<T> root) {
if (root == null) {
return;
}
inOrder(root.left);//L
System.out.print(root.data + " ");//V
inOrder(root.right);//R
}
/**
* 以root指向的节点为起始节点进行后序遍历访问 LRV
* @param root
*/
private void postOrder(Entry<T> root) {
if (root == null) {
return;
}
postOrder(root.left);//L
postOrder(root.right);//R
System.out.print(root.data + " ");//V
}
/**
* 递归实现层序遍历
* 一个levelOrder做的是深度遍历，一层一层打印说的是广度遍历，有几层遍历几次
*/
public void levelOrder() {
System.out.print("递归实现层序遍历：");
int l = level();
for (int i = 0; i < l; i++) {
levelOrder(this.root, i);
}
System.out.println();
}