二叉排序树

二叉排序树：BST(Binary Sort Tree)，对于二叉排序树的任何一个非叶子结点，要求左子节点的值比当前节点的值小，右子结点的值比当前节点的大。如果有相同的值，可以将该结点放在左子节点或者右子结点。

package BinarySortTree;

/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: ChrisPeng
 * @Date: 2021/06/25/20:37
 * @Description:
 */
public class Demo {
    public static void main(String[] args) {
        int[] arr = {7,3,10,12,5,1,9};
        BinarySortTree binarySortTree = new BinarySortTree();
        //for循环添加节点到排序树
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }

        //中序遍历二叉树
        System.out.println("中序遍历二插排序树" );
        binarySortTree.infixOrder();
    }
}

//创建二叉排序树
class BinarySortTree{
    private Node root;
    //添加节点的方法
    public void add(Node node){
        if (root == null){
            //如果为空，则直接让root指向node
            root = node;
        }else {
            root.add(node);
        }
    }
    public void infixOrder(){
        if (root!= null){
            root.infixOrder();
        }else {
            System.out.println("此二叉树为空");
        }
    }
}
class Node{
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //添加节点的方法
    //递归的形式添加节点，需要满足二叉排序树的要求
    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);
            }
        }
    }
    //中序遍历
    public void infixOrder(){
        if (this.left != null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null){
            this.right.infixOrder();
        }
    }
}

二叉排序树的删除

• 情况一：当要删除的结点没有子结点的时候： (1)需要先去找到要删除的结点targetNode (2)找到targetNode的父节点parent (3)确定targetNode是parent的左子节点还是右子结点 (4)根据前面的情况对应的删除，左子节点:parent.left = null;右子结点:parent.right = null;
• 情况二：删除只有一颗子树的结点 (1)首先找到要删除的结点targetNode (2)找到target的父节点parent (3)确定targetNode的子结点是右子结点还是左子节点 (4)targetNode是parent的左子节点还是右子结点 (5)如果targetNode是parent的左子节点 5.1 targetNode的子结点是左子节点，parent.left=targetNode.left 5.2 targetNode的子结点是右子节点，parent.left=targetNode.right 如果targetNode是parent的右子结点 5.3 targetNode的子结点是左子节点，parent.left=targetNode.right 5.4 targetNode的子结点是右子节点，parent.right=targetNode.right
• 情况三：删除有两颗子树的结点 (1)首先找到要删除的结点targetNode (2)找到target的父节点parent (3)从targetNode的右子树找到最小的结点 (4)用一个临时变量，将最小的值保存到temp (5)删除最小节点 (6)targetNode.value = temp

赏

谢谢你请我吃糖果