二叉树的插入、前序遍历、中序遍历、后序遍历、查找节点、删除节点
首先需要一个节点Node类

public class Node {
    public long data;
    public Node leftNode;
    public Node rightNode;

    Node(long value){
        this.data = value;
    }
}

接下来是二叉树,有一个根节点root

1、插入节点图示

2、删除节点

2.1 删除的节点没有子节点

2.2 删除的节点有一个子节点

2.2.1删除节点的左节点为空
(1)删除节点的右节点为空,删除的节点为右节点

(2)删除节点的右节点为空,删除的节点为左节点

2.2.2删除节点的左节点为空

(1)删除节点的左节点为空,删除的节点为左节点

(2)删除节点的左节点为空,删除的节点为左节点

2.3删除节点有两个子节点

3、 参考代码

package tree;

public class Tree {
    public Node root;
    public void insert(long value){//中序插入节点
        //封装节点
        Node newNode = new Node(value);
        //创建一个当前节点
        Node currentNode = root;
        //父节点
        Node parent;
        if (root==null){//第一次插入
            root = newNode;
            return;
        }else {
            while (true) {
                //因为插入时需要父节点指向,这里需要记录下parent节点
                parent = currentNode;
                if (value < currentNode.data) {//值比当前节点小,则往左走
                    currentNode = currentNode.leftNode;
                    if (currentNode==null){//如果当前节点为空,即走到了一个空节点,使用父节点赋值
                        parent.leftNode = newNode;
                        return;
                    }
                } else {//值比当前节点大,则往右走
                    currentNode = currentNode.rightNode;
                    if (currentNode==null){//如果当前节点为空,即走到了一个空节点,使用父节点赋值
                        parent.rightNode = newNode;
                        return;
                    }
                }
            }
        }

    }

    /**
     * 寻找一个节点,若找到返回节点,没有返回null
     * @param value
     * @return
     */
    public Node find(long value){
        Node current = root;

        while (current.data!=value){//循环直到找到当前节点的值等于value
            if (current.data>value){
                current = current.leftNode;
            }else {
                 current = current.rightNode;
            }
            if (current == null){
                return null;
            }
        }
        return current;
    }

    public boolean delete(long value){//删除节点,二叉树难的部分
        //需要使用当前节点进行遍历,记录父亲节点方便指向
        Node current = root;
        Node parent = root;
        //记录下当前是否为左节点
        boolean isLeft = true;
        //1、首先要找到要删除的节点,这里与find()函数类似
        while (current.data!=value){
            parent = current;//这里将当前节点的值赋值给parent,后面current要指向leftNode或rightNode
            if (current.data>value){
                current = current.leftNode;
                isLeft = true;//记录下isLeft的值
            }else {
                current = current.rightNode;
                isLeft = false;//记录下isLeft的值
            }
            if (current==null){
                return false;
            }
        }
        //2、找到要删除的节点为current,接下来要对该节点进行删除
        //2.1删除要分为三种情况:
        //第一种:要删除的节点左右都为null
//                    只需要利用parent与isLeft即可
        if (current.leftNode==null && current.rightNode==null){
            if (current==root) {
                root = null;
            }else if (isLeft){
                parent.leftNode=null;
                return true;
            }else {
                parent.rightNode=null;
                return true;
            }
            //第二种:左节点为空或右节点为空
            //右节点为空,那么左节点必定不为空
        }else if (current.rightNode == null){
            if (current==root){
                root = current.leftNode;
            }else if (isLeft){
                parent.leftNode = current.leftNode;
                //删除的节点是左节点,把删除节点的左节点赋值给parent的左节点,见图1
            }else {
                parent.rightNode = current.leftNode;
                //删除的节点是右节点,把删除节点的左节点赋值给parent的右节点,见图2
            }
            //左节点为空,那么右节点必定不为空
        }else if (current.leftNode == null){
            if (current==root){
                root = current.rightNode;
            }else if (isLeft){
                parent.leftNode = current.rightNode;
                //删除的节点是左节点,把删除节点的右节点赋值给parent的左节点,见图3
            }else {
                parent.rightNode = current.rightNode;
                //删除的节点是右节点,把删除节点的右节点赋值给parent的右节点,见图4
            }
        }else {
            //第三种:删除的节点有两个子节点
            Node successor = getSuccessor(current);
            //1、先找到successor节点即要替换的节点
            if (successor == root){
                root = successor;
            }else if (isLeft){
                //如果删除的节点是左边的,也就是说parent缺少了左节点,将替换的节点赋值给parent的左节点
                parent.leftNode = successor;
            }else {
                //如果删除的节点是右边的,也就是说parent缺少了右节点,将替换的节点赋值给parent的右节点
                parent.rightNode = successor;
            }
        }
        return false;
    }

