vlambda博客
学习文章列表

多日不见，朋友们还记得什么是二叉树吗？

什么是二叉查找树

在树的任意一个节点，左子树中每个节点的值都要小于这个节点，右子树中每个节点的值都要大于这个节点，这就是二叉查找树。

查找操作

从根节点开始，如果比根节点的值小，就查询它的左子树；

如果比根节点的值大，就查询它的右子树；

如果等于我们要查找的数据，就返回这个节点元素；

按照这种逻辑，依次往下递归查询，最后到叶子节点都没有查到类似的数据，则表示数据不存在。

查找一个节点可以使用递归查询，也可以使用循环查询，一般建议使用循环操作，假设树变成一个链表，递归过深的时候，很容易出现stackoverflow 的异常。

public class BinarySearchTree {
    // 根节点
    private Node root;

    /**
     * 循环实现方法
     * 
     * @param value 要查找的值
     * @return 查找结果
     */
    public Node find(int value) {
        Node node = root;
        while (root != null) {
            if (node.value == value) {
                return node;
            }
            if (node.value > value) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return null;
    }

    /**
     * 递归实现方法
     * 
     * @param node 起始节点，一般为根节点
     * @param value 要查找的值
     * @return 查找结果
     */
    public Node find2(Node node, int value) {
        if (node == null) {
            return null;
        }
        if (node.value > value) {
            return find2(node.right, value);
        } else if (node.value < value) {
            return find2(node.left, value);
        } else {
            return node;
        }
    }

    public class Node {
        private int value;
        private Node left;
        private Node right;

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

插入操作

插入和查询的操作很类似，一般把新插入的节点放到叶子节点。类似查询的操作方式，查找元素应该插入的位置。

1. 需要判断根节点是否为空，为空，则添加为根节点

2. 如果根节点不为空，则与根节点对比大小

3. 如果比根节点大，则从右子树继续查找

4. 如果比根节点小，则从左子树继续查找

5. 插入的条件：判断当前节点是否还有左/右节点，如果没有，则插入当前节点的左/右节点位置。

public void insert(int value) {
    Node node = root;
    if (node == null) {
        node = new Node(value);
        return;
    }

    while (node != null) {
        if (node.value > value) {
            if (node.right == null) {
                node.right = new Node(value);
                return;
            }
            node = node.right;
        } else {
            if (node.left == null) {
                node.left = new Node(value);
                return;
            }
            node = node.left;
        }
    }

删除操作

标记删除法：使用类似散列表中添加标记的删除方法，当一个数据删除以后，我们把它标记为已删除，数据并不会真的从内存中清理掉，这时候比较浪费内存。

还可以在查找的基础上进行改造，先查询节点所在位置，然后对其进行删除。

• 待删除节点为叶子节点，直接设置节点为null即可。

• 待删除节点只有一个子节点，让待删除节点的父节点指向待删除节点的子节点即可。

• 待删除节点有两个节点，删除节点以后，我们需要一个子节点填在删除的位置上，可以在它的左子树查找一个最大值，或者在右子树查找一个最小值。这个值一般在叶子节点，我们移动到删除节点位置即可。

编码思路

1. 查询待删除的节点以及其父节点

2. 判断节点是否为空，为空表示不存在

3. 假设有两个节点，找出右子树中最小节点，替换待删除节点，然后把要删除的情况转化成叶子节点

4. 假设删除的节点是叶子节点或者仅有一个子节点，或者待删除节点的子节点

5. 使待删除节点的父节点指向待删除节点的子节点。

public void delete(int value) {
    Node delNode = tree;//要删除的节点
    Node pDelNode = null;// 要删除节点的父节点
    // 1.查找要删除节点，以及其父节点
    while (delNode != null && delNode.value != value) {
        pDelNode = delNode;
        if (delNode.value > value) {
            delNode = delNode.left;
        } else {
            delNode = delNode.right;
        }
    }
    // 要删除的节点不存在时
    if (delNode == null) {
        return;
    }
    // 2.假设待删除节点有两个子节点，查询出右子树最小节点
    if (delNode.left != null && delNode.right != null) {
        Node miniRight = delNode.right;
        Node pMiniRight = miniRight;
        while (miniRight.left != null) {
            pMiniRight = miniRight;
            miniRight = miniRight.left;
        }
        // 两个节点的情况转化成 待删除节点为叶子节点，父节点为叶子节点的父节点
        delNode.value = miniRight.value;
        delNode = miniRight;
        pDelNode = pMiniRight;
    }
    // 3. 假设待删除节点只有一个子节点，获取删除节点的子节点
    Node child;
    if (delNode.left != null) {
        child = delNode.left;
    } else if (delNode.right != null) {
        child = delNode.right;
    } else {
        // 如果两个子节点都是空，表示要删除的节点是叶子节点
        child = null;
    }

    // 设置父节点的后继节点，删除节点
    if (pDelNode == null) {
        // 删除根节点，只有一个根节点的情况
        tree = null;
    } else if (pDelNode.right == delNode) {
        pDelNode.right = child;
    } else {
        pDelNode.left = child;
    }
}

其他

中序遍历二叉树，可以输出有序的数据序列，时间复杂度为O(n)

包含重复数据的二叉树

一、使用链表或者数组存储相同的数据，然后存放到节点中

二、把和某节点相同的值当做大于这个节点的值来处理。数据插入到这个节点的右子树。查找数据的时候，遇到值相同的节点，接着去右子树中查找数据，停止查找的条件变为遇到叶子节点。删除的时候也需要遍历右子树节点处理。

时间复杂度

二叉查找树退化成链表时，查找的时间复杂度为O(n)

如果二叉树是一个完全二叉树时，时间复杂度跟输的高度成正比，O(height)，使用层数做计算，假设层数为 k 。第一层包含1个节点，第二层包含2个节点，第三层包含4个节点，下面一层节点个数是上一层的2倍，第 k 层包含的节点个数是 2^(k-1)

假设节点个数为n，最大层数为k
n >= 1+2+4+8+……+2^(k-2)
n <= 1+2+4+8+……+2^(k-2)+2^(k-1)

所以 k 的范围是 [log2(n+1), log2(n)+1]，完全二叉树的层数小于等于log2(n)+1，高度小于等于log2(n)，最好的时间复杂度为O(logn)。平衡二叉树的时间复杂度可以做到稳定的O(logn)