内容来自尚硅谷Java数据结构与java算法（Java数据结构与算法）_哔哩哔哩_bilibili

写在前面:本文内容大致和原视频内老师的笔记内容相同，会偶尔插入自己的注释和理解，尽量会完成作业

本次作业已完成，理解了之后就很简单

11.4二叉排序树

11.4.1先看一个需求

给你一个数列(7,3,10,12,5,1,9),要求能够高效的完成对数据的查询和添加

11.4.2解决方案分析

使用数组

数组未排序，优点:直接在数组尾添加，速度快。缺点:查找速度慢.[示意图]

数组排序，优点:可以使用二分查找，查找速度快，缺点:为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢。[示意图]

使用链式存储-链表

不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动。[示意图]

使用二叉排序树

11.4.3二叉排序树介绍

二叉排序树:BST:(BinarySort(Search)Tree)。对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

特别说明:如果有相同的值，可以将该节点放在左子节点或右子节点

比如针对前面的数据(7,3,10,12,5,1,9)，对应的二叉排序树为:

11.4.4二叉排序树的创建和遍历

一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如:数组为Array(7,3,10,12,5,1,9)，创建成对应的二叉排序树为∶

二叉排序树的删除情况比较复杂，有下面三种情况需要考虑

1.      删除叶子节点(比如: 2,5,9,12)

2.      删除只有一颗子树的节点(比如:1)

3.      删除有两颗子树的节点.(比如:7,3,10)

4.      操作的思路分析

//对删除节点的不同情况的分析

第一种情况:

删除叶子节点(比如:2,5,9,12)

思路

(1)需求先去找到要删除的结点targetNode

(2)找到targetNode的父结点parent

(3)确定targetNode是parent的左子结点还是右子结点

(4)根据前面的情况来对应册除

左子结点parent.left = null

右子结点parent.right = null;

第二种情况:册删除只有一颗子树的节点比如1

思路

(1)需求先去找到要删除的结点targetNode

(2)找到targetNode的父结点parent

(3)确定targetNode的子结点是左子结点还是右子结点

(4)targetNode是parent的左子结点还是右子结点

(5)如果targetNode有左子结点

5.1如果targetNode是parent 的左子结点

parent.left = targetNode.left;

5.2如果targetNode是parent的右子结点

parent.right = targetNode.left;

(6)如果targetNode有右子结点

6.1如果targetNode是 parent的左子结点

parent.left = targetNode.right;

6.2如果targetNode是 parent的石子结点

parent.right = targetNode.right

情况三:删除有两颗子树的节点.(比如:7,3，10 )

思路

(1)需求先去找到要删除的结点targetNode

(2)找到targetNode的父结点 parent

(3)从targetNode 的右子树找到最小的结点

(4)用一个临时变量，将最小结点的值保存temp = 11

(5)删除该最小结点

(6)targetNode.value = temp

11.4.6二叉排序树删除节点的代码实现

11.4.7课后练习：完成老师代码，并使用第二种方式解决

如果我们从左子树找到最大的节点，然后按照前面的思路完成