【数据结构】二叉树

摘要

本文主要总结二叉树、二叉搜索树、平衡二叉树、红黑树等相关知识以及具有代表性的题目，后续将持续更新。

二叉树

1 前序、中序、后序遍历的迭代算法

对于前序遍历，遍历顺序为“根、左、右”，因此对于任意一个节点，直接将节点值加入结果列表并入栈，然后遍历左子树，直到节点为空，开始遍历右子树即可，前序遍历代码：

vector<int> preorderTraversal(TreeNode* root)
{
    vector<int> ans;
    stack<TreeNode*> s;
    while(root != nullptr || !s.empty())
    {
        while(root)
        {
            ans.push_back(root->val);	//直接加入结果
            s.push(root);		//入栈
           	root = root->left;	//遍历左子树
        }
        root = s.top();
        s.pop();
        root = root->right;		//遍历右子树
	}
    return ans;
}

对于中序遍历，遍历顺序为“左、根、右”，因此只需要将前序遍历的顺序改为，对于任意一个节点，先遍历左子树入栈，直到节点为空，取栈顶节点加入结果列表（此时栈顶节点的左节点为空，因此栈顶结点即为子树的根节点，加入结果列表），然后遍历右子树，中序遍历代码：

vector<int> inorderTraversal(TreeNode* root)
{
    vector<int> ans;
    stack<TreeNode*> s;
    while(root != nullptr || !s.empty())
    {
        while(root)
        {
            s.push(root);		//入栈
           	root = root->left;	//遍历左子树
        }
        //左子树为空此时栈顶结点就作为子树的根节点，加入结果列表，并出栈，然后遍历右子树
        root = s.top();
        ans.push_back(root->val);
        s.pop();
        root = root->right;		//遍历右子树
	}
    return ans;
}

对于后序遍历，遍历顺序为“左、右、根”，考虑其和前序遍历顺序“根、左、右”的关系，如果前序遍历时把节点值放入结果的、列表尾部的操作改为插入列表头部，则遍历顺序变为“右、左、根”，此时只需要再将前序遍历时，先遍历左子树在遍历右子树的顺序对调，就可以将遍历顺序改为“左、右、根”，即为后序遍历了，后序遍历代码：

vector<int> postorderTraversal(TreeNode* root)
{
    vector<int> ans;
    stack<TreeNode*> s;
    while(root != nullptr || !s.empty())
    {
        while(root)
        {
            ans.insert(ans.begin(),root->val);	//结果插到列表开头
            s.push(root);		//入栈
           	root = root->right;	//先遍历右子树
        }
        root = s.top();
        s.pop();
        root = root->left;		//再遍历左子树
	}
    return ans;
}

2 层序遍历

使用广度优先搜索即可

3 构造二叉树

前序与中序构建二叉树

后序与中序构建二叉树

二叉树的序列化与反序列化

4 递归解决二叉树问题

二叉树的最大深度

对称二叉树

路径总和

路径总和 II：广搜方法值得注意，用哈希表记录每个结点的父节点，找到一条路径后从叶子节点往回找父节点就可以还原出一条路径

路径总和 III：双重递归

二叉树的最近公共祖先

二叉树的直径

二叉搜索树（BST）

1 定义与性质

二叉搜索树（BST）是二叉树的一种特殊表示形式，它满足如下特性：

每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

二叉搜索树的插入和删除：

插入节点：

删除节点：

总结一下二叉搜索树的性质：

中序遍历可以得到递增序列
Successor 代表的是中序遍历序列的下一个节点。即比当前节点大的最小节点，简称后继节点。先取当前节点的右节点，然后一直取该节点的左节点，直到左节点为空，则最后指向的节点为后继节点。
Predecessor 代表的是中序遍历序列的前一个节点。即比当前节点小的最大节点，简称前驱节点。先取当前节点的左节点，然后取该节点的右节点，直到右节点为空，则最后指向的节点为前驱节点。

可以利用二叉搜索树的性质解决许多问题。这里只给出二叉搜索树的基本操作，后面会遇到许多用到二叉搜索树的题目。

2 平衡二叉搜索树

实际使用中由于输入值不够随机，也许经过某些插入或删除操作，二叉搜索树可能会失去平衡，造成搜寻效率低落的情况。所谓二叉树平衡与否，并没有一个绝对的测量标准。 “平衡”的大致意义是：没有任何一个节点过深（深度过大）。不同的平衡条件，造就出不同的效率表现，以及不同的实现复杂度。有数种特殊结构如 AVL-tree 、RB-tree 、AA-tree，均可实现出平衡二叉搜索树，它们都比一般的（无法绝对维持平衡的）二叉搜索树复杂，因此，插入节点和删除节点的平均时间也比较长，但是它们可以避免极难应付的最坏（高度不平衡）情况，而且由于它们总是保持某种程度的平衡，所以元素的访问（搜寻）时间平均而言也就比较少。一般而言其搜寻时间可节省 25% 左右。

3 AVL-tree

AVL tree 是一个 “加上了额外平衡条件”的二叉搜索树。其平衡条件的建立是为了确保整棵树的深度为 O(logN)，AVL tree 要求任何节点的左右子树高度相差不超过 1。

当一个节点插入 AVL 树中并破坏了树的平衡时，之存在以下两种情况：

其中外侧插入可以通过单旋转调整至平衡状态，内侧插入可以通过双旋转调整至平衡状态。

