1，笛卡尔树的介绍

前面我们讲过《堆》和《二叉搜索树》，能不能把这两种数据结构的特性结合起来构造一棵新的树呢？当然是可以的，这个就是我们这里要讲的笛卡尔树(Cartesian tree)。

笛卡尔树的每个节点有两个值 (x，y) ，其中一个满足二叉搜索树的特性，一个满足堆的特性，所以笛卡尔树是一棵具有二叉搜索树和堆的两种特性的二叉树

笛卡尔树中节点的两个值分别是数组中元素的值，和该元素在数组中的下标，其中元素的值满足堆的特性，元素的下标满足二叉搜索树的特性。

下面使用数组 [5, 6, 3, 8, 9, 1, 4, 7, 2] 构造一棵笛卡尔树。

2，笛卡尔树的构建

因为元素的下标满足二叉搜索树的特性，而数组中元素的下标又是递增的，所以新插入的节点要么是根节点，要么是根节点右子树上的某个节点，不可能是根节点左子树上的某个节点。

所以节点插入的时候不需要考虑左子树，又由于元素的值满足堆的特性(这里我们选择最小堆)，如果新插入的节点比根节点小，那么新节点就变成根节点的父节点，根节点就变成新节点的左子节点，如下图所示。

如果新节点的值比根节点大，那么新节点一定是根节点右子树上的某个节点，根节点的右子树节点可能很多，究竟插入到哪个位置呢？

实际上笛卡尔树的任何一棵子树也都是笛卡尔树，那么右子树当然也满足插入规则，如果新节点比根节点的右子节点小，那么根节点的右子节点是新节点的左子节点，新节点变成根节点的右子节点，如果新节点比根节点的右子节点大，继续和根节点右子节点的右子节点比较……

也就是说插入的时候新节点会和根节点一直往右的这条路径上的节点比较，为了方便比较我们可以使用一个栈来记录从根节点一直往右走的所有节点，很明显这个栈从栈顶到栈底是单调递减的，每次比较的时候不在从根节点开始，而是从栈顶元素开始比较，这个栈顶元素就是根节点一直往右走，最右边的节点。

这里我们选用最小堆，来看下笛卡尔树的构建步骤：

1，用数组中的第一个元素创建根节点，然后把根节点添加到栈中。
2，遍历数组的剩余元素，然后创建新节点和栈顶元素比较，如果栈不为空并且栈顶元素比新节点大，栈顶元素出栈。一直比较，直到栈为空或者栈顶元素小于新节点为止。
3，如果栈为空，让新节点变成根节点的父节点，根节点变成新节点的左子节点。
4，如果栈不为空，让最后一个出栈的节点变成新节点的左子节点，新节点变成栈顶元素的右子节点。
5，新节点入栈，继续重复步骤2,3,4,5，直到数组遍历完为止。

我们以数组 [5,6,3,8,9,1,4,7,2] 为例，来看下笛卡尔树的构建过程：

3，笛卡尔树的代码实现