二叉查找树

简介

二叉查找树（Binary Search Tree），又被成为二叉搜索树。
它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个节点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个节点，则key[y]<key[x];如果y是x的右子树的一个节点，则key[y]>key[x]。那么，这棵树就是二叉查找树。如图

image.png

在二叉查找树中：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于他的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。

遍历

这里讲解前序遍历、中序遍历和后续遍历3中方式。

1. 前序遍历
   若二叉树非空，则执行以下操作：

• 访问根节点
• 先序遍历左子树
• 先序遍历右子树

2. 中序遍历
   若二叉树非空，则执行以下操作：

• 中序遍历左子树
• 访问根节点
• 中序遍历右子树

3. 后序遍历
   若二叉树非空，则执行以下操作：

• 后序遍历左子树
• 后序遍历右子树
• 访问根节点

public class Node {

    public int key;
    public int value;
    public Node leftChild;
    public Node rightChild;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class Tree {

    private Node root; //保存树的根

    /**
     * 查找指定节点
     */
    public Node find(int key) {
        Node currentNode = root;
        while (null != currentNode && currentNode.key != key) {
            if (key < currentNode.key) {
                currentNode = currentNode.leftChild;
            } else {
                currentNode = currentNode.rigthChild;
            }
        }
        return currentNode;
    }

    /**
     * 插入节点
     */
    public void insert(int key, int value) {
        if (null == root) {
            root = new Node(key, value);
            return;
        }

        Node currentNode = root;
        Node parentNode = root;
        boolean isLeftChild = true;
        while (currentNode != null) {
            parentNode = currentNode;
            if (key < currentNode.key) {
                currentNode = currentNode.leftChild;
                isLeftChild = true;
            } else {
                currentNode = currentNode.rigthChild;
                isLeftChild = false;
            }
        }

        Node newNode = new Node(key, value);
        if (isLeftChild) {
            parentNode.leftChild = newNode;
        } else {
            parentNode.rigthChild = newNode;
        }
    }

    /**
     * 删除指定节点
     */
    public boolean delete(int key) {
        Node currentNode = root;
        Node parentNode = root;
        boolean isLeftChild = true;
        while (null != currentNode && currentNode.key != key) {
            parentNode = currentNode;
            if (key < currentNode.key) {
                currentNode = currentNode.leftChild;
                isLeftChild = true;
            } else {
                currentNode = currentNode.rigthChild;
                isLeftChild = false;
            }
        }

        if (currentNode == null) {
            return false;
        }

        if (currentNode.leftChild == null && currentNode.rigthChild == null) {
            if (currentNode == root) { //要删除的节点为叶子节点
                root = null;
            } else if (isLeftChild) {
                parentNode.leftChild = null;
            } else {
                parentNode.rigthChild = null;
            }
        } else if (currentNode.rigthChild == null) { //要删除的节点只有左孩子
            if (currentNode == root) {
                root = currentNode.leftChild;
            } else if (isLeftChild) {
                parentNode.leftChild = currentNode.leftChild;
            } else {
                parentNode.rigthChild = currentNode.leftChild;
            }
        } else if (currentNode.leftChild == null) {
            if (currentNode == root) {
                root = currentNode.rigthChild;
            } else if (isLeftChild) {
                parentNode.leftChild = currentNode.rigthChild;
            } else {
                parentNode.rigthChild = currentNode.leftChild;
            }
        } else {
            //要删除的节点既有左孩子又有有孩子
            //思路:用待删除节点右子树中的key值最小的节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
            //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
            Node directPostNode = getDirectPostNode(currentNode);
            currentNode.key = directPostNode.key;
            currentNode.value = directPostNode.value;
        }
        return true;
    }

    /**
     * 得到待删除节点的直接后继节点
     */
    private Node getDirectPostNode(Node delNode) {
        Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
        Node directPostNode = delNode; //用来保存待删除节点的直接后继节点
        Node currentNode = delNode.rigthChild;
        while (currentNode != null) {
            parentNode = directPostNode;
            directPostNode = currentNode;
            currentNode = currentNode.leftChild;
        }

        if (directPostNode != delNode.rigthChild) { //从树中删除此直接后继节点
            parentNode.leftChild = directPostNode.rigthChild;
            directPostNode.rigthChild = null;
        }
        return directPostNode;
    }

    /**
     * 先序遍历树
     */
    public void preOrder(Node rootNode) {
        if (null != rootNode) {
            System.out.println(rootNode.key + " " + rootNode.value);
            preOrder(rootNode.leftChild);
            preOrder(rootNode.rigthChild);
        }
    }

    /**
     * 中序遍历树
     */
    public void inOrder(Node rootNode) {
        if (null != rootNode) {
            inOrder(rootNode.leftChild);
            System.out.println(rootNode.key + " " + rootNode.value);
            inOrder(rootNode.rigthChild);
        }
    }

    /**
     * 后序遍历树
     */
    public void postOrder(Node rootNode) {
        if (null != rootNode) {
            postOrder(rootNode.leftChild);
            postOrder(rootNode.rigthChild);
            System.out.println(rootNode.key + " " + rootNode.value);
        }
    }
}