二叉查找树

二叉查找树（BST：Binary Search Tree）是一种特殊的二叉树，改善二叉树节点的查找效率。

特性：

其左子树下的每个后代节点的值都小于节点n的价值；

其右子树下的每个后代节点的值都大于节点n的值；

原理理论

从二叉查找树的性质可知，BST 各节点存储的数据必须能够与其他的节点进行比较。给定任意两个节点，BST 必须能够判断这两个节点的值是小于、大于还是等于。

BST算法极度依赖树的拓扑结构，如果生成的结构是线性的就是这颗树没有广度可言，那其实他的算法复杂度和数组一样都是O(n). 如果根节点正好在中间那么最佳的结果就是O(log2(n)).

---

二叉树的插入节点

BST 的插入算法的复杂度与查找算法的复杂度是一样的：最佳情况是 O(log­2n)，而最坏情况是 O(n)。因为它们对节点的查找定位策略是相同的。

---

二叉树的输出节点

从 BST 中删除节点比插入节点难度更大。

删除一个非叶子节点，就必须选择其他节点来填补因删除节点所造成的树的断裂。

删除节点算法的第一步是定位要被删除的节点, 运行时间为 O(log­2n).

需要考虑三种情况来代替删除节点的位置：

• 删除节点没有左节点 有右节点 或者 有左节点 没有右节点 ，可以直接用右/左节点代替删除节点位置
• 删除节点有左右节点，就需要用被删除节点的右节点的左节点的最下左节点来替换，或者是左节点的右节点的最下右节点替换。 其实就是左右2树的最大值和最小值进行替换。

和查找、插入算法类似，删除算法的运行时间也与 BST 的拓扑结构有关，最佳情况是 O(log­2n)，而最坏情况是 O(n)。

---

二叉树的遍历查询

对于二叉树的遍历通常采用三种遍历方式：

• 前序遍历 Perorder traversal
• 中序遍历 Inorder traversal
• 后序遍历 Postorder traversal

前序遍历

​ 前序遍历的规则是先重复访问其左节点，在访问其右节点。

​ 上图中树的遍历结果为：90 50 20 5 25 75 66 80 150 95 92 111 175 166 200

​ 可以想象成/////方式的遍历读取

中序遍历

​ 中序遍历的规则是先访问左节点再访问自身最后访问右节点。

​ 上图中树的遍历结果为：5 20 25 50 66 75 80 90 92 95 111 150 166 175 200

后序遍历

​ 后序遍历的规则是先访问左节点再访问右节点最后访问自身节点

​ 上图中树的遍历结果为：5, 25, 20, 66, 80, 75, 50, 92, 111, 95, 166, 200, 175, 150, 90

代码实现

package com.example.demo;

import lombok.Data;

import java.util.ArrayList;
import java.util.List;

/**
 * Create With: demo
 * Create By: kole
 * Date: 2019/4/4
 */
@Data
public class BinartTree<T extends Comparable> {
    @Data
    class Node<T extends Comparable>{
        public Node (T data, Node parent, Node left, Node right) {
            this.setParent(parent);this.setLeft(left);this.setRight(right); this.setData(data);
        }
        private Node<T> parent;
        private Node<T> left;
        private Node<T> right;
        private T data;

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }

    // 二叉树的根节点
    private Node<T> root;
    // 节点计数器
    private int nodeCount = 0;

    // 返回最后一个关联节点
    private Node findLastNode(T data, boolean searchStop) {
        if (this.getRoot() == null) throw new RuntimeException("node root data is null");
        Node current = this.getRoot();
        for (;;) {
            if (current.getData() == null) throw new RuntimeException("node data is null");

            switch (current.getData().compareTo(data)){
                case 1:
                    if (current.getLeft() == null) return current;
                    current = current.getLeft();
                    break;
                case 0:
                    if (searchStop) return current;
                case -1:
                    if(current.getRight() == null) return current;
                    current = current.getRight();
                    break;
                default:
                    throw new RuntimeException("undefined number of type");
            }
        }
    }
    // -------------------- 查找
    // 查找目标节点
    public Node find(T data) {
        if (data == null) throw new IllegalArgumentException("data is null");

        Node lastNode = this.findLastNode(data, true);
        if (lastNode.getData().compareTo(data) == 0) return lastNode;

        return null;
    }
    // -------------------- /查找

    // -------------------- 添加
    // 插入二叉树中
    public BinartTree add(T data) {
        if (data == null) throw new IllegalArgumentException("data is null");

        try {
            // 加入根节点
            if (this.getRoot() == null) {
                this.setRoot(new Node<>(data, null, null, null));
                return this;
            }

            Node lastNode = this.findLastNode(data, false);

            switch (lastNode.getData().compareTo(data)){
                case 1:
                    lastNode.setLeft(new Node(data, lastNode, null, null));
                    break;
                case 0:
                case -1:
                    lastNode.setRight(new Node(data, lastNode, null, null));
                    break;
                default:
                    throw new RuntimeException("undefined number of type");
            }
            return this;
        }
        finally {
            this.nodeCount++;
        }
    }
    // -------------------- /添加

