笛卡尔树非常有特点
以题中示例 seq[0, 9] = {8,15,3,4,1,5,12,10,18,6}为例
特点之一是最小堆堆序性, 即某个结点的权必须小于它两个孩子的权。
所以以seq[0, 9]这段序列建树, 根结点一定是seq[0, 9]中最小的那个元素即1, 下标为4
特点二是中序遍历返回原序列, 中序遍历我们都知道是左->根->右, 前面我们确定了整颗树的根为1, 所以seq中在1之前的元素一定在1的左子树上, 1之后的元素一定在1的右子树上。
是不是递归的味道就出来了。
我们对1之前的序列seq[0, 3]进行树的构建, 构建出来的树作为1的左子树
对1后的序列seq[5, 9]进行树的构建, 构建出来的树作为1的右子树。
返回1结点的地址
这样树就构造完毕了。
最后对树进行广度优先遍历即可
代码实现
//
// Created by trudbot on 2022/6/21.
//作者:trudbot 结果: Accepted 通过了 10/10个数据 运行时间:10 ms 运行空间: 212 KB
#include <bits/stdc++.h>
using namespace std;
typedef struct node{
int val;
struct node* left, *right;
}*Node;
//新建结点
inline Node NewNode(int val){
Node n = new node;
n->val = val;
n->left = n->right = nullptr;
return n;
}
//找到子序列中最小元素的下标
inline int FindMin(const int* seq, int first, int last){
if(first == last){
return first;
}
if(first > last){
return -1;
}
int mini = first;
while(++first <= last){
if(seq[first] < seq[mini]){
mini = first;
}
}
return mini;
}
//树的建立
Node BuildTree(const int* seq, int first, int last){
if(first > last){//序列为空, 返回NULL
return nullptr;
}
int pos = FindMin(seq, first, last);
Node root = NewNode(seq[pos]);
root->left = BuildTree(seq, first, pos-1);
root->right = BuildTree(seq, pos+1, last);
return root;
}
//广度优先遍历
void BFS(Node root){
queue<Node> q;
Node temp;
q.push(root);
while(!q.empty()){
temp = q.front();
q.pop();
cout << temp->val << " ";
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}
}
int main() {
int N;
cin>> N;
int seq[N];
for(int i=0; i<N; i++){
cin >> seq[i];
}
Node tree = BuildTree(seq, 0, N-1);
BFS(tree);
return 0;
}
妙!