    /**
     * 给定要删除的节点delNode,返回一个替换的节点
     * 替换节点:找到一个比当前节点大的最小节点
     * 换言之,应先查找删除节点的右节点,再查找最左节点,见图5
     * @param delNode
     * @return
     */
    public Node getSuccessor(Node delNode){
        //替换节点
        Node successor = delNode;
        //替换节点的父节点
        Node successorParent = delNode;
        //用于遍历的当前节点,初始值为删除节点的右节点
        Node current = delNode.rightNode;
        //1、current最左边的节点
        while (current!=null){
            //successorParent记录successor的父节点
            successorParent = successor;
            //successor为当前节点
            successor = current;
            //current左移
            current = current.leftNode;
            //current为null时,successor为current的父节点,successorParent为successor的父节点
        }
        //2、如果替换节点不是删除节点的右节点
        if (successor != delNode.rightNode){
            //successor一定没有左节点了,successorParent就缺少了一个左节点,此时将successor的右节点接给successorParent的左节点
            successorParent.leftNode = successor.rightNode;
            //把删除节点的右节点赋值给successor的右节点
            successor.rightNode = delNode.rightNode;
        }
        //无论替换节点是不是删除节点的右节点,替换节点的左节点都要指向删除节点的左节点
            successor.leftNode = delNode.leftNode;
        return successor;
    }
    public void firstOrder(Node local){
        if (local==null)return;
        //中左右
        System.out.print(local.data+" ");
        firstOrder(local.leftNode);
        firstOrder(local.rightNode);
    }
    public void beforeOrder(Node local){
        if (local==null){return;}
        //左中右
        beforeOrder(local.leftNode);
        System.out.print(local.data+" ");
        beforeOrder(local.rightNode);
    }
    public void laterOrder(Node local){
        if (local==null){return;}
        //左右中
        laterOrder(local.leftNode);
        laterOrder(local.rightNode);
        System.out.print(local.data+" ");
    }
}


4、测试类


public class TestTree {
        public static void main(String[] args) {
            Tree tree = new Tree();
            tree.insert(30);
            tree.insert(50);
            tree.insert(20);
            tree.insert(15);
            tree.insert(25);
            tree.insert(35);
            tree.insert(55);
            tree.insert(10);
            tree.insert(18);
            tree.insert(21);
            tree.insert(27);
            tree.insert(33);
            tree.insert(40);
            tree.insert(51);
            tree.insert(60);

            System.out.println("前序遍历");
            tree.firstOrder(tree.root);
            System.out.println();
            System.out.println("中序遍历");
            tree.beforeOrder(tree.root);
            System.out.println();
            System.out.println("后序遍历");
            tree.laterOrder(tree.root);
            System.out.println();

            // 删除有两个子节点的
            System.out.println("删除20:");
            tree.delete(20);
            tree.beforeOrder(tree.root);
            System.out.println();
            System.out.println("删除50:");
            tree.delete(50);
            tree.beforeOrder(tree.root);System.out.println();
            System.out.println("删除35:");
            tree.delete(35);
            tree.beforeOrder(tree.root);System.out.println();
            System.out.println("删除55:");
            tree.delete(55);
            tree.beforeOrder(tree.root);System.out.println();
            System.out.println("删除15:");
            tree.delete(15);
            tree.beforeOrder(tree.root);System.out.println();
            System.out.println("删除25:");
            tree.delete(25);
            tree.beforeOrder(tree.root);System.out.println();
        }
}

5、测试结果