Java 实现二叉搜索树的查找、插入、删除、遍历

由于最近想要阅读下jdk1.8 中hashmap的具体实现，但是由于hashmap的实现中用到了红黑树，所以我觉得有必要先复习下红黑树的相关知识，所以写下这篇随笔备忘，有不对的地方请指出～

学习红黑树，我觉得有必要从二叉搜索树开始学起，本篇随笔就主要介绍java实现二叉搜索树的查找、插入、删除、遍历等内容。

二叉搜索树需满足以下四个条件：

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

任意节点的左、右子树也分别为二叉查找树；

没有键值相等的节点。

二叉搜索树举例：

图一

接下来将基于图一介绍二叉搜索树相关操作。

首先，应先有一个节点对象相关的类，命名为 node。

class node {
 int key;
 int value;
 node leftchild;
 node rightchild;
 public node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 public void displaynode() {
 }
}

node 类中包含 key 值，用于确定节点在树中相应位置，value 值代表要存储的内容，还含有指向左右孩子节点的两个引用。

接下来看下搜索树相应的类：

class tree {
 node root;//保存树的根
 public node find(int key) {//查找指定节点
 }
 public void insert(int key, int value) {//插入节点
 }
 public boolean delete(int key) {//删除指定节点
 }
 private node getdirectpostnode(node delnode) {//得到待删除节点的直接后继节点
 }
 public void preorder(node rootnode) {//先序遍历树
 }
 public void inorder(node rootnode) {//中序遍历树
 }
 public void postorder(node rootnode) {//后序遍历树
 }
}

类中表示树的框架，包含查找、插入、遍历、删除相应方法，其中删除节点操作最为复杂，接下来一一介绍。

一、查找某个节点

由于二叉搜索树定义上的特殊性，只需根据输入的 key 值从根开始进行比较，若小于根的 key 值，则与根的左子树比较，大于根的key值与根的右子树比较，以此类推，找到则返回相应节点，否则返回 null。

public node find(int key) {
 node currentnode = root;
 while (currentnode != null && currentnode.key != key) {
 if (key < currentnode.key) {
 currentnode = currentnode.leftchild;
 } else {
 currentnode = currentnode.rightchild;
 }
 }
 return currentnode;
}

二、插入节点

与查找操作相似，由于二叉搜索树的特殊性，待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置，在比较的过程中要注意保存父节点的信息 及 待插入的位置是父节点的左子树还是右子树，才能插入到正确的位置。

public void insert(int key, int value) {
 if (root == null) {
 root = new node(key, value);
 return;
 }
 node currentnode = root;
 node parentnode = root;
 boolean isleftchild = true;
 while (currentnode != null) {
 parentnode = currentnode;
 if (key < currentnode.key) {
 currentnode = currentnode.leftchild;
 isleftchild = true;
 } else {
 currentnode = currentnode.rightchild;
 isleftchild = false;
 }
 }
 node newnode = new node(key, value);
 if (isleftchild) {
 parentnode.leftchild = newnode;
 } else {
 parentnode.rightchild = newnode;
 }
}

三、遍历二叉搜索树

遍历操作与遍历普通二叉树操作完全相同，不赘述。

public void preorder(node rootnode) {
 if (rootnode != null) {
 system.out.println(rootnode.key + " " + rootnode.value);
 preorder(rootnode.leftchild);
 preorder(rootnode.rightchild);
 }
 }
public void inorder(node rootnode) {
 if (rootnode != null) {
 inorder(rootnode.leftchild);
 system.out.println(rootnode.key + " " + rootnode.value);
 inorder(rootnode.rightchild);
 }
 }
public void postorder(node rootnode) {
 if (rootnode != null) {
 postorder(rootnode.leftchild);
 postorder(rootnode.rightchild);
 system.out.println(rootnode.key + " " + rootnode.value);
 }
 }

四、删除指定节点。

在二叉搜索树中删除节点操作较复杂，可分为以下三种情况。

1、待删除的节点为叶子节点，可直接删除。

