-
为什么使用二叉排序树
对于顺序存储的二叉树：不排序-查找/删除/插入困难
排序-删除/插入困难
链式存储的二叉树：是否排序-都会查找困难(每次都需要从头结点开始找)
而二叉排序树就解决了以上问题
-
什么是二叉排序树
百度百科定义：二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。在一般情况下，查询效率比链表结构要高。
要求： 对于二叉树中的任何一个非叶子结点，要求左子结点比当前结点值小，右子结点比当前结点值大。
举例：
需求-将如下数字 {7,3,11,13,5,1,9} 变成一颗二叉排序树
实现思路：将第一个数作为根节点，依次比较，比它大的放右子节点，小的放子节点
如果子节点还有子节点，那么就需要接着往下比较，直到找到一个合适的位置，如下图
如果我们想插入任意一个数字，比如插入10
比较过程：和7比较->和11比较->和9比较->插入到9的右子节点
2. 代码实现 2.1 涉及的操作add() 增加结点-使其变成一颗二叉排序树
midShow() 中序遍历输出二叉排序树-使用中序遍历刚好能够输出排序好的序列
search() 查找节点-输入value，如果找到返回value
delete() 删除节点-只删除传入的目标节点，其他结点不删除并且删除后还是一颗二叉排序树
情况一： 删除的节点是叶子结点
只需切断父节点和删除节点的联系即可
情况二： 删除节点有一颗子树：左子树或右子树
需要用删除节点的子树替换掉目标结点, 如：删除节点是left，它的子树是left parent.left=target.left
情况三： 删除节点有两棵子树，左子树和右子树
删除节点的左子树中结点值都小于删除节点，右子树都大于删除节点
要删除目标节点，我们要找到可以替代它位置的节点，而这个结点就是左子树最大的或者右子树最小的
Way1：删除目标节点左子树中最大的结点并存储它的value，用value替换掉目标节点value
Way2：删除目标节点右子树中最小的结点并存储它的value，用value替换掉目标节点value
(以下我们采用方式二)
2.2 代码BinarySortTree.java
//二叉排序树
public class BinarySortTree {
Node root;
//添加节点
public void add(Node node){
//第一次进入方法时，是一颗空树，设置为根节点root
if(root==null){
root=node;
}else{
//调用节点的add方法
root.add(node);
}
}
//中序遍历，输出二叉排序树结果
public void midShow(){
if(root!=null){
root.midShow(root);
}
}
//查找节点
public Node search(int value){
if(root!=null){
return root.search(value);
}
return null;
}
//删除结点
public void delete(int value){
if(root==null){
return;
}
root.delete(value);
}
//查找父节点
public Node SearchParent(int value){
if(root!=null){
return root.searchParent(value);
}
return null;
}
}
Node.java
public class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
//添加节点
public void add(Node node) {
//小于当前结点值
if(node.valuethis.value){
//往右节点查找
if(this.right==null){
this.right=node;
return;
}
//没有找到继续往下递归查找
this.right.add(node);
}
}
//中序遍历
public void midShow(Node node) {
if(node==null){
return;
}
//遍历左儿子
midShow(node.left);
//输出当前值
System.out.print(node.value+" ");
//遍历右儿子
midShow(node.right);
}
//查找节点
public Node search(int value) {
//找到节点直接返回
if(this.value==value){
return this;
}
//要查找的value比当前小，查找左节点
else if(valuethis.value){
if(this.right==null){
return null;
}
return this.right.search(value);
}
return null;
}
//删除结点
public void delete(int value) {
Node target=search(value);
if(target==null){
return;
}
//找到父节点
Node parent = searchParent(value);
//如果删除的节点是叶子节点
if(target.left==null&&target.right==null){
if(parent.left==target){
parent.left=null;
}else{
parent.right=null;
}
//删除的节点有左右两棵子树
}else if(target.left!=null&&target.right!=null){
//删除目标节点右子树中最小的结点，并存储最小节点值
int rightMin= findRightMin(target.right);
//替换目标节点value,这是就相当于我们删除了目标元素
target.value=rightMin;
//删除的节点有左子树或右子树
}else{
//目标节点是父节点的左节点
if(target==parent.left){
//目标元素有左子树
if(target.left!=null){
parent.left=target.left;
//目标元素有右子树
}else{
parent.left=target.right;
}
//目标节点是父节点的右节点
}else{
if(target.right!=null){
parent.right=target.right;
}else{
parent.right=target.left;
}
}
}
}
//找到并删除右子树中最小节点值的节点返回该节点的值
public int findRightMin(Node right) {
//一直找左儿子，直到为空
while(right.left!=null){
right=right.left;
}
int value=right.value;
//这里我们直接调用delete方法，必定是叶子结点，这种情况我们上面已经考虑到
delete(value);
return value;
}
//查找父节点
public Node searchParent(int value) {
//如果当前节点的左儿子或右儿子是目标节点，找到父节点，返回
if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
return this;
}else{
//往左子树递归查找
if(valuethis.value&&this.right!=null){
return this.right.searchParent(value);
}
}
return null;
}
}
测试类 TestBinarySortTree.java
public class TestBinarySortTree {
public static void main(String[] args) {
//二叉排序树的组成节点值
int[] arr={7,3,11,13,5,1,9};
//创建二叉排序树
BinarySortTree binarySortTree = new BinarySortTree();
//遍历给二叉排序树添加节点
for (int value : arr) {
binarySortTree.add(new Node(value));
}
//遍历输出二叉排序树(中序遍历)
System.out.println("二叉排序树遍历结果：");
binarySortTree.midShow();
//查找节点
System.out.println("n查找value=9的结点："+binarySortTree.search(9).value);
System.out.println("查找value=10的结点："+binarySortTree.search(10));
//测试删除节点
binarySortTree.delete(7);//删除有两棵子树的节点7
System.out.print("删除结点7：");
binarySortTree.midShow();
System.out.print("n删除结点1：");
binarySortTree.delete(1);//删除叶子结点1
binarySortTree.midShow();
System.out.print("n删除结点3：");
binarySortTree.delete(3);//删除只有一颗子树的节点3
binarySortTree.midShow();
}
}
2.3 运行结果
二叉排序树遍历结果： 1 3 5 7 9 11 13 查找value=9的结点：9 查找value=10的结点：null 删除结点7：1 3 5 9 11 13 删除结点1：3 5 9 11 13 删除结点3：5 9 11 13
