数据结构学习笔记｜树

1. 树的概念

之前学习的链表、队列、栈和数组，都是线性的。而树不同，树是由顶点和边组成的。就像下图，每个结点之间可能存在一定的关系：上下存在父子关系，左右存在兄弟关系。

把随意一个结点从树上拿出来单独看，就会发现它构成了一个独立的树。

一个树只有一个根结点，根结点是没有父的结点。

树还有很多术语，只列举现在能用得到的：

• 树的高度：树的高度是其根结点的高度。
• 结点的层：节点的深度+1
• 结点的深度：结点的深度是从树的根结点到该结点的边的个数。
• 结点的高度：结点的高度是该结点和某个叶子之间存在的最长路径上的边的个数。

更多的参考这篇文章：完美二叉树, 完全二叉树和完满二叉树

2. 二叉树

2.1 二叉树的概念

学数据结构离不开怎么用这个话题。在学习MySQL的时候会反反复复地提及一个数据结构叫做B+树的，实际就是个多叉树的变种。而多叉树的学习绕不开基本的二叉树。

二叉树首先是一棵树，只不过比较特殊，每个结点规定不能超过 2 个子结点。

知道了这个定义之后，甚至可以直接写出二叉树的代码了：

typedef struct btree {
    int data;
    tree left;
    tree right;
} *tree, TreeNode;

这里我用了链式实现的方法，实际上还可以用数组来实现。如下图就是一个用数组实现的二叉树，只不过这个二叉树比较特殊，这是一个完全二叉树。

A Complete Binary Tree （CBT) is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. 完全二叉树倒数第二层一定是满的，叶子结点则靠左排列。

最初我读到靠左排列的时候纳闷了好久，什么叫做靠左？实际上英文的解释更加的好理解一些，注意“as far left as possible”，其实是尽可能的靠左排列。

如果看到下面的数组，就可以理解的更好了，如果是一个完全二叉树，数组里是不会有空洞的，size=11 的数组除了 0 位置之外都是没出现空洞，不造成空间的浪费。

2.2 二叉树的递归遍历和非递归遍历

二叉树有三种遍历方式，前序遍历、中序遍历和后序遍历。

• 前序遍历：先访问根节点，然后访问左孩子，然后访问右孩子；
• 中序遍历：先访问左孩子，然后访问根节点，然后访问右孩子；
• 后序遍历：先访问左孩子，然后访问右孩子，最后访问根节点。

也很好记，根节点访问在什么位置叫什么序，其余结点的访问一定是左先右后。

void midReverse(tree t) {
    if (t == nullptr) {
        return ;
    }
    midReverse(t->left);
    printf("%d\n", t->data);
    midReverse(t->right);
}


void preReverse(tree t) {
    if (t == nullptr) {
        return ;
    }

    printf("%d\n", t->data);
    preReverse(t->left);
    preReverse(t->right);
}

void postReverse(tree t) {
    if (t == nullptr) {
        return ;
    }

    postReverse(t->left);
    postReverse(t->right);
    printf("%d\n", t->data);
}

非递归的办法稍微麻烦一些，有点难于理解。可以归结为：

1. 从 root 遍历，把所有的左结点 push 到栈里；
2. 取（pop）栈顶元素判断是否有右子树，如果有，则以此元素为 root，重复上面的步骤，直到栈空；

不管是中序还是前序，都是这么个过程，区别在于访问 root 结点的时机。以打印 root 结点为例：

• 中序：结点 pop 时打印；
• 先序：结点入栈前打印

后序麻烦些，因为需要判断左子树和右子树都处理完了。待以后再学。

2.3 二叉搜索树

所谓二叉搜索树，其实也是一个二叉树，只不过是为了快速搜索实现的。相比于一般的二叉树，有一个显著的特点：对于任意结点，其左子树中的所有节点都要小于该结点，而右子树中的所有结点都要大于该结点。

下面是二叉查找树的插入和搜索代码实现：

void insert(tree t, int data) {
    tree root = t;
    tree p = (tree) malloc(sizeof (Btree));
    p->data = data;
    while (root != nullptr) {
        if (data > root->data) {
            if (root->right == nullptr) {
                root->right = p;
                return;
            }
            root = root->right;
        } else {
            if (root->left == nullptr) {
                root->left = p;
                return ;
            }
            root = root->left;
        }
    }
}


tree find(tree t, int data) {
    tree root = t;

    while (root != nullptr) {
        if (data < root->data) {
            root = root->left;
        } else if (data > root->data) {
            root = root->right;
        } else {
            return root;
        }
    }

    return nullptr;
}

实现起来很简单，依照着定义就能写出来了。不过删除操作比较麻烦，一些情况下还需要对大量的结点进行迁移，将其迁移到新的 root 下，这是个复杂的操作，因此有些时候甚至只是将结点标记为删除，以空间浪费换取一些遍历。

这也就是之前学 MySQL 的时候常说的，不要用随机的数做主键，容易导致 B+树的重建，消耗大量的 IO的原因。

如果二叉查找树是一个完全二叉树，那么其搜索、插入、删除的时间复杂度都是 O(logn)。但是注意，随着数据增多，树会逐渐的不平衡，极端情况下会退化成一个链表，这个时候的时间复杂度就又成为 O(n)了。

为了保持树的平衡，人们是提出了很多方法，不过最出名的是红黑树，也是 HashMap 里使用的。

其实红黑树应用比较广泛是因为它本身并不是一个严格的平衡二叉树，而是一种近似平衡的二叉树。不过如果要维持绝对平衡，那付出的代价也是很高的。

可以说红黑树是在性能的再平衡代价中的一种择优方案。