二叉树

本文为数据结构与算法之美的学习笔记，如需学习完整内容，请参考链接，禁止转载。

树

树的直观表现如下图所示：

将树中的每个元素称为“节点”；相邻节点之间的关系被称为“父子关系”。如下图所示，A节点是B节点的父节点，B节点是A节点的子节点，B、C、D的父节点相同，因而这三个节点被称为兄弟节点。将没有父节点的节点称作根节点，即E节点。没有子节点的节点称作叶子节点，如图中的G、H、I等。

对于树来说，还要以下三个概念：

举例如下：

二叉树

树中最常用的结构是二叉树。

二叉树即每一个节点最多有两个子节点，分别是左子节点和右子节点。但，二叉树不要求每一个节点都有两个子节点。

在上图中，第二棵树的叶子节点都在最底层，且除了叶子节点之外，每个节点都有左右两个子节点，该二叉树被成为满二叉树。

而第三棵树的叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，且除了最后一层，其它层的节点的子节点的个数都是两个，这种二叉树被称为完全二叉树。

区分完全二叉树要把握住三个要点：

叶子节点都在最底下两层；
最后一层的叶子节点都靠左排列；
除了最后一层，其它层的节点的子节点的个数都是两个。

举例如下：

那么为何会有完全二叉树这种看似奇怪的二叉树存在？

首先需要了解二叉树的存储方式。有两种方法，一种是基于指针或引用的二叉链式存储法，一种是基于数组的顺序存储法。

在链式存储法中，链表中的每一个节点都有三个字段，其中一个为当前节点存储的数据，另外两个分别存储指向左右子节点的指针。大部分的二叉树都是通过这种存储方式实现的。

而在顺序存储法中，将根节点存储在下标为i=1的位置，其左子节点存储在2*i=2的位置，右子节点存储在2*i+1=3的位置。其他节点的存储方式以此类推。如下图所示。

这样，在顺序存储法中，只要知道根节点的位置（为了计算方便，根节点会被存储在下标为1的位置），就可以使用公式计算出其它节点的位置。

在这种情况下，当二叉树是完全二叉树时，就只会浪费下标为0的位置，而对于非完全二叉树，就会浪费很多的存储空间。

因而，当二叉树为完全二叉树时，使用数组进行存储将是最节省内存的方式。这就是完全二叉树特殊的地方。

二叉树的遍历

在对二叉树进行遍历时，一般有三种策略：

前序遍历：对于树中的任意结点，先打印该结点，再打印它的左子树，最后打印它的右子树。
中序遍历：对于树中的任意结点，先打印该结点，再打印它的左子树，最后打印它的右子树。
后序遍历：对于树中的任意结点，先打印它的左子树，再打印它的右子树，最后打印该结点。

上述过程就是递归的过程，写出递归公式如下：

前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

将其写为代码，如下：

void preOrder(Node* root) {
  if (root == null) return;
  print root // 此处为伪代码，表示打印root节点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此处为伪代码，表示打印root节点
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此处为伪代码，表示打印root节点
}

二叉树的遍历算法的时间复杂度为$O(n)$。

二叉查找树（Binary Search Tree）

二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。然而散列表也支持这些操作，且更为高效，时间复杂度为$O(1)$。那么为何还需要二叉查找树？

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

那么，二叉查找树是如何实现快速查找、插入和删除操作的？

二叉查找树的查找操作

在二叉查找树中查找一个节点，先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

二叉查找树的代码实现如下：

struct Node
{
    int data;
    Node *left = nullptr;
    Node *right = nullptr;
};


class BinarySearchTree {
public:
    BinarySearchTree() : num(0)
    {
        root = new Node;
        root -> left = nullptr;
        root -> right = nullptr;
    }

    bool find(int item, Node *root)
    {
        if (root == nullptr)
            return false;
        else if (root -> data == item)
            return true;
        else if (item < root -> data)
            return find(item, root -> left);
        else
            return find(item, root -> right);
    }
private:
    Node *root;
    int num;
};

二叉查找树的插入操作

新插入的数据一般都在叶子结点上，因而需要从根节点开始依次比较要插入的数据和节点的大小关系。

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

代码如下：

/*
* 向二叉查找树中插入新的元素
* */
void insert(int item, Node *root)
{
    if (num == 0){
        // 如果当前树中不存在节点，则将元素放入根节点中
        root->data = item;
        num++;
        return;
    }
    if (item < root->data){
        // 如果元素比当前结点处的值小，则插入到左子树中
        if (root->left == nullptr){
            root->left = new Node;
            root->left->data = item;
            num++;
            return;
        }else{
            return insert(item, root->left);
        }
    }else {
        // 否则插入到右子树中
        if (root->right == nullptr) {
            root->right = new Node;
            root->right->data = item;
            num++;
            return;
        } else {
            return insert(item, root->right);
        }
    }
}

二叉查找树的删除操作

二叉查找树的节点删除操作相对来说比较复杂，要分情况讨论。

