簡(jiǎn)介

二叉查找樹（Binary Search Tree），又被成為二叉搜索樹卢鹦。
它是特殊的二叉樹：對(duì)于二叉樹臀脏，假設(shè)x為二叉樹中的任意一個(gè)節(jié)點(diǎn)，x節(jié)點(diǎn)包含關(guān)鍵字key，節(jié)點(diǎn)x的key值記為key[x]揉稚。如果y是x的左子樹中的一個(gè)節(jié)點(diǎn)秒啦，則key[y]<key[x];如果y是x的右子樹的一個(gè)節(jié)點(diǎn)，則key[y]>key[x]窃植。那么帝蒿，這棵樹就是二叉查找樹。如圖

image.png

在二叉查找樹中：

1. 若任意節(jié)點(diǎn)的左子樹不空巷怜，則左子樹上所有節(jié)點(diǎn)的值均小于他的根節(jié)點(diǎn)的值葛超；
2. 若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值延塑；
3. 任意節(jié)點(diǎn)的左绣张、右子樹也分別為二叉查找樹；
4. 沒有鍵值相等的節(jié)點(diǎn)关带。

遍歷

這里講解前序遍歷侥涵、中序遍歷和后續(xù)遍歷3中方式。

1. 前序遍歷
   若二叉樹非空宋雏，則執(zhí)行以下操作：

• 訪問根節(jié)點(diǎn)
• 先序遍歷左子樹
• 先序遍歷右子樹

2. 中序遍歷
   若二叉樹非空芜飘，則執(zhí)行以下操作：

• 中序遍歷左子樹
• 訪問根節(jié)點(diǎn)
• 中序遍歷右子樹

3. 后序遍歷
   若二叉樹非空，則執(zhí)行以下操作：

• 后序遍歷左子樹
• 后序遍歷右子樹
• 訪問根節(jié)點(diǎn)

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; //保存樹的根

    /**
     * 查找指定節(jié)點(diǎn)
     */
    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;
    }

    /**
     * 插入節(jié)點(diǎn)
     */
    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;
        }
    }

    /**
     * 刪除指定節(jié)點(diǎn)
     */
    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) { //要?jiǎng)h除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)
                root = null;
            } else if (isLeftChild) {
                parentNode.leftChild = null;
            } else {
                parentNode.rigthChild = null;
            }
        } else if (currentNode.rigthChild == null) { //要?jiǎng)h除的節(jié)點(diǎn)只有左孩子
            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 {
            //要?jiǎng)h除的節(jié)點(diǎn)既有左孩子又有有孩子
            //思路:用待刪除節(jié)點(diǎn)右子樹中的key值最小的節(jié)點(diǎn)的值來替代要?jiǎng)h除的節(jié)點(diǎn)的值,然后刪除右子樹中key值最小的節(jié)點(diǎn)
            //右子樹key最小的節(jié)點(diǎn)一定不含左子樹,所以刪除這個(gè)key最小的節(jié)點(diǎn)一定是屬于葉子節(jié)點(diǎn)或者只有右子樹的節(jié)點(diǎn)
            Node directPostNode = getDirectPostNode(currentNode);
            currentNode.key = directPostNode.key;
            currentNode.value = directPostNode.value;
        }
        return true;
    }

    /**
     * 得到待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)
     */
    private Node getDirectPostNode(Node delNode) {
        Node parentNode = delNode;//用來保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)的父親節(jié)點(diǎn)
        Node directPostNode = delNode; //用來保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)
        Node currentNode = delNode.rigthChild;
        while (currentNode != null) {
            parentNode = directPostNode;
            directPostNode = currentNode;
            currentNode = currentNode.leftChild;
        }

        if (directPostNode != delNode.rigthChild) { //從樹中刪除此直接后繼節(jié)點(diǎn)
            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);
        }
    }
}