Java实现二叉搜索树算法（BST）

一、树 & 二叉树

树是由节点和边构成，储存元素的集合。节点分根节点、父节点和子节点的概念。

如图：树深=4; 5是根节点；同样8与3的关系是父子节点关系。

二叉树binary tree，则加了“二叉”（binary），意思是在树中作区分。每个节点至多有两个子（child）,left child & right child。二叉树在很多例子中使用，比如二叉树表示算术表达式。

如图：1/8是左节点；2/3是右节点；

二、二叉搜索树 BST

顾名思义，二叉树上又加了个搜索的限制。其要求：每个节点比其左子树元素大，比其右子树元素小。

如图：每个节点比它左子树的任意节点大，而且比它右子树的任意节点小

三、BST Java实现

直接上代码，对应代码分享在Github主页

BinarySearchTree.java

package org.algorithm.tree;/** Copyright [] [Jeff Lee]** Licensed under the Apache License, Version 2.0 (the "License");* you may not use this file except in compliance with the License.* You may obtain a copy of the License at** /licenses/LICENSE-2.0** Unless required by applicable law or agreed to in writing, software* distributed under the License is distributed on an "AS IS" BASIS,* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.* See the License for the specific language governing permissions and* limitations under the License.*//*** 二叉搜索树(BST)实现** Created by bysocket on 16/7/7.*/public class BinarySearchTree {/*** 根节点*/public static TreeNode root;public BinarySearchTree() {this.root = null;}/*** 查找*树深(N) O(lgN)*1. 从root节点开始*2. 比当前节点值小,则找其左节点*3. 比当前节点值大,则找其右节点*4. 与当前节点值相等,查找到返回TRUE*5. 查找完毕未找到,* @param key* @return*/public TreeNode search (int key) {TreeNode current = root;while (current != null&& key != current.value) {if (key < current.value )current = current.left;elsecurrent = current.right;}return current;}/*** 插入*1. 从root节点开始*2. 如果root为空,root为插入值*循环:*3. 如果当前节点值大于插入值,找左节点*4. 如果当前节点值小于插入值,找右节点* @param key* @return*/public TreeNode insert (int key) {// 新增节点TreeNode newNode = new TreeNode(key);// 当前节点TreeNode current = root;// 上个节点TreeNode parent = null;// 如果根节点为空if (current == null) {root = newNode;return newNode;}while (true) {parent = current;if (key < current.value) {current = current.left;if (current == null) {parent.left = newNode;return newNode;}} else {current = current.right;if (current == null) {parent.right = newNode;return newNode;}}}}/*** 删除节点*1.找到删除节点*2.如果删除节点左节点为空 , 右节点也为空;*3.如果删除节点只有一个子节点右节点或者左节点*4.如果删除节点左右子节点都不为空* @param key* @return*/public TreeNode delete (int key) {TreeNode parent = root;TreeNode current = root;boolean isLeftChild = false;// 找到删除节点及是否在左子树while (current.value != key) {parent = current;if (current.value > key) {isLeftChild = true;current = current.left;} else {isLeftChild = false;current = current.right;}if (current == null) {return current;}}// 如果删除节点左节点为空 , 右节点也为空if (current.left == null && current.right == null) {if (current == root) {root = null;}// 在左子树if (isLeftChild == true) {parent.left = null;} else {parent.right = null;}}// 如果删除节点只有一个子节点右节点或者左节点else if (current.right == null) {if (current == root) {root = current.left;} else if (isLeftChild) {parent.left = current.left;} else {parent.right = current.left;}}else if (current.left == null) {if (current == root) {root = current.right;} else if (isLeftChild) {parent.left = current.right;} else {parent.right = current.right;}}// 如果删除节点左右子节点都不为空else if (current.left != null && current.right != null) {// 找到删除节点的后继者TreeNode successor = getDeleteSuccessor(current);if (current == root) {root = successor;} else if (isLeftChild) {parent.left = successor;} else {parent.right = successor;}successor.left = current.left;}return current;}/*** 获取删除节点的后继者*删除节点的后继者是在其右节点树种最小的节点* @param deleteNode* @return*/public TreeNode getDeleteSuccessor(TreeNode deleteNode) {// 后继者TreeNode successor = null;TreeNode successorParent = null;TreeNode current = deleteNode.right;while (current != null) {successorParent = successor;successor = current;current = current.left;}// 检查后继者(不可能有左节点树)是否有右节点树// 如果它有右节点树,则替换后继者位置,加到后继者父亲节点的左节点.if (successor != deleteNode.right) {successorParent.left = successor.right;successor.right = deleteNode.right;}return successor;}public void toString(TreeNode root) {if (root != null) {toString(root.left);System.out.print("value = " + root.value + " -> ");toString(root.right);}}}/*** 节点*/class TreeNode {/*** 节点值*/int value;/*** 左节点*/TreeNode left;/*** 右节点*/TreeNode right;public TreeNode(int value) {this.value = value;left = null;right = null;}}

1.节点数据结构

首先定义了节点的数据接口，节点分左节点和右节点及本身节点值。如图

代码如下：

/*** 节点*/class TreeNode {/*** 节点值*/int value;/*** 左节点*/TreeNode left;/*** 右节点*/TreeNode right;public TreeNode(int value) {this.value = value;left = null;right = null;}}

2. 插入

插入，和删除一样会引起二叉搜索树的动态变化。插入相对删处理逻辑相对简单些。如图插入的逻辑：

a. 从root节点开始

b.如果root为空,root为插入值

c.循环:

d.如果当前节点值大于插入值,找左节点

e.如果当前节点值小于插入值,找右节点

代码对应：

/*** 插入*1. 从root节点开始*2. 如果root为空,root为插入值*循环:*3. 如果当前节点值大于插入值,找左节点*4. 如果当前节点值小于插入值,找右节点* @param key* @return*/public TreeNode insert (int key) {// 新增节点TreeNode newNode = new TreeNode(key);// 当前节点TreeNode current = root;// 上个节点TreeNode parent = null;// 如果根节点为空if (current == null) {root = newNode;return newNode;}while (true) {parent = current;if (key < current.value) {current = current.left;if (current == null) {parent.left = newNode;return newNode;}} else {current = current.right;if (current == null) {parent.right = newNode;return newNode;}}}}

3.查找

其算法复杂度 :O(lgN),树深(N)。如图查找逻辑：

a.从root节点开始

b.比当前节点值小,则找其左节点

c.比当前节点值大,则找其右节点

d.与当前节点值相等,查找到返回TRUE

e.查找完毕未找到

代码对应：

/*** 查找*树深(N) O(lgN)*1. 从root节点开始*2. 比当前节点值小,则找其左节点*3. 比当前节点值大,则找其右节点*4. 与当前节点值相等,查找到返回TRUE*5. 查找完毕未找到,* @param key* @return*/public TreeNode search (int key) {TreeNode current = root;while (current != null&& key != current.value) {if (key < current.value )current = current.left;elsecurrent = current.right;}return current;}

4. 删除

首先找到删除节点，其寻找方法：删除节点的后继者是在其右节点树种最小的节点。如图删除对应逻辑：

结果为：

a.找到删除节点

b.如果删除节点左节点为空 , 右节点也为空;

c.如果删除节点只有一个子节点右节点或者左节点

d.如果删除节点左右子节点都不为空

代码对应见上面完整代码。

案例测试代码如下，BinarySearchTreeTest.java

运行结果如下：

value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 8 -> value = 9 -> value = 10 -> value = 20 -> value = 25 -> 是否存在节点值为10 => 10是否存在节点值为11 => null删除节点8 => 8value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 9 -> value = 10 -> value = 20 -> value = 25 ->