二叉查找树的综合应用

一 需求

实现二叉查找树的搜索、插入、删除操作。

二 代码

package bst;

import java.util.Scanner;

public class BST {
    static int ENDFLAG = -1;
    // 二叉排序树的递归查找
    static public TreeNode search(TreeNode root, int val) {
        // 若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
        if ((root == null) || val == root.val)
            return root;
        else if (val < root.val)
            return search(root.left, val); // 在左子树中继续查找
        else
            return search(root.right, val); // 在右子树中继续查找
    }

    // 二叉排序树的插入
    static public TreeNode Insert(TreeNode root, int val) {
        if (root == null) {
            // 树为空树的情况
            return new TreeNode(val);
        }
        // 一个临时节点指向根节点，用于返回值
        TreeNode tmp = root;
        TreeNode pre = root;


        while (root != null && root.val != val) {
            // 保存父节点
            pre = root;
            if (val > root.val) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        // 通过父节点添加
        if (val > pre.val) {
            pre.right = new TreeNode(val);
        } else {
            pre.left = new TreeNode(val);
        }
        return tmp;
    }

    // 二叉排序树的创建
    static TreeNode CreateBST(TreeNode node) {
        Scanner scanner = new Scanner(System.in);
        // 依次读入一个关键字为key的结点，将此结点插入二叉排序树T中
        int e;
        e = scanner.nextInt();
        while (e != ENDFLAG) // ENDFLAG为自定义常量，作为输入结束标志
        {
            node = Insert(node, e);  // 插入二叉排序树T中
            e = scanner.nextInt();
        }
        return node;
    }

    // 二叉排序树的删除
    static public TreeNode DeleteBST(TreeNode root, int key) {
        TreeNode tmp = root;
        TreeNode pre = root;
        // 寻找要删除的节点
        while (root != null && root.val != key) {
            pre = root;
            if (key > root.val) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        // 找不到符合的节点值
        if (root == null) {
            return tmp;
        }
        // 只有一个子节点或者没有子节点的情况
        if (root.left == null || root.right == null) {
            if (root.left == null) {
                // 要删除的是根节点，返回它的子节点
                if (root == tmp) {
                    return root.right;
                }
                // 使用父节点连接子节点，实现删除当前节点
                if (pre.left == root) {
                    pre.left = root.right;
                } else {
                    pre.right = root.right;
                }
            } else {
                if (root == tmp) {
                    return root.left;
                }
                if (pre.left == root) {
                    pre.left = root.left;
                } else {
                    pre.right = root.left;
                }
            }
            return tmp;
        }

        // 寻找中序遍历的后一个节点，也就是右子树进行中序遍历的第一个节点，右子树的最左节点
        pre = root;
        TreeNode rootRight = root.right;
        while (rootRight.left != null) {
            pre = rootRight;
            rootRight = rootRight.left;
        }

        // 节点的值进行交换
        int tmpVal = rootRight.val;
        rootRight.val = root.val;
        root.val = tmpVal;

        // 中序遍历的第一个节点肯定是没有左子树的，但是可能有右子树，将右子树连接到父节点上（相当于删除有一个子节点的节点）
        if (pre.left == rootRight) {
            pre.left = rootRight.right;
        } else {
            pre.right = rootRight.right;
        }


        return tmp;
    }


    // 中序遍历
    static public void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            preorder(root.left);
        }
        System.out.print(root.val + " ");
        if (root.right != null) {
            preorder(root.right);
        }
    }

    public static void main(String[] args) {
        TreeNode node = null;
        System.out.println("请输入一些整型数，-1结束");
        node = CreateBST(node);
        System.out.println("当前有序二叉树中序遍历结果为");
        preorder(node);
        System.out.println();
        int key; // 待查找或待删除内容
        System.out.println("请输入待查找关键字");
        Scanner scanner = new Scanner(System.in);
        key = scanner.nextInt();
        TreeNode result = search(node, key);
        if (result != null)
            System.out.println("找到" + key);
        else
            System.out.println("未找到" + key);
        key = scanner.nextInt();
        DeleteBST(node, key);
        System.out.println("当前有序二叉树中序遍历结果为");
        preorder(node);
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;


    TreeNode(int val) {
        this.val = val;
    }
}

三 测试

绿色为输入，白色为输出。