二叉搜索樹(shù)刪除節(jié)點(diǎn)分三種情況:

1. 被刪除節(jié)點(diǎn)沒(méi)有子樹(shù)的情況，直接刪除，并修改對(duì)應(yīng)父節(jié)點(diǎn)的指針為空。
2. 對(duì)于只有一個(gè)子樹(shù)的情況，考慮將其子樹(shù)作為其父節(jié)點(diǎn)的子樹(shù)，關(guān)于是左還是右，根據(jù)被刪除的節(jié)點(diǎn)確定。
3. 被刪除節(jié)點(diǎn)有左右孩子,可以從它的左子樹(shù)找到最大的節(jié)點(diǎn),然后被刪除節(jié)點(diǎn)的值替換為左子樹(shù)最大節(jié)點(diǎn)的值.最后把左子書(shū)最大節(jié)點(diǎn)刪除.也可以對(duì)右子樹(shù)最小節(jié)點(diǎn)做操作.
   此外,還需要考慮別刪除的節(jié)點(diǎn)是根節(jié)點(diǎn)或者被刪除節(jié)點(diǎn)不存在,如果需要修改根節(jié)點(diǎn),還要修改樹(shù)根節(jié)點(diǎn)的引用.

BinarySortTree.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 二叉排序樹(shù)
 */
public class BinarySortTree<T extends Comparable<? super T>> {
    //根節(jié)點(diǎn)
    private Node root;

    public Node getRoot() {
        return root;
    }


    //二叉樹(shù)節(jié)點(diǎn)
    class Node {
        T val;
        Node left;
        Node right;
        int count = 1;

        Node(T val) {
            this.val = val;
        }
    }

    /**
     * 層次遍歷
     * 用一個(gè)鏈表保存節(jié)點(diǎn),每次從前面取節(jié)點(diǎn),同時(shí)把該節(jié)點(diǎn)的左右節(jié)點(diǎn)加入鏈表尾部
     *
     * @return 每個(gè)List表示一層元素
     */
    public List<List<T>> levelTraverse() {
        List<List<T>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<Node> list = new LinkedList<>();
        list.push(root);
        while (!list.isEmpty()) {
            //當(dāng)前層元素?cái)?shù)量
            int size = list.size();
            List<T> nowLevelElemts = new ArrayList<>();
            while (size-- > 0) {
                Node node = list.removeFirst();
                nowLevelElemts.add(node.val);
                if (node.left != null) {
                    list.addLast(node.left);
                }
                if (node.right != null) {
                    list.addLast(node.right);
                }
            }
            res.add(nowLevelElemts);
        }
        return res;
    }

    /**
     * 插入
     */
    public void insert(T val) {
        if (root == null) {
            root = new Node(val);
            return;
        }

        //找到的位置
        Node parentNode = root;
        Node curNode = root;
        while (curNode != null) {
            parentNode = curNode;
            if (val.compareTo(curNode.val) < 0) {
                curNode = curNode.left;
            } else if (val.compareTo(curNode.val) > 0) {
                curNode = curNode.right;
            } else {
                //已經(jīng)存在val了
                curNode.count++;
                return;
            }
        }

        //插入新節(jié)點(diǎn)
        if (val.compareTo(parentNode.val) < 0) {
            parentNode.left = new Node(val);
        }
        if (val.compareTo(parentNode.val) > 0) {
            parentNode.right = new Node(val);
        }
    }

    /**
     * 查找指定值的父節(jié)點(diǎn)
     *
     * @return 找不到返回null, 找到則返回父節(jié)點(diǎn)
     */
    private Node findParent(Node root, T val) {
        if (root == null || val.equals(root.val)) {
            return null;
        }
        Node res = root;
        while (root != null) {
            if (root.val.equals(val)) {
                break;
            } else if (val.compareTo(root.val) > 0) {
                res = root;
                root = root.right;
            } else {
                res = root;
                root = root.left;
            }
        }
        return root == null ? null : res;
    }


    public boolean delNode(T val) {
        if (val.equals(root.val)) {
            delNode(root);
            return true;
        }
        //得到val的父節(jié)點(diǎn)
        Node parent = findParent(root, val);
        //val不存在
        if (parent == null) {
            return false;
        }
        return delNode(parent, parent.left.val.equals(val) ? parent.left : parent.right);
    }

    /**
     * @param parent 要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)
     * @param p      要?jiǎng)h除的節(jié)點(diǎn)
     * @return 刪除成功返回true, 否則返回false
     */
    private boolean delNode(Node parent, Node p) {
        if (parent == null) {
            throw new NullPointerException();
        }
        if (p == null) {
            return true;
        }
        if (parent.left != p && parent.right != p) {
            return false;
        }
        //p沒(méi)有孩子節(jié)點(diǎn),直接刪除
        if (p.left == null && p.right == null) {
            if (parent.left == p) {
                parent.left = null;
            } else {
                parent.right = null;
            }

            //p只有一個(gè)孩子節(jié)點(diǎn),讓p的父節(jié)點(diǎn)指向p的孩子節(jié)點(diǎn)
        } else if (p.left == null || p.right == null) {
            if (parent.left == p) {
                parent.left = (p.left == null ? p.right : p.left);
            } else {
                parent.right = (p.left == null ? p.right : p.left);
            }
            //p有兩個(gè)孩子節(jié)點(diǎn)時(shí),找到p的左字樹(shù)中最大的節(jié)點(diǎn),p賦值為左字樹(shù)中最大的節(jié)點(diǎn)的值,
            //同時(shí)刪除左字樹(shù)中最大的節(jié)點(diǎn)
        } else {
            parent = p;
            Node leftMaxNode = p.left;
            while (leftMaxNode.right != null) {
                parent = leftMaxNode;
                leftMaxNode = leftMaxNode.right;
            }
            p.val = leftMaxNode.val;
            //如果p的左孩子沒(méi)有孩子節(jié)點(diǎn),parent就是p,parent的左孩子就是左邊最大的節(jié)點(diǎn)
            if (parent.left == leftMaxNode) {
                parent.left = leftMaxNode.left;
            } else {
                parent.right = leftMaxNode.left;
            }
        }
        return true;
    }

