设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数 若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。 要求输出： （1）tree的最高加分 （2）tree的前序遍历 数据范围： ，每个节点的值满足
区块链毕设网qklbishe.com为您提供问题的解答
设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。
要求输出：
（1）tree的最高加分
（2）tree的前序遍历
数据范围： 
，每个节点的值满足 
动态规划，dp[i][j] = max(dp[i][k – 1] * dp[k +１][j] + vec[k]),用一个矩阵保存使dp[i][j]最大的根节点位置，rootPos[i][j] = max(k).最后递归打印出前序遍历结果
#include #include using namespace std; void preOrder(vector> &rootPos, int left, int right); int main() { int n; cin >> n; vector vec(n, 0); for (int i = 0; i < n; ++i) { cin >> vec[i]; } vector> dp(n + 2, vector(n + 2, 1)), rootPos(n + 1, vector(n + 1, 0)); for (int i = n; i > 0; --i) { dp[i][i] = vec[i - 1]; rootPos[i][i] = i; for (int j = i + 1; j <= n; ++j) { int maxVal = 0, maxPos = 0; for (int k = i; k <= j; ++k) { int num = dp[i][k - 1] * dp[k + 1][j] + vec[k - 1] ; if (maxVal < num) { maxVal = num; maxPos = k; } } dp[i][j] = maxVal; rootPos[i][j] = maxPos; } } cout << dp[1][n] << endl; preOrder(rootPos, 1, n); return 0; } void preOrder(vector> &rootPos, int left, int right) { if (left > right) return; cout << rootPos[left][right] << ' '; preOrder(rootPos, left, rootPos[left][right] - 1); preOrder(rootPos, rootPos[left][right] + 1, right); }
31:05
以上就是关于问题设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数 若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。 要求输出： （1）tree的最高加分 （2）tree的前序遍历
数据范围： ，每个节点的值满足的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
