二叉查找树是一种应用十分广泛的数据结构，它在算法中应用十分广泛，二叉查找树支持多种动态集合的操作，这些操作主要包括：
1、查找某个特定值：
2、二叉查找树中最小值：
3、二叉查找树中最大值：
4、某个节点的前驱：
5、某个节点的后继：
6、插入特定值：
7、删除特定值：
一般情况下，我们为了保持查找和删除情况的唯一性，假设二叉查找树中各个元素的key值不想等。
下面一一剖析二叉查找树的结构与方法：
1、二叉查找树的数据结构：
// 构造二叉查找数的内部类,这就相当于C语言中的结构体
private class TreeNode {
private int key;
private TreeNode lchild; // 定义二叉查找树的左孩子节点
private TreeNode rchild;// 定义二叉查找树的右孩子节点
private TreeNode parent;// 定义二叉查找树的父亲节点
public TreeNode(int key, TreeNode lchild, TreeNode rchild,
TreeNode parent) {
this.key = key;
this.lchild = lchild;
this.rchild = rchild;
this.parent = parent;
}
public int getKey() {
return key;
}
}
public void treeInsert(int key) {// 实现二叉查找数的插入操作
TreeNode parentNode = null;
TreeNode newNode = new TreeNode(key, null, null, null);
TreeNode tmpNode = root;
if (root == null) {
root = newNode;
return;
}
while (tmpNode != null) { // 一般情况下，我们不会插入树中已经存在的节点
parentNode = tmpNode;// 只是作为一个中间变量的节点
if (key < tmpNode.key)
tmpNode = tmpNode.lchild;
else if (key > tmpNode.key)
tmpNode = tmpNode.rchild;
else
return;
}
if (key < parentNode.key) {
parentNode.lchild = newNode;
newNode.parent = parentNode;
} else {
parentNode.rchild = newNode;
newNode.parent = parentNode;
}
}
3、二叉查找树的删除操作：
public void treeDelete(int key) {
TreeNode tmpNode = treeSearch(key);
if (tmpNode == null)
System.out.println("此树中没有你要删除的节点!");
delete(tmpNode); // 删除某一节点
}
public void delete(TreeNode node) { // 删除节点的关键的核心函数
if (node == null)
return;
if (node.lchild == null && node.rchild == null) {// 如果被删除节点左右节点均为空
TreeNode parentNode = node.parent;
if (node == parentNode.lchild)
parentNode.lchild = null;
else
parentNode.rchild = null;
return;
}
if (node.lchild != null && node.rchild == null) {// 左孩子不为空，右孩子为空
TreeNode parentNode = node.parent;
if (node == parentNode.lchild) {
parentNode.lchild = node.lchild;
node.lchild.parent = parentNode;
} else {
parentNode.rchild = node.lchild;
node.lchild.parent = parentNode;
}
return;
}
if (node.lchild == null && node.rchild != null) {// 左孩子为空，右孩子不为空
TreeNode parentNode = node.parent;
if (node == parentNode.lchild) {
parentNode.lchild = node.rchild;
node.rchild.parent = parentNode;
} else {
parentNode.rchild = node.rchild;
node.rchild.parent = parentNode;
}
return;
}
// 该节点的左右孩子均非为空
TreeNode tmpNode = treeSuccessor(node);
node.key = tmpNode.key;
delete(tmpNode);
}
4、求二叉查找树中最小元素的函数：
public TreeNode treeMinNode(TreeNode node) { // 获取此树中最小元素的节点
if (node == null) {
System.out.println("此树为空!");
return null;
}
TreeNode tmpNode = node;
while (tmpNode.lchild != null)
tmpNode = tmpNode.lchild;
return tmpNode;
}
5、求二叉查找树中最大元素的函数：
public TreeNode treeMaxNode(TreeNode node) { // 获取此树中最大元素的节点
if (node == null) {
System.out.println("此树为空!");
return null;
}
TreeNode tmpNode = node;
while (tmpNode.rchild != null)
tmpNode = tmpNode.rchild;
return tmpNode;
}
6、求二叉查找树的前驱节点：
public TreeNode treePrevious(TreeNode node) {// 找出中序条件下某节点的前续节点
if (node == null)
return null;
if (node == treeMinNode(root))// 此时有一种特殊情况，就是节点是最小元素的节点，则没有前续节点
return null;
if (node.lchild != null)
return treeMaxNode(node.lchild);
else {
TreeNode parentNode = node.parent;
while (parentNode != null && node == parentNode.lchild) {
node = parentNode;
parentNode = parentNode.parent;
}
return parentNode;
}
}
7、求二叉查找树的后继节点：
public TreeNode treeSuccessor(TreeNode node) {// 找出中序条件下某节点的后续节点
if (node == null)
return null;
if (node == treeMaxNode(root))// 此时有一种特殊情况，就是节点是最大元素的节点，则没有后续节点
return null;
if (node.rchild != null) // 当此节点右子树不为空
return treeMinNode(node.rchild);
else {// 当此节点右子树为空
TreeNode parentNode = node.parent;
while (parentNode != null && node == parentNode.rchild) {
node = parentNode;
parentNode = parentNode.parent;
}
return parentNode;
}
}
8、中序遍历此二叉查找树：
public void inOrderTranvers(TreeNode node) { // 这是二叉查找树的中序遍历
if (node != null) {
inOrderTranvers(node.lchild);
nodelist.add(node);
inOrderTranvers(node.rchild);
}
}
public List<TreeNode> inOrderTree() { // 获取二叉查找树中序遍历的节点，存在nodelist中
if (nodelist != null)
nodelist.clear();
inOrderTranvers(root);
return nodelist;
}
9、打印出此二叉查找树：
public String printTree() { // 打印出此二叉查找树
List<TreeNode> ll = inOrderTree();
Iterator<TreeNode> it = ll.iterator();
StringBuilder sb = new StringBuilder();
while (it.hasNext()) {
TreeNode p = (TreeNode) it.next();
sb.append(p.key + " ");
}
return sb.toString();
}
下面贴出完整源码：
package binaryTree;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/*
* 实现一个二叉查找数，实现插入、删除、查找等操作
*/
public class BinarySearchTree {
private TreeNode root = null;// 定义树的根节点
private List<TreeNode> nodelist = new ArrayList<TreeNode>();// 遍历链表节点
// 构造二叉查找数的内部类,这就相当于C语言中的结构体
private class TreeNode {
private int key;
private TreeNode lchild; // 定义二叉查找树的左孩子节点
private TreeNode rchild;// 定义二叉查找树的右孩子节点
private TreeNode parent;// 定义二叉查找树的父亲节点
public TreeNode(int key, TreeNode lchild, TreeNode rchild,
TreeNode parent) {
this.key = key;
this.lchild = lchild;
this.rchild = rchild;
this.parent = parent;
}
public int getKey() {
return key;
}
}
public boolean isEmpty() { // 判断此二叉查找树是否为空
return root == null;
}
public void treeInsert(int key) {// 实现二叉查找数的插入操作
TreeNode parentNode = null;
TreeNode newNode = new TreeNode(key, null, null, null);
TreeNode tmpNode = root;
if (root == null) {
root = newNode;
return;
}
while (tmpNode != null) { // 一般情况下，我们不会插入树中已经存在的节点
parentNode = tmpNode;// 只是作为一个中间变量的节点
if (key < tmpNode.key)
tmpNode = tmpNode.lchild;
else if (key > tmpNode.key)
tmpNode = tmpNode.rchild;
else
return;
}
if (key < parentNode.key) {
parentNode.lchild = newNode;
newNode.parent = parentNode;
} else {
parentNode.rchild = newNode;
newNode.parent = parentNode;
}
}
public TreeNode treeSearch(int key) { // 实现二叉查找树的查找操作
TreeNode tmpNode = root;
while (tmpNode != null && tmpNode.key != key) {
if (key < tmpNode.key)
tmpNode = tmpNode.lchild;
else
tmpNode = tmpNode.rchild;
}
return tmpNode;
}
public TreeNode treeMinNode(TreeNode node) { // 获取此树中最小元素的节点
if (node == null) {
System.out.println("此树为空!");
return null;
}
TreeNode tmpNode = node;
while (tmpNode.lchild != null)
tmpNode = tmpNode.lchild;
return tmpNode;
}
public TreeNode treeMaxNode(TreeNode node) { // 获取此树中最大元素的节点
if (node == null) {
System.out.println("此树为空!");
return null;
}
TreeNode tmpNode = node;
while (tmpNode.rchild != null)
tmpNode = tmpNode.rchild;
return tmpNode;
}
public TreeNode treeSuccessor(TreeNode node) {// 找出中序条件下某节点的后续节点
if (node == null)
return null;
if (node == treeMaxNode(root))// 此时有一种特殊情况，就是节点是最大元素的节点，则没有后续节点
return null;
if (node.rchild != null) // 当此节点右子树不为空
return treeMinNode(node.rchild);
else {// 当此节点右子树为空
TreeNode parentNode = node.parent;
while (parentNode != null && node == parentNode.rchild) {
node = parentNode;
parentNode = parentNode.parent;
}
return parentNode;
}
}
public TreeNode treePrevious(TreeNode node) {// 找出中序条件下某节点的前续节点
if (node == null)
return null;
if (node == treeMinNode(root))// 此时有一种特殊情况，就是节点是最小元素的节点，则没有前续节点
return null;
if (node.lchild != null)
return treeMaxNode(node.lchild);
else {
TreeNode parentNode = node.parent;
while (parentNode != null && node == parentNode.lchild) {
node = parentNode;
parentNode = parentNode.parent;
}
return parentNode;
}
}
public void inOrderTranvers(TreeNode node) { // 这是二叉查找树的中序遍历
if (node != null) {
inOrderTranvers(node.lchild);
nodelist.add(node);
inOrderTranvers(node.rchild);
}
}
public List<TreeNode> inOrderTree() { // 获取二叉查找树中序遍历的节点，存在nodelist中
if (nodelist != null)
nodelist.clear();
inOrderTranvers(root);
return nodelist;
}
public void treeDelete(int key) {
TreeNode tmpNode = treeSearch(key);
if (tmpNode == null)
System.out.println("此树中没有你要删除的节点!");
delete(tmpNode); // 删除某一节点
}
public void delete(TreeNode node) { // 删除节点的关键的核心函数
if (node == null)
return;
if (node.lchild == null && node.rchild == null) {// 如果被删除节点左右节点均为空
TreeNode parentNode = node.parent;
if (node == parentNode.lchild)
parentNode.lchild = null;
else
parentNode.rchild = null;
return;
}
if (node.lchild != null && node.rchild == null) {// 左孩子不为空，右孩子为空
TreeNode parentNode = node.parent;
if (node == parentNode.lchild) {
parentNode.lchild = node.lchild;
node.lchild.parent = parentNode;
} else {
parentNode.rchild = node.lchild;
node.lchild.parent = parentNode;
}
return;
}
if (node.lchild == null && node.rchild != null) {// 左孩子为空，右孩子不为空
TreeNode parentNode = node.parent;
if (node == parentNode.lchild) {
parentNode.lchild = node.rchild;
node.rchild.parent = parentNode;
} else {
parentNode.rchild = node.rchild;
node.rchild.parent = parentNode;
}
return;
}
// 该节点的左右孩子均非为空
TreeNode tmpNode = treeSuccessor(node);
node.key = tmpNode.key;
delete(tmpNode);
}
public TreeNode getRoot() {// 获取根节点
return root;
}
public String printTree() { // 打印出此二叉查找树
List<TreeNode> ll = inOrderTree();
Iterator<TreeNode> it = ll.iterator();
StringBuilder sb = new StringBuilder();
while (it.hasNext()) {
TreeNode p = (TreeNode) it.next();
sb.append(p.key + " ");
}
return sb.toString();
}
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
System.out.println("此二叉查找树是否为空:" + bst.isEmpty());
int[] keys = new int[] { 15, 6, 18, 3, 7, 13, 20, 2, 9, 4 };
for (int key : keys)
bst.treeInsert(key);
System.out.println("此二叉查找树是否为空:" + bst.isEmpty());
System.out.println("此二叉查找树中最小元素为:"
+ bst.treeMinNode(bst.getRoot()).getKey());
System.out.println("此二叉查找树中最大元素为:"
+ bst.treeMaxNode(bst.getRoot()).getKey());
System.out.println("此二叉查找树根节点元素为:" + bst.getRoot().getKey());
System.out.println("此二叉查找树为:" + bst.printTree());
System.out.println("查找9是否在二叉查找树中:"
+ ((bst.treeSearch(9) != null) ? "在" : "不在"));
bst.treeDelete(9);
System.out.println("查找9是否在二叉查找树中:"
+ ((bst.treeSearch(9) != null) ? "在" : "不在"));
System.out.println("此二叉查找树为:" + bst.printTree());
System.out.println("查找13是否在二叉查找树中:"
+ ((bst.treeSearch(13) != null) ? "在" : "不在"));
}
}
下面是运行截图：