    // -------------------- 删除
    public Node delete(T data) {
        Node deleteNode = this.find(data);
        if (deleteNode == null) return null;

        Node parentNode = deleteNode.getParent();
        // 删除节点是上一个节点的左节点还是右节点
        boolean parentNodeLeftSide = false;
        // 替换node
        Node replaceNode = deleteNode;

        if (parentNode != null) {
            // 选择节点位置
            if (parentNode.getRight().getData().compareTo(data) == 0) parentNodeLeftSide = false;
            else if (parentNode.getLeft().getData().compareTo(data) == 0) parentNodeLeftSide = true;
            else throw new RuntimeException("not node");
        }

        // 删除节点为叶子节点
        if (deleteNode.getLeft() == null && deleteNode.getRight() == null) replaceNode = null;
        else if (deleteNode.getRight() == null){ // 有左节点没有右节点
            replaceNode = deleteNode.getLeft();
            deleteNode.setLeft(null);
            replaceNode.setParent(parentNode);
        } else if (deleteNode.getLeft() == null) {
            replaceNode = deleteNode.getRight();
            deleteNode.setRight(null);
            replaceNode.setParent(parentNode);
        } else {
            Node minNode = null;
            boolean minNodeLeftSide = true;
            replaceNode = replaceNode.getRight();
            // 选择左节点最小值
            for(;;) {
                minNode = replaceNode.getLeft();
                if (minNode != null) {
                    replaceNode = minNode;
                    minNodeLeftSide = true;
                    continue;
                }
                minNode = replaceNode.getRight();
                if (minNode != null) {
                    replaceNode = minNode;
                    minNodeLeftSide = false;
                    continue;
                }

                // 解除关系
                if (minNodeLeftSide) replaceNode.getParent().setLeft(null);
                else replaceNode.getParent().setRight(null);
                break;
            }
        }

        // 重设关系
        if (parentNode != null) {
            if (parentNodeLeftSide) parentNode.setLeft(replaceNode);
            else parentNode.setRight(replaceNode);
        }

        // 如果删除父节点
        if (deleteNode.getParent() == null){
            this.setRoot(replaceNode);
        }

        replaceNode.setParent(deleteNode.getParent());
        replaceNode.setRight(deleteNode.getRight());
        replaceNode.setLeft(deleteNode.getLeft());

        if (deleteNode.getRight() != null) deleteNode.getRight().setParent(replaceNode);
        if (deleteNode.getLeft() != null) deleteNode.getLeft().setParent(replaceNode);
        // 删除节点去除关系
        deleteNode.setParent(null);
        deleteNode.setLeft(null);
        deleteNode.setRight(null);



        this.nodeCount--;
        return deleteNode;
    }
    // -------------------- /删除

    // -------------------- 遍历

    // 前序遍历
    public List perorder() {
        List list = new ArrayList(this.getNodeCount());
        this.traverseTree(this.getRoot(), list, new int[] {1, 2, 3});
        return list;
    }

    // 前序遍历
    public List inorder() {
        List list = new ArrayList(this.getNodeCount());
        this.traverseTree(this.getRoot(), list, new int[] {2, 1, 3});
        return list;
    }

    // 后序遍历
    public List postorder() {
        List list = new ArrayList(this.getNodeCount());
        this.traverseTree(this.getRoot(), list, new int[] {2, 3, 1});
        return list;
    }

    // 根据规则读取数据
    private void traverseTree(Node<T> current, List list, int[] order) {
        for (int i = 0; i < order.length; i++) {
            switch (order[i]){
                case 1:
                    list.add(current);
                    break;
                case 2:
                    if (current.getLeft() != null) this.traverseTree(current.getLeft(), list, order);
                    break;
                case 3:
                    if (current.getRight() != null) this.traverseTree(current.getRight(), list, order);
                    break;
                default:
                    throw new RuntimeException("undefined order type");
            }
        }
    }
    // -------------------- /遍历

		// -------------------- 演示
    public static void main(String[] args) {
        BinartTree<Integer> tree = new BinartTree<>();
        	tree.add(90)
            .add(50).add(150)
						.add(20).add(75).add(95)
            .add(175).add(5).add(25)
            .add(66).add(80).add(111)
            .add(166).add(200).add(20);

        // 查找
        System.out.println(tree.find(50));
        System.out.println(tree.find(30));


        // 删除
        System.out.println(tree.delete(151));

        // 遍历
        System.out.println(tree.perorder());
        System.out.println(tree.inorder());
        System.out.println(tree.postorder());
    }
   // -------------------- /演示
}