public boolean delete(int key) {
 node currentnode = root;//用来保存待删除节点
 node parentnode = root;//用来保存待删除节点的父亲节点
 boolean isleftchild = true;//用来确定待删除节点是父亲节点的左孩子还是右孩子
 while (currentnode != null && currentnode.key != key) {
 parentnode = currentnode;
 if (key < currentnode.key) {
 currentnode = currentnode.leftchild;
 isleftchild = true;
 } else {
 currentnode = currentnode.rightchild;
 isleftchild = false;
 }
 }
 if (currentnode == null) {
 return false;
 }
 if (currentnode.leftchild == null && currentnode.rightchild == null) {//要删除的节点为叶子节点
 if (currentnode == root)
 root = null;
 else if (isleftchild)
 parentnode.leftchild = null;
 else
 parentnode.rightchild = null;
 } 
 ......
 }

2、待删除节点只有一个孩子节点

例如删除图一中的 key 值为 11 的节点，只需将 key 值为 13 的节点的左孩子指向 key 值为 12的节点即可达到删除 key 值为 11 的节点的目的。

由以上分析可得代码如下（接上述 delete 方法省略号后）：

else if (currentnode.rightchild == null) {//要删除的节点只有左孩子
 if (currentnode == root)
 root = currentnode.leftchild;
 else if (isleftchild)
 parentnode.leftchild = currentnode.leftchild;
 else
 parentnode.rightchild = currentnode.leftchild;
 } else if (currentnode.leftchild == null) {//要删除的节点只有右孩子
 if (currentnode == root)
 root = currentnode.rightchild;
 else if (isleftchild)
 parentnode.leftchild = currentnode.rightchild;
 else
 parentnode.rightchild = currentnode.rightchild;
 } 
 ......

3、待删除节点既有左孩子，又有右孩子。

例如删除图一中 key 值为 10 的节点，这时就需要用 key 值为 10 的节点的中序后继节点（节点 11）来代替 key 值为 10 的节点，并删除 key 值为 10 的节点的中序后继节点，由中序遍历相关规则可知， key 值为 10 的节点的直接中序后继节点一定是其右子树中 key 值最小的节点，所以此中序后继节点一定不含子节点或者只含有一个右孩子，删除此中序后继节点就属于上述 1,2 所述情况。图一中 key 值为 10 的节点的直接中序后继节点 为 11，节点 11 含有一个右孩子 12。

所以删除 图一中 key 值为 10 的节点分为以下几步：

a、找到 key 值为 10 的节点的直接中序后继节点（即其右子树中值最小的节点 11），并删除此直接中序后继节点。

private node getdirectpostnode(node delnode) {//方法作用为得到待删除节点的直接后继节点
 node parentnode = delnode;//用来保存待删除节点的直接后继节点的父亲节点
 node direcrpostnode = delnode;//用来保存待删除节点的直接后继节点
 node currentnode = delnode.rightchild;
 while (currentnode != null) {
 parentnode = direcrpostnode;
 direcrpostnode = currentnode;
 currentnode = currentnode.leftchild;
 }
 if (direcrpostnode != delnode.rightchild) {//从树中删除此直接后继节点
 parentnode.leftchild = direcrpostnode.rightchild;
 direcrpostnode.rightchild = null;
 }
 return direcrpostnode;//返回此直接后继节点
}

b、将此后继节点的 key、value 值赋给待删除节点的 key，value值。(接情况二中省略号代码之后)

else { //要删除的节点既有左孩子又有右孩子
 //思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 node directpostnode = getdirectpostnode(currentnode);
 currentnode.key = directpostnode.key;
 currentnode.value = directpostnode.value;
}

至此删除指定节点的操作结束。

最后给出完整代码及简单测试代码及测试结果：

