C＋树进阶系列之笛卡尔树的两面性

1. 前言

是一种特殊的二叉树数据结构，融合了和两大特性。可以把对象映射成，便于使用结构的逻辑求解数列的区间最值或区间排名等类似问题。

如有数列 ，任一存储单元格均有 个属性：

值：单元格中的数据。

位置：单元格在数列中的位置（下标、索引）。

构建要求节点至少有 个权重，把数列映射成树结构时，可使用这 个属性作为笛卡尔树节点的权重。把线性结构的数列映射成后，此树需要满足如下 个特征：

如果观察，则在树中具有堆的有序性，即任一父节点的值大于（最大堆）或小于（最小堆）子节点的值。根据堆的特性，可以查询或上的最大值或最小值。且可以使用算法排序数列。

如果观察，则在树中遵循的逻辑结构，或者说，对笛卡尔树进行中序遍历，可以得到原来的数组。

2. 构建笛卡尔树

可以说是双权重的节点树。那么，如何构建才能保证数列最终能映射成笛卡尔树。

实现过程中，需要借助数据结构。

什么是单调栈？

本质指的就是栈，但在存储数据时，需要要保持栈中数据按递增或递减顺序，本文构建最小堆，要求栈单调递减。

2.1 构建流程

现把数组 构建成笛卡尔树的过程详细讲解一下：

首先，准备一个栈。把数组中位置为 、值为 的元素（后面统一以格式描述）。将其压入栈中，且设置成树的根节点。

把数组中的和栈中上已有元素 比较，因值比 大。因能保持栈的递减顺序，可以直接入栈。且把入栈的元素作为的右子节点。

Tips： 至此，总结一下：能压入栈的元素作为栈中比它小的元素的右子节点。

从数组中取出，因比栈顶元素小 ，不能直接入栈，则需要把比它大的元素从栈中移走，然后把最后一个比它大的元素作为它的左子结点。如下图所示：

从数组中取出，因都比先入栈的元素大，可以直接依次入栈，且成为比它小的节点的右子节点。

Tips： 可以观察到，栈中的元素均为上的节点。

从数组中抽出元素，为了维持栈的递减顺序，则需要把比它大的元素从栈中移走，直到留下。把作为的右子节点，且让最后一个出栈的成为的左子节点。

继续拿出，可以直接入栈，让其成为的右子节点。

拿出。把比它大的元素出栈，成为最近比它小的元素的右子结点，最后出栈的元素成为它的左子节点。

从数组中最后拿出元素。因比栈中所有元素大，直接入栈，且成为栈顶元素的右子节点。

2.2 小结

使用单调栈构建笛卡尔树的原则：

如果需要移走其它元素后，元素才能入栈，则移走的最后一个节点成为其左子节点。

当数据入栈时，需要在栈中找到比它小的第一个元素，让会成为此元素的右节点。

栈中始终存储的最新上的节点。

构建完毕后，最后栈底的元素为根节点。

3. 笛卡尔树的物理结构

二叉树的物理实现有和 两种方案，本文将使用这 种方案：

3.1 矩阵实现

笛卡尔树类结构：

类中主要为构建函数和中序遍历，其它的为辅助性函数。代码中有详细注解。

实现 函数：

函数是核心，用来构建笛卡尔树。

实现此之前，需先实现辅助，用来实现把数组中的数据压入栈中时，查询到比之大的最后一个数据。本质是使用了单调栈的逻辑特性。

函数：

测试：

输出结果：表示不存在左或右子节点。

因中序遍历可以输出原数组，可用于验证笛卡尔树的构建是否正确。在类中可添加中序遍历函数的实现。

测试中序遍历：

输出结果：

3.2 链式实现

链式实现逻辑与矩阵实现本质没有什么不一样。不做过多解释，直接上完整代码。

4. 总结

本文讲解了笛卡尔树，对其特性作了较全面的分析，并且讲解了矩阵和链式两种实现方案。