当要删除的节点不存在子节点时，直接删除即可；
当要删除的节点存在一个子节点（只有左子节点或者又子节点）时，将要删除的节点的父节点中指向要删除的节点的指针指向要删除的节点的子节点即可；
当要删除的节点存在左右两个子节点时，这是最复杂的情况。首先，我们需要找到右子节点中最小的那个节点，接着，使用该最小节点替换掉需要删除的节点，最后将该最小节点删除（该最小的节点肯定不存在左子节点，因而可以利用上述两条规则将该节点删除）。如下图所示，假设要删除节点18.

代码如下：

bool delete_data(int item)
{
    if (root == nullptr)
        return false;
    Node *current_root = root;
    Node *deleted_node = nullptr;
    Node *parent_node = nullptr;
    // 查找需要删除的节点
    while(current_root != nullptr){
        if (item == current_root->data) {
            deleted_node = current_root;
            break;
        }
        else if (item < current_root->data) {
            parent_node = current_root;
            current_root = current_root->left;
        }else {
            parent_node = current_root;
            current_root = current_root->right;
        }
    }
    if (deleted_node == nullptr)
        return false;
    // 左右节点都不为空
    if (deleted_node->left != nullptr && deleted_node->right != nullptr){
        // 找到右子树中最小的节点
        Node *min_node = deleted_node->right;
        Node *min_node_parent = deleted_node;
        while (min_node != nullptr){
            if (min_node->left != nullptr) {
                min_node_parent = min_node;
                min_node = min_node->left;
            }else
                break;
        }
        min_node_parent->left = nullptr;
        if (parent_node->left == deleted_node)
            parent_node->left = min_node;
        else
            parent_node->right = min_node;
        delete(deleted_node);
    }
    // 当待删除节点无子节点时，直接删除
    if (deleted_node->left == nullptr && deleted_node->right == nullptr) {
        if (parent_node == nullptr)
            // 父节点为空，则说明删除的节点是根节点，直接删除即可
            delete (deleted_node);
        else {
            // 删除节点之前要将父节点指向该节点的指针置空
            if (parent_node->left == deleted_node)
                parent_node->left = nullptr;
            else
                parent_node->right = nullptr;
            delete (deleted_node);
        }
    }else{
        Node *temp = nullptr;
        if (deleted_node->left != nullptr)
            temp = deleted_node->left;
        else
            temp = deleted_node->right;
        if (parent_node->left == deleted_node)
            parent_node->left = temp;
        else
            parent_node->right = temp;
    }
    return true;
}

除此之外，二叉查找树还支持快速查找最大、最小节点、前驱节点和后继节点。同时，如果对二叉查找树进行中序遍历，会得到一个有序的序列，时间复杂度为$O(n)$。因此，二叉查找树又成为二叉排序树。

支持重复数据的二叉查找树

当所要存储的数据中存在重复数据时，就要进行特殊处理。有以下两种处理方法：

在二叉查找树的每一个节点处存放链表和支持动态扩容的数组等数据结构，将相同数值的数据存储在同一个节点上。
每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。

当要查找数据的时候，遇到值相同的节点，不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。

对于删除操作，也要找到所有值相同的节点，并使用上面所说的删除方法依次删除各个节点。

二叉查找树的时间复杂度分析
对于不同形状的二叉查找树，有着不同的插入、删除和查找时间复杂度。如下图所示：

最左侧的二叉查找树退化为了普通的链表，因而查找时间复杂度为$O(n)$。

那么，当二叉查找树为一棵完全二叉树（或者满二叉树）时，时间复杂度是多少？

其实，不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 $O(height)$。问题就转换为求一棵包含n个节点的完全二叉树的高度。

树的高度就等于最大层数减一，为了方便计算，我们转换成层来表示。从图中可以看出，包含 n 个节点的完全二叉树中，第一层包含 1 个节点，第二层包含 2 个节点，第三层包含 4 个节点，依次类推，下面一层节点个数是上一层的 2 倍，第 K 层包含的节点个数就是 2^(K-1)。

但是，完全二叉树的最后一层的节点数目不完全遵守上述规律。其包含的节点数目在1到$2^{(L-1)}$个。令每一层的节点个数之和为总节点个数，那么：

1 2	n >= 1+2+4+8+...+2^(L-2)+1 n <= 1+2+4+8+...+2^(L-2)+2^(L-1)

借助等比数列的求和公式，可以计算出，L 的范围是 $[log2(n+1), log2n +1]$。完全二叉树的层数小于等于 $log2n +1$，也就是说，完全二叉树的高度小于等于$log2n$。

因而，当二叉查找树的节点分布较为平衡时，其插入、删除、查找操作的时间复杂度也比较稳定，是$O(logn)$。

总结

那么，既然散列表的插入、删除、查找操作的时间复杂度可以做到常量级的$O(1)$，为何还需要二叉查找树？原因有以下几点：

散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

因而，在某些方面，平衡二叉查找树的性能要优于散列表，具体使用那个要视实际工程而定。

参考

数据结构与算法之美

二叉树

树

二叉树