class node {
 int key;
 int value;
 node leftchild;
 node rightchild;
 public node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 public void displaynode() {
 }
}
class tree {
 node root;
 public node find(int key) {
 node currentnode = root;
 while (currentnode != null && currentnode.key != key) {
 if (key < currentnode.key) {
 currentnode = currentnode.leftchild;
 } else {
 currentnode = currentnode.rightchild;
 }
 }
 return currentnode;
 }
 public void insert(int key, int value) {
 if (root == null) {
 root = new node(key, value);
 return;
 }
 node currentnode = root;
 node parentnode = root;
 boolean isleftchild = true;
 while (currentnode != null) {
 parentnode = currentnode;
 if (key < currentnode.key) {
 currentnode = currentnode.leftchild;
 isleftchild = true;
 } else {
 currentnode = currentnode.rightchild;
 isleftchild = false;
 }
 }
 node newnode = new node(key, value);
 if (isleftchild) {
 parentnode.leftchild = newnode;
 } else {
 parentnode.rightchild = newnode;
 }
 }
 public boolean delete(int key) {
 node currentnode = root;
 node parentnode = root;
 boolean isleftchild = true;
 while (currentnode != null && currentnode.key != key) {
 parentnode = currentnode;
 if (key < currentnode.key) {
 currentnode = currentnode.leftchild;
 isleftchild = true;
 } else {
 currentnode = currentnode.rightchild;
 isleftchild = false;
 }
 }
 if (currentnode == null) {
 return false;
 }
 if (currentnode.leftchild == null && currentnode.rightchild == null) {
 //要删除的节点为叶子节点
 if (currentnode == root)
 root = null;
 else if (isleftchild)
 parentnode.leftchild = null;
 else
 parentnode.rightchild = null;
 } else if (currentnode.rightchild == null) {//要删除的节点只有左孩子
 if (currentnode == root)
 root = currentnode.leftchild;
 else if (isleftchild)
 parentnode.leftchild = currentnode.leftchild;
 else
 parentnode.rightchild = currentnode.leftchild;
 } else if (currentnode.leftchild == null) {//要删除的节点只有右孩子
 if (currentnode == root)
 root = currentnode.rightchild;
 else if (isleftchild)
 parentnode.leftchild = currentnode.rightchild;
 else
 parentnode.rightchild = currentnode.rightchild;
 } else { //要删除的节点既有左孩子又有右孩子
 //思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 node directpostnode = getdirectpostnode(currentnode);
 currentnode.key = directpostnode.key;
 currentnode.value = directpostnode.value;
 }
 return true;
 }
 private node getdirectpostnode(node delnode) {//方法作用为得到待删除节点的直接后继节点
 node parentnode = delnode;//用来保存待删除节点的直接后继节点的父亲节点
 node direcrpostnode = delnode;//用来保存待删除节点的直接后继节点
 node currentnode = delnode.rightchild;
 while (currentnode != null) {
 parentnode = direcrpostnode;
 direcrpostnode = currentnode;
 currentnode = currentnode.leftchild;
 }
 if (direcrpostnode != delnode.rightchild) {//从树中删除此直接后继节点
 parentnode.leftchild = direcrpostnode.rightchild;
 direcrpostnode.rightchild = null;
 }
 return direcrpostnode;//返回此直接后继节点
 }
 public void preorder(node rootnode) {
 if (rootnode != null) {
 system.out.println(rootnode.key + " " + rootnode.value);
 preorder(rootnode.leftchild);
 preorder(rootnode.rightchild);
 }
 }
 public void inorder(node rootnode) {
 if (rootnode != null) {
 inorder(rootnode.leftchild);
 system.out.println("key: " + rootnode.key + " " + "value: " + rootnode.value);
 inorder(rootnode.rightchild);
 }
 }
 public void postorder(node rootnode) {
 if (rootnode != null) {
 postorder(rootnode.leftchild);
 postorder(rootnode.rightchild);
 system.out.println(rootnode.key + " " + rootnode.value);
 }
 }
}
public class binarysearchtreeapp {
 public static void main(string[] args) {
 tree tree = new tree();
 tree.insert(6, 6);//插入操作,构造图一所示的二叉树
 tree.insert(3, 3);
 tree.insert(14, 14);
 tree.insert(16, 16);
 tree.insert(10, 10);
 tree.insert(9, 9);
 tree.insert(13, 13);
 tree.insert(11, 11);
 tree.insert(12, 12);
 system.out.println("删除前遍历结果");
 tree.inorder(tree.root);//中序遍历操作
 system.out.println("删除节点10之后遍历结果");
 tree.delete(10);//删除操作
 tree.inorder(tree.root);
 }
}

测试结果：

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持！