【Java数据结构与算法】二叉树遍历，二叉搜索树插入、查找、删除

1. 不存在度大于2的结点
2. 左子树、右子树有次序，即使只有一颗子树，也得区分左子树、右子树

所有节点只有左子树的二叉树叫左斜树

所有分支结点都有左子树和右子树，所有叶子在同一层

1. 叶子节点只在最下层和次下层
2. 只有一个子树的结点，这个子树一定是左子树
3. 结点数相同的二叉树，完全二叉树的深度最小
   例：

又叫二叉查找树、二叉排序树

1. 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
3. 它的左、右子树也分别为二叉查找树。

前序遍历：按父 ->左->右的顺序
中序遍历：按左 ->父->右的顺序
后序遍历：按左->右 ->父的顺序
层序遍历：一层一层的遍历
例：

程序的二叉树和上图二叉树一样

public class _普通二叉树遍历 {
    public static void main(String[] args) {
        //创建二叉树
        TreeNode root = new TreeNode('A');
        root.left = new TreeNode('B');
        root.right = new TreeNode('C');
        root.left.left = new TreeNode('D');
        root.left.right = new TreeNode('E');
        root.right.left = new TreeNode('F');
        root.right.right = new TreeNode('G');
        root.left.left.left = new TreeNode('H');
        root.left.left.right = new TreeNode('I');
        root.left.right.left = new TreeNode('J');

        System.out.print("前序遍历：");
        MLR前序遍历(root);
        System.out.println();
        
        System.out.print("中序遍历：");
        LMR中序遍历(root);
        System.out.println();
        
        System.out.print("后序遍历：");
        LRM后序遍历(root);
        System.out.println();
        
        System.out.print("层序遍历：");
        BFS层序遍历(root);
        System.out.println();


    }
    //前序遍历, 父 -> 左 -> 右
    public static void MLR前序遍历(TreeNode root) {
        System.out.print(root.c); //先输出根节点
        //左子树递归
        if(root.left != null){
            MLR前序遍历(root.left);
        }
        //右子树递归
        if(root.right != null){
            MLR前序遍历(root.right);
        }
    }

    //中序遍历,  左 -> 父 -> 右
    public static void LMR中序遍历(TreeNode root) {
        //左子树递归
        if(root.left != null){
            LMR中序遍历(root.left);
        }
        System.out.print(root.c); //中间输出根节点
        //右子树递归
        if(root.right != null){
            LMR中序遍历(root.right);
        }
    }

    //后序遍历,  左 -> 右 -> 父
    public static void LRM后序遍历(TreeNode root) {
        //左子树递归
        if(root.left != null){
            LRM后序遍历(root.left);
        }
        //右子树递归
        if(root.right != null){
            LRM后序遍历(root.right);
        }
        System.out.print(root.c); //最后输出根节点
    }
   
    public static void BFS层序遍历(TreeNode root) {
        if (root == null) return;
        Queue queue = new linkedList<>();
        queue.add(root); //用队列实现一层一层从左到右遍历
        while (queue.size() > 0) {
            TreeNode poll = queue.poll();
            System.out.print(poll.c);
            if (poll.left != null) queue.add(poll.left);
            if (poll.right != null) queue.add(poll.right);
        }
    }

}

class TreeNode {
     Character c;
     TreeNode left;
     TreeNode right;

    public TreeNode(char c) {
        this.c = c;
    }

}

输出：

前序遍历：ABDHIEJCFG
中序遍历：HDIBJEAFCG
后序遍历：HIDJEBFGCA
层序遍历：ABCDEFGHIJ

删除部分比较复杂一点，分三种情况

1. 删除的结点没有子结点，直接删除，让他的parent.left(right) = null
2. 删除的结点只有一个孩子结点，直接删除，让它parent.left(或者right) = 孩子节点
3. 删除的结点有两个孩子结点：
   引入后继结点的概念，后继结点就是中序遍历二叉树后，这个结点的下一个结点, 也是右子树中最小的结点。
   找到后继结点后，用后继结点替换当前要删除的结点即可。四步实现：
   successor.parent = successor.right
   successor.left= cur.left
   successor.right = cur.right
   parent.left(right) = successor

public class _二叉搜索树 {
    public static void main(String[] args) {

    }
}
class BinarySearchTree{

    //结点类
    private class Node{
        int no;
        Node left;
        Node right;

        public Node() { }
        public Node(int no) {
            this.no = no;
        }
    }
    private Node root;//树根节点

    
    public void insert(int data){
        Node in = new Node(data);//待插入结点
        if (root == null) {
            root = in;
        }else {
            Node parent;
            Node cur = root;
            while (true){
                parent = cur;
                if(data > cur.no){  //比当前结点大就往右走
                    cur = cur.right;
                    if(cur == null){
                        parent.right = in; //走到尽头，插入
                        return;
                    }
                }else if (data < cur.no){ //比当前结点小就往右走
                    cur = cur.left;
                    if(cur == null){
                        parent.left = in; //走到尽头，插入
                        return;
                    }
                }else {
                    System.out.println("元素重复，不能插入");
                    return;
                }
            }
        }
    }

    
    public Node find(int data) {
        Node cur = root;
        while (cur != null) {
            if (data == cur.no) {
                return cur;
            }
            cur = data > cur.no ? cur.right: cur.left;
        }
        return null;
    }

    
    public boolean remove(int data){
        Node cur = root;
        Node curParent = null;
        boolean isRightChile = false;
        while (cur.no != data){
            curParent = cur;
            if (data > cur.no){
                cur = cur.right;
                isRightChile = true;
            }else {
                cur = cur.left;
                isRightChile = false;
            }
            if (cur == null) {
                System.out.println("找不到要删除的结点");
                return false;
            }
        }
        //此时，cur就是要删除的结点， parent是其父节点

        //1.要删除的结点是叶子结点
        if(cur.right == null && cur.left == null) {

            if (cur == root) {  //当前结点是根节点,父节点未更新=null
                root = null;//直接清空
            }else { //让他的parent.left(right) = null
                if (isRightChile) curParent.right = null;
                else curParent.left = null;
            }
        }
        //2.要删除的结点有一个子节点 直接删除，让它parent.left(或者right) = 孩子节点
        else if (cur.left == null){
            if (cur == root) root = cur.right;
            else if (isRightChile) curParent.right = cur.right;
            else curParent.left = cur.right;
        }else if (cur.right == null) {
            if (cur == root) root = cur.left;
            else if (isRightChile) curParent.right = cur.left;
            else curParent.left = cur.left;
        }

        //2.要删除的结点有两个子杰点，找到后继结点，
        //1.找到后继结点并对其进行调整
        Node successor = getSuccessor(cur);
        //2.第三步
        if (curParent == null) { //也就是 cur == root
            root = successor;
            //TODO
        }else if (isRightChile){
            curParent.right = successor;
        }else {
            curParent.left = successor;
        }
        //第四步
        successor.left = cur.left;
        return true;

    }

    private Node getSuccessor(Node del) {
        Node successorPatent = del;
        Node successor = del;
        Node cur = del.right;

        //找到右子树最小的那个结点
        while (cur != null){
            successorPatent = successor;
            successor = cur;
            cur = cur.left;
        }
        //如果 successor
        if (successor != del.right) {
            //第一步
            successorPatent.left = successor.right; //successor没有 左子结点
            //第二步
            successor.right = del.right;
        }
        return successor;
    }
}