二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树； （4）没有键值相等的结点。

---

二叉排序树的删除(有以下三种情况)：

---

情况一：删除叶子结点

（1）找到需要删除的targetNode

（2）找到需要删除的targetNode的父节点parentNode

（3）确定需删除的targetNode是左子结点还是右子结点 如果是左子结点：parentNode.left = null 如果是右子结点：parentNode.right = null

情况二：删除只有一颗子树的结点 （1）找到需要删除的targetNode

（2）找到需要删除的targetNode的父节点parentNode

（3）确定targetNode的子结点是左子结点还是右子结点

（4）确定targetNode是parent的左子结点还是右子结点

（5）如果targetNode是parentNode的左子结点 <1>如果targetNode的子结点是左子结点：parentNode.left = targetNode.left <2>如果targetNode的子结点是右子结点：parentNode.left = targetNode.right

（6）如果targetNode是parentNode的右子结点 <1>如果targetNode的子节点是左子节点：parentNode.right = targetNode.left <2>如果targetNode的子节点是右子节点：parentNode.right = targetNode.right

情况三：删除有两颗子树的结点

（1）找到需要删除的targetNode

（2）找到需要删除的targetNode的父结点parentNode

（3）从targetNode的右子树找最小的结点

（4）用一个临时变量temp接收此在右子树寻找最小的结点

（5）删除该最小的结点

（6）TargetNode.value = temp

实现代码：

package com.tree; public class BinarySortTreeDemo { public static void main(String[] args) { int[] arr = {7,3,10,12,5,1,9,2}; BinarySortTree binarySortTree = new BinarySortTree(); for (int i = 0; i < arr.length; i++) {//循环添加结点 binarySortTree.addNode(new Node(arr[i])); } binarySortTree.delNode(7); binarySortTree.infixOrder();//运行后，树是按升序的顺序输出的 } } //创建二叉排序树 class BinarySortTree { private Node root; //查找需要删除结点的方法 public Node searchTarget(int value) { if (root == null) return null; else return root.searchTarget(value); } //查找需要删除结点的父节点(parentNode) public Node searchparentNode(int value) { if (root == null) return null; else return root.searchParentNode(value); } //右子树向左删除最小结点 public int delRightTreeMin(Node node){ //定义一个辅助变量指针 Node target = node; while (target.getLeft() != null) { //向左递归查找最小的结点 target = target.getLeft(); } //删除最小结点 delNode(target.getValue()); return target.getValue();//返回当前最小的结点 } //删除结点方法 public void delNode(int value) { if (root == null) return; else { //1、查找需要删除的结点(targetNode) Node targetNode = searchTarget(value); if (targetNode == null)//此时没有找到需要删除的结点 return; //如果此时二叉排序树只有一个结点(根结点)，直接删除 if (root.getLeft() == null && root.getRight() == null) { root = null; return; } //2、查找targetNode的父结点(parentNode) Node parentNode = searchparentNode(value); //一、如果要删除的结点是叶子结点 if (targetNode.getLeft() == null && targetNode.getRight() == null) { //此时targetNode为叶子结点,判断targetNode是父节点的左子结点或右子结点 //此时targetNode是parentNode的左子结点 if (parentNode.getLeft() != null && parentNode.getLeft().getValue() == value) parentNode.setLeft(null); //此时targetNode是parentNode的左子结点 else if (parentNode.getRight() != null && parentNode.getRight().getValue() == value) parentNode.setRight(null); } //二、如果要删除的是有两颗子树的结点 else if (targetNode.getLeft() != null && targetNode.getRight() != null) { int minVal = delRightTreeMin(targetNode.getRight());//从右子树删除最小的结点 targetNode.setValue(minVal); } //三、如果要删除的是只有一颗子树的结点 else { if (targetNode.getLeft() != null) {//如果要删除的结点有左子结点 if (parentNode != null) { //targetNode是parentNode的左子结点 if (parentNode.getLeft().getValue() == value) parentNode.setLeft(targetNode.getLeft()); //targetNode是parentNode的右子结点 else { parentNode.setRight(targetNode.getLeft()); } } else//此时删除的是根结点 { root = targetNode.getLeft(); } } else //如果删除的结点有右子结点 { if (parentNode != null) { //targetNode是parentNode的左子结点 if (parentNode.getLeft().getValue() == value) { parentNode.setLeft(targetNode.getRight()); }else//targetNode是parentNode的右子结点 parentNode.setRight(targetNode.getRight()); } else {//此时删除的为根结点 root = targetNode.getRight(); } } } } } //添加结点方法 public void addNode(Node node) { if (root == null)//如果root为null，让root指向node root = node; else root.addNode(node); } //中序遍历方法 public void infixOrder() { if (root != null) root.infixOrder(); else System.out.println("树为空"); } } //创建Node结点 class Node { private int value; private Node left; private Node right; public Node(int value) { this.value = value; } //查找需要删除的结点 //value->希望删除结点的值，如果找到返回该结点，否则返回null public Node searchTarget(int value) { if (value == this.value)//此时找到希望删除的结点 return this; else if (value < this.value){//如果查找的值小于当前结点，向左子树递归查找 if (this.left == null)//此时左子结点为空，找不到 return null; else return this.left.searchTarget(value); }else//此时查找的值大于当前结点，向右子树递归查找 { if (this.right == null)//此时右子树为空，找不到 return null; else return this.right.searchTarget(value); } } //查找要删除结点的父结点(parentNode) //value->要找到结点的值 public Node searchParentNode(int value) { if ((this.left != null && this.left.value == value)|| (this.right!= null && this.right.value == value)) { //此时this就位parentNode return this; }else { //如果查找的值比当前的值要小，并且当前的左子结点不为空，则向左子树递归查找parentNode if (value < this.value && this.left != null) return this.left.searchParentNode(value); //如果查找的值比当前的值要大，并且当前的右子结点不为空，则向右子树递归查找parentNode else if (value >= this.value && this.right != null) return this.right.searchParentNode(value); else {//此时上述条件都不满足，即为没有父节点 return null; } } } //添加结点的方法 //以递归的形式添加结点，需要满足二叉排序树的要求 public void addNode(Node node) { if (node == null)//此时没有添加内容 return; //判断传入的值与当前子树根结点的值之间大小关系 if (node.value < this.value)//此时传入的值小于根结点的值，应放入根节点的左边 { if (this.left == null)//判断根结点的左子结点是否为空 this.left = node; else this.left.addNode(node);//如果不为空，递归向左子树添加 }else //此时传入的值大于根结点的值，应放入根节点的右边 { if (this.right == null)//判断根结点的右子结点是否为空 this.right = node; else this.right.addNode(node);//递归向右子结点添加 } } //中序遍历 public void infixOrder() { if (this.left != null) this.left.infixOrder(); System.out.println(this); if (this.right != null) this.right.infixOrder(); } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } @Override public String toString() { return "Node{" + "value=" + value + '}'; } }