1. 是什么?
数组和链表在增删改查数据时,都有各自的缺点,比如数组要在中间插入数据,就要让后面的数据整体都移动,而链表检索数据很慢。之前说二叉树时,说到树这种结构就是就是为了弥补数组和链表的缺点而诞生的,二叉排序树(Binary search tree,简称BST),更是体现了这一点。二叉排序树有以下特点:
2. 构建过程:
假如现有数列:7,3,10,12,5,1,9
,构建二叉排序树的过程如下:
二叉排序树
3. 二叉排序树的删除:
二叉排序树的删除有三种情况,如下:
(1):删除的是叶子节点:比如上面这棵二叉排序树中的1,5,9,12:
(2):删除的是只有一棵子树的节点:假如上面这棵二叉排序树节点1右边再挂个2,那么1就是只有一棵子树:
(3):删除的是有两棵子树的节点:比如上面这棵二叉排序树中的7,3,10:
4. 代码实现:
按照上面的思路,用代码实现二叉排序树的构建和删除功能:
public class BinarySearchTree {
/** 根节点 */
private Node root;
/**
* 添加节点
* @param value
*/
public void add(int value){
if (root == null){
root = new Node(value);
} else {
root.add(new Node(value));
}
}
/**
* 查找值为value的节点
* @param value
* @return
*/
public Node findNode(int value){
if (root == null){
return null;
} else {
return root.findNode(value);
}
}
/**
* 查找值为value的节点的父节点
* @param value
* @return
*/
public Node findParentNode(int value){
if (root == null){
return null;
} else {
return root.findParentNode(value);
}
}
/**
* 删除值为value的节点
* @param value
*/
public void deleteNode(int value){
if (root == null){
return;
}
// 找到要删除的节点和要删除节点的父节点
Node targetNode = findNode(value);
Node parentNode = findParentNode(value);
if (targetNode == null){
return;
}
if (targetNode.left == null && targetNode.right == null){
// 要删除的是叶子节点
deleteLeafNode(targetNode, parentNode);
} else if(targetNode.left != null && targetNode.right != null){
// 要删除的是有两棵子树的节点
deleteDoubleSonNode(targetNode);
} else {
// 要删除的是只有一棵子树的节点
deleteSingleSonNode(targetNode, parentNode);
}
}
/**
* 要删除的节点是叶子节点
* @param targetNode
* @param parentNode
*/
private void deleteLeafNode(Node targetNode, Node parentNode){
if (parentNode == null){
// parentNode为空,说明整棵二叉树只有一个节点,直接置空root即可
root = null;
} else {
// parentNode不为空,那就看targetNode是parentNode的左孩子还是右孩子
if (parentNode.left != null && parentNode.left.value == targetNode.value){
parentNode.left = null;
} else {
parentNode.right = null;
}
}
}
/**
* 要删除的是有两棵子树的节点
* @param targetNode
*/
private void deleteDoubleSonNode(Node targetNode){
// 从targetNode的右子树找到值最小的节点
Node rightMinNode = findMinNode(targetNode.right);
// 删除找到的最小的节点,此时的rightMinNode一定是叶子节点
deleteNode(rightMinNode.value);
// 将rightMinNode的值赋给targetNode
targetNode.value = rightMinNode.value;
}
/**
* 要删除的是只有一棵子树的节点
* @param targetNode
* @param parentNode
*/
private void deleteSingleSonNode(Node targetNode, Node parentNode){
if (parentNode == null){
// 要删除的是根节点,且根节点有一棵子树
Node sonNode = root.left == null ? root.right : root.left;
root.value = sonNode.value;
root.left = null;
root.right = null;
} else {
Node sonNode = targetNode.left == null ? targetNode.right : targetNode.left;
// 要删除的节点有一棵子树且不是根节点
if (parentNode.left != null && parentNode.left.value == targetNode.value){
parentNode.left = sonNode;
} else {
parentNode.right = sonNode;
}
}
}
/**
* 查找node子树中值最小的节点
* @param node
* @return
*/
private Node findMinNode(Node node){
Node rightMinNode = node;
while (rightMinNode.left != null){
rightMinNode = rightMinNode.left;
}
return rightMinNode;
}
/**
* 中序遍历
*/
public void middleOrder(){
if (root == null){
return;
} else {
root.middleOrder();
}
}
/**
* 层序遍历
*/
public void sequenceOrder(){
if (root == null){
return;
} else {
root.sequenceOrder();
}
}
/**
* 节点
*/
class Node{
/** 值 */
int value;
/** 左子树 */
Node left;
/** 右子树 */
Node right;
Node(int value){
this.value = value;
}
/**
* 添加节点
* @param node
*/
public void add(Node node){
if (node == null){
return;
}
if (node.value < this.value){
// 值比当前节点小,往左添加
if (this.left == null){
this.left = node;
} else {
this.left.add(node);
}
} else {
// 值比当前节点大,往右添加
if (this.right == null){
this.right = node;
} else {
this.right.add(node);
}
}
}
/**
* 查找值为value的节点
* @param value
* @return
*/
public Node findNode(int value){
if (this.value == value){
return this;
} else if (value < this.value && this.left != null){
return this.left.findNode(value);
} else if (value >= this.value && this.right != null){
return this.right.findNode(value);
} else {
return null;
}
}
/**
* 查找值为value的节点的父节点
* @param value
* @return
*/
public Node findParentNode(int value){
if ((this.left != null && this.left.value == value)
|| (this.right != null && this.right.value == value)){
return this;
} else {
if (this.left != null && value < this.value){
return this.left.findParentNode(value);
} else if (this.right != null && value >= this.value){
return this.right.findParentNode(value);
} else {
return null;
}
}
}
/**
* 中序遍历
*/
public void middleOrder(){
if (this.left != null){
this.left.middleOrder();
}
System.out.println(this.value);
if (this.right != null){
this.right.middleOrder();
}
}
/**
* 层序遍历
*/
public void sequenceOrder(){
Queue<Node> queue = new LinkedList<>();
Node currentNode = this;
while(currentNode != null){
System.out.println(currentNode.value);
if (currentNode.left != null){
queue.add(currentNode.left);
}
if (currentNode.right != null){
queue.add(currentNode.right);
}
currentNode = queue.poll();
}
}
}
}
测试代码:
public class BinarySearchTreeTest {
public static void main(String[] args) {
int[] arr = {7,3,10,12,5,1,9};
BinarySearchTree binarySearchTree = new BinarySearchTree();
for (int i = 0; i < arr.length; i++) {
binarySearchTree.add(arr[i]);
}
binarySearchTree.middleOrder();
binarySearchTree.deleteNode(5);
System.out.println("删除之后:");
binarySearchTree.middleOrder();
}
}
不知各位发现没有,二叉排序树中序遍历就是一个升序序列。