二叉查找树的搜索、插入、删除、遍历等操作

节点结构，每个节点保存left节点 & right节点，以及当前节点的数据

public class TreeNode {
    private int data;
    private TreeNode leftChirld;
    private TreeNode rightChirld;

    public TreeNode(int val){
        this.data = val;
    }
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public TreeNode getLeftChirld() {
        return leftChirld;
    }
    public void setLeftChirld(TreeNode leftChirld) {
        this.leftChirld = leftChirld;
    }
    public TreeNode getRightChirld() {
        return rightChirld;
    }
    public void setRightChirld(TreeNode rightChirld) {
        this.rightChirld = rightChirld;
    }

}

二叉树结构

public class BinaryTree {
    private TreeNode root;
    private int size;

搜索，使用递归

    public TreeNode find(int val){
        return find(root, val);
    }

/**
     * 利用递归查找节点，如果没有则为null
     * @param node
     * @param val
     * @return
     */
    private TreeNode find(TreeNode node, int val){
        TreeNode cur = node;
        if (cur == null || val == cur.getData()){
            return cur;
        }

        if (val < cur.getData()){
            return find(cur.getLeftChirld(), val);
        }else if (val > cur.getData()){
            return find(cur.getRightChirld(),val);
        }

        return null;
    }

插入操作，写的比较繁琐

public void insert(int val){
        //Add a new node when there is no node
        if (root == null){
            root = new TreeNode(val);
        }else {
            TreeNode cur = root;

            //如果val大于某个节点，并且节点的子节点不为空，遍历子节点的节点，否则新建一个节点
            while (cur != null){
                if (val < cur.getData() && cur.getLeftChirld() == null){
                    size++;
                    cur.setLeftChirld(new TreeNode(val));
                    break;
                }else if (val < cur.getData() && cur.getLeftChirld() != null){
                    cur = cur.getLeftChirld();
                }

                if (val > cur.getData() && cur.getRightChirld() == null){
                    size++;
                    cur.setRightChirld(new TreeNode(val));
                    break;
                }else if (val > cur.getData() && cur.getRightChirld() != null){
                    cur = cur.getRightChirld();
                }

                if (val == cur.getData()){
                    cur.setData(val);
                    break;
                }
            }

        }
    }

删除
考虑三种情况、要删除的节点没有子节点、要删除的节点只有左节点或者右节点、要删除的节点有两个节点

public void delete(int val){
        TreeNode cur = root;
        TreeNode prev = null;

        while (cur != null && cur.getData() != val){
            prev = cur;
            if (val < cur.getData()){
                cur = cur.getLeftChirld();
            }else{
                cur = cur.getRightChirld();
            }
        }

        if (cur == null){
            return;
        }

        //如果节点的左右节点不为空，找到右节点的最小节点，将它替换到当前要删除的节点。
        if (cur.getLeftChirld() != null && cur.getRightChirld() != null){
            //find the smallest node of right subtree
            TreeNode rightNodeParent = cur;
            TreeNode rightNode = cur.getRightChirld();
            while (rightNode.getLeftChirld() != null){
                rightNodeParent = rightNode;
                rightNode = rightNode.getLeftChirld();
            }

            if (rightNode == null){
                rightNode = rightNodeParent;
            }

            cur.setData(rightNode.getData());
            rightNodeParent.setLeftChirld(null);
            cur.setRightChirld(rightNodeParent);
        }


        //处理只有一个子节点或者没有子节点的情况
        TreeNode child;
        if(cur.getLeftChirld() != null){
            child = cur.getLeftChirld();
        }else if (cur.getRightChirld() != null){
            child = cur.getRightChirld();
        }else {
            child = null;
        }

        if (prev == null){
            root = child;
        }else if (prev.getLeftChirld() == cur){
            prev.setLeftChirld(child);
        }else {
            prev.setRightChirld(child);
        }
    }

比如我删除51，而有两个节点的情况： 7533C72CA07126E904558905915B5534.png

//后序遍历
public void postOrder(TreeNode treeNode){
        if (treeNode == null){
            return;
        }

        postOrder(treeNode.getLeftChirld());
        postOrder(treeNode.getRightChirld());
        System.out.println(treeNode.getData());
    }

  //中序遍历
    void inOrder(TreeNode treeNode){
        if (treeNode == null){
            return;
        }

        inOrder(treeNode.getLeftChirld());
        System.out.println(treeNode.getData());
        inOrder(treeNode.getRightChirld());
    }

    //前序遍历
    void preOrder(TreeNode treeNode){
        if (treeNode == null){
            return;
        }

        System.out.println(treeNode.getData());
        preOrder(treeNode.getLeftChirld());
        preOrder(treeNode.getRightChirld());
    }