上海
摘要：
1，笛卡尔树的介绍
2，笛卡尔树的构建
3，笛卡尔树的代码实现
4，笛卡尔树的特性
5，笛卡尔树的应用
1，笛卡尔树的介绍
前面我们讲过和，能不能把这两种数据结构的特性结合起来构造一棵新的树呢？当然是可以的，这个就是我们这里要讲的笛卡尔树(Cartesian tree)。
笛卡尔树的每个节点有两个值 (x，y) ，其中一个满足二叉搜索树的特性，一个满足堆的特性，所以笛卡尔树是一棵具有二叉搜索树和堆的两种特性的二叉树
笛卡尔树中节点的两个值分别是数组中元素的值，和该元素在数组中的下标，其中元素的值满足堆的特性，元素的下标满足二叉搜索树的特性。
下面使用数组 [5, 6, 3, 8, 9, 1, 4, 7, 2] 构造一棵笛卡尔树。
2，笛卡尔树的构建
因为元素的下标满足二叉搜索树的特性，而数组中元素的下标又是递增的，所以新插入的节点要么是根节点，要么是根节点右子树上的某个节点，不可能是根节点左子树上的某个节点。
所以节点插入的时候不需要考虑左子树，又由于元素的值满足堆的特性(这里我们选择最小堆)，如果新插入的节点比根节点小，那么新节点就变成根节点的父节点，根节点就变成新节点的左子节点，如下图所示。
如果新节点的值比根节点大，那么新节点一定是根节点右子树上的某个节点，根节点的右子树节点可能很多，究竟插入到哪个位置呢？
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