    /**
     * 尋找二叉樹(shù)最大節(jié)點(diǎn)
     *
     * @param root
     * @return
     */
    public Node findMaxNode(Node root) {
        if (root == null) {
            return null;
        }
        //一直往右邊走就對(duì)了
        Node res = root;
        while (res.right != null) {
            res = res.right;
        }
        return res;
    }

    /**
     * 尋找二叉樹(shù)最小節(jié)點(diǎn)
     *
     * @param root
     * @return
     */
    public Node findMinNode(Node root) {
        if (root == null) {
            return null;
        }
        //一直往左邊走就對(duì)了
        Node res = root;
        while (res.left != null) {
            res = res.left;
        }
        return res;
    }

    private boolean delNode(Node p) {
        if (p == null) {
            return true;
        }
        //要?jiǎng)h除的節(jié)點(diǎn)為根節(jié)點(diǎn)
        if (p == root) {
            //找到左子樹(shù)最大的節(jié)點(diǎn)
            if (p.left != null) {
                Node parent = p;
                Node leftMaxNode = p.left;
                while (leftMaxNode.right != null) {
                    parent = leftMaxNode;
                    leftMaxNode = leftMaxNode.right;
                }
                p.val = leftMaxNode.val;
                if (parent.left == leftMaxNode) {
                    parent.left = leftMaxNode.left;
                } else {
                    parent.right = leftMaxNode.left;
                }
                //找右子樹(shù)最小的節(jié)點(diǎn)
            } else if (p.right != null) {
                Node parent = p;
                Node rightMinNode = p.right;
                while (rightMinNode.left != null) {
                    parent = rightMinNode;
                    rightMinNode = rightMinNode.left;
                }
                p.val = rightMinNode.val;
                if (parent.right == rightMinNode) {
                    parent.right = rightMinNode.right;
                } else {
                    parent.left = rightMinNode.right;
                }
                //都找不到,意味著二叉樹(shù)只有一個(gè)節(jié)點(diǎn)
            } else {
                this.root = null;
            }
            return true;
        }
        Node pParent = findParent(root, p.val);
        //不存在p的父節(jié)點(diǎn),那也不存在節(jié)點(diǎn)p
        if (pParent == null) {
            return false;
        }
        return delNode(pParent, p);
    }
}

TreeTest.java

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.List;
import java.util.Scanner;

public class TreeTest {
    public static void main(String[] args) {
        BinarySortTree<Integer> tree = new BinarySortTree<>();
        //input.txt的內(nèi)容為:
        //15 5 3 12 16 20 23 13 18 10 6 7
        Scanner in = getScanner("input.txt");
        //測(cè)試插入元素
        while (in.hasNext()) {
            tree.insert(in.nextInt());
        }
        //測(cè)試刪除元素
        testDelete(tree);

    }

    private static void testDelete(BinarySortTree<Integer> tree) {
        //層次遍歷元素
        List<List<Integer>> elements = tree.levelTraverse();
        System.out.println(elements);

        //測(cè)試刪除根節(jié)點(diǎn)
//        tree.delNode(tree.getRoot().val);
//        elements = tree.levelTraverse();
//        System.out.println(elements);

        //測(cè)試刪除帶兩個(gè)孩子節(jié)點(diǎn)的節(jié)點(diǎn)
//        tree.delNode(5);
//        elements = tree.levelTraverse();
//        System.out.println(elements);

//        //測(cè)試刪除帶左孩子節(jié)點(diǎn)的節(jié)點(diǎn)
//        tree.delNode(10);
//        elements = tree.levelTraverse();
//        System.out.println(elements);

        //測(cè)試刪除帶右孩子節(jié)點(diǎn)的節(jié)點(diǎn)
//        tree.delNode(16);
//        elements = tree.levelTraverse();
//        System.out.println(elements);

        //測(cè)試刪除沒(méi)有孩子子節(jié)點(diǎn)的節(jié)點(diǎn)
//        tree.delNode(18);
//        elements = tree.levelTraverse();
//        System.out.println(elements);

        //測(cè)試刪除不存在的節(jié)點(diǎn)
//        tree.delNode(181);
//        elements = tree.levelTraverse();
//        System.out.println(elements);
    }

    //從輸入流讀取輸入數(shù)據(jù)
    public static Scanner getScanner(InputStream is) {
        return new Scanner(is);
    }

    //從文件讀取輸入數(shù)據(jù)
    public static Scanner getScanner(String fileName) {
        try {
            return getScanner(new FileInputStream(fileName));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        return null;
    }
}