用C++输入一组数建立最优二叉树

在C++中，我们可以使用贪心算法或者优先队列（如`std::priority_queue`）来构建最优二叉搜索树（例如最小生成树问题，Minimun Spanning Tree，MST）。这里我们假设你想要的是构建一棵满足所有节点值非降序排列，并且连接边的权值尽可能小的二叉搜索树。这种树也被称为霍夫曼树（Huffman Tree）在编码应用中很常见。

以下是一个简单的步骤：

1. **收集数据**：首先，从用户那里读取或输入一组整数值。

#include <iostream>
#include <queue>

// 假设TreeNode是一个结构体或类，包含int value和指向左右孩子的指针
struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
};

void buildOptimalBST(std::vector<int>& nums) {
    // 需要一个空的堆来存储节点及其权值
    std::priority_queue<std::pair<int, TreeNode*>, std::vector<std::pair<int, TreeNode*>>, std::greater<int>> heap;

    // 将每个节点添加到堆中
    for (int num : nums) {
        heap.push({num, new TreeNode{num, nullptr, nullptr}});
    }

    // 从堆中创建树的过程
    TreeNode* root = nullptr;
    while (heap.size() > 1) {
        auto left = heap.top(); heap.pop();
        auto right = heap.top(); heap.pop();
        // 创建新节点，连接左、右孩子
        TreeNode* newNode = new TreeNode(left.first + right.first, left.second, right.second);
        heap.push({left.first + right.first, newNode});
        root = newNode;
    }
    // 最后一个元素就是根节点
    if (!heap.empty()) {
        root = heap.top().second;
    }
}