二叉排序树
1. 是什么？
数组和链表在增删改查数据时，都有各自的缺点，比如数组要在中间插入数据，就要让后面的数据整体都移动，而链表检索数据很慢。之前说二叉树时，说到树这种结构就是就是为了弥补数组和链表的缺点而诞生的，二叉排序树(Binary search tree，简称BST)，更是体现了这一点。二叉排序树有以下特点：
- 左子节点的值比父节点小；
- 右子节点的值比父节点大；
2. 构建过程：
假如现有数列：7,3,10,12,5,1,9，构建二叉排序树的过程如下：
- 7当成父节点，3比7小，放到7的左边；
- 10比7大，放到7的右边；
- 12比7大，比10也大，放到10的右边；
- 5比7小，比3大，放到3的右边；
- 1比7小，比3小，放到3的左边；
- 9比7大，比10小，放到10的左边；
二叉排序树
3. 二叉排序树的删除：
二叉排序树的删除有三种情况，如下：
(1)：删除的是叶子节点：比如上面这棵二叉排序树中的1,5,9,12：
- 首先找到这个节点targetNode，如果不存在，直接删除失败；
- 然后找到targetNode节点的父节点parent；
- 然后判断targetNode是它的左节点还是右节点，直接让对应的左/右节点置空就行了(为什么不能直接targetNode == null？因为这个时候targetNode其实只是一个临时指针，并不是原二叉树的节点，targetNode == null对原二叉树是没有影响的)。
(2)：删除的是只有一棵子树的节点：假如上面这棵二叉排序树节点1右边再挂个2，那么1就是只有一棵子树：
- 前面的逻辑都一样，找到targetNode的parentNode后，要判断targetNode的子节点sonNode是在targetNode的左边还是右边，同时要判断targetNode在parent的左边还是右边。
- 如果targetNode是parentNode的左子节点，那么直接将sonNode挂在parentNode左边即可；
- 如果targetNode是parentNode的右子节点，那么直接将sonNode挂在parentNode右边即可；
- 如果parentNode为空，说明要删除的是根节点，并且根节点只有一个子节点，那么直接把这个子节点的值赋给根节点，然后再置空子节点即可。
(3)：删除的是有两棵子树的节点：比如上面这棵二叉排序树中的7，3，10:
- 前面的逻辑也一样，找到targetNode和parentNode；
- 从targetNode的右子树找到最小的节点，用临时变量temp保存起来；
- 删除上一步找到的那个右子树的最小节点；
- 将temp的值赋给targeteNode。
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();
}
}不知各位发现没有，二叉排序树中序遍历就是一个升序序列。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-05-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读