3.1 单旋转

在外侧插入状态中，如下图所示：

A 子树成长了一层，致使它比 C 子树的深度多 2，为了调整平衡状态，我们希望将 A 子树提高一层，并将 C 子树下降一层，我们可以这么想象，把 k1 向上提起，使 k2 自然下滑，并将 B 子树挂到 k2 的左侧。
这么做是因为，二叉搜索树的规则使我们知道， k2 > k1, 所以 k2 必须成为新树中的 k1 的右子节点。二叉搜索树的规则也告诉我们， B 子树的所有节点的键值都在 k1 和 k2 之间，所以新树中的 B 子树必须落在 k2 的左侧。

以上所有调整操作都只需要将指针稍做搬移，就可迅速达成。完成后的新树符合 AVL-tree 的平衡条件，不需再做调整。

3.2 双旋转

在内侧插入状态中，如下图所示：

我们不能再以 k3 为根节点，其次，我们不能将 k3 和 k1 做一次单旋转，因为旋转之后还是不平衡，唯一的可能是以 k2 为新的根节点，这使得（根据二叉搜索树的规则） k1 必须成为 k2 的左子节点， k3 必须成为 k2 的右子节点，而这么一来也就完全决定了四个子树的位置。

新的树形满足 AVL-tree的平衡条件，并且，就像单旋转的情况一样，它恢复了节点插入之前的高度，因此保证不再需要任何调整。

而所谓双旋转是指以上操作可以通过两次单旋转完成，这为编程带来了极大的便利：

红黑树（RB-tree）

RB-tree 是另一个被广泛使用的平衡二叉搜索树，也是 SGI STL 唯一实现的一种搜寻树，作为 STL 关联式容器 (associated containers) 的底部机制。STL 的关联式容器将在 STL 专题中学习。

所谓 RB-tree, 不仅是一个二叉搜索树，而且必须满足以下规则：

每个节点不是红色就是黑色。（图中深色底纹代表黑色，浅色底纹代表红色）
根节点为黑色。
如果节点为红，其两个子节点必须为黑。（父子节点不能同时为红）
任一节点至 NULL （树尾端）的任何路径，所含之黑节点数必须相同。

1 插入节点

现在我们为上图中的红黑树分别插入 3、8、35、75，根据二叉搜索树的规则，这 4 个新节点的落脚处如下图：

可以发现，由于新增节点必为红色，不论插入哪一个节点，都会破坏 RB-tree 的规则，致使我们必须旋转树形并调整节点的颜色。

为了方便讨论，让我先为某些特殊节点定义一些代名，以下讨论都将沿用这些代名。假设新节点为 X，其父节点为 P，祖父节点为 G，伯父节点（父节点之兄弟节点）为 S，曾祖父节点为 GG。

根据二叉搜索树的规则，新节点 X 必为叶节点。根据红黑树规则 4，X 必为红。若 P 亦为红（这就违反了规则 3, 必须调整树形），则 G 必为黑（因为原为 RB-tree，必须遵循规则 3) 。于是，根据 X 的插入位置及外围节点（S 和 GG）的颜色，有了以下四种考虑：

S 为黑且 X 为外侧插入。对此情况，我们先对 P,G 做一次单旋转，再更改 P,G 颜色，即可重新满足红黑树的规则 3。

注意，此时可能产生不平衡状态（高度相差 1 以上）,例如图中的 A 和 B 为 null，D 或 E 不为 null，但是没关系，因为 RB-tree 的平衡性本来就比 AVL-tree 弱。然而 RB-tree 通常能够维持良好的平衡状态。并且经验告诉我们， RB-tree 的平均搜索效率和 AVL-tree 几乎相等。

S 为黑且 X 为内侧插入。对此情况，我们必须先对 P, X 做一次单旋转并更改 G, X 颜色，再将结果对 G 做一次单旋转，即可再次满足红黑树规则 3 。

S 为红且 X 为外侧插入。对此情况，先对 P 和 G 做一次单旋转，并改变 X 的颜色。此时如果 GG 为黑，一切搞定。

S 为红且 X 为外侧插入。对此情况，先对 P 和 G 做一次单旋转，并改变 X 的颜色。此时如果 GG 亦为红，还得持续往上做，直到不再有父子连续为红的情况。

在最后一种情况下，父子节点皆为红色的情况会持续向RB-tree 的上层结构发展，形成处理时效上的瓶颈，于是我们可以施行一个由上而下的程序：假设新增节点为 A，那么就延着 A 的路径，只要看到有某节点 X 的两个子节点皆为红色，就把 X 改为红色，并把两个子节点改为黑色，如下图：

此时如果 A 的父节点 P 也为红色（注意，此时 S 绝不可能为红），就得像第一种情况一样做一次单旋转并改变颜色，或是像第二种情况一样做一次双旋转并改变颜色。

2 对比 BST 和 AVL

红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以O(logN)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。

相比于BST，因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证 O(logN) 的，这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到 O(N)。

红黑树的算法时间复杂度和 AVL 相同，但统计性能比 AVL 树更高，所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多，但是他们的查找效率都是 O(logN)，所以红黑树应用还是高于 AVL 树的。实际上插入 AVL 树和红黑树的速度取决于你所插入的数据。如果你的数据分布较好，则比较宜于采用 AVL树（例如随机产生系列数），但是如果你想处理比较杂乱的情况，则红黑树是比较快的。