填空题

最优二叉树

Question

有一个节点数组，需要创建一棵最优二叉树，即每个节点的权值乘以节点在树中的长度，然后相加得到的值最小。以下图一为例，节点数组的[A,B,C,D,E]的权值分别为[15,7,6,6,5]，构建好的最优二叉树见图二。

相关框架代码已经给出，请补充缺失部分，保证程序正常运行，输出预期结果。

```

struct node {

    int left, right, parent

    int val

}

int build_tree(struct node arr[], int cnt)

{

    while (1) {

        int i

        int min1 = -1              //权值最小的节点编号

        int min2 = -1              //权值第二小的节点编号

        int root_node = 0          //根节点(没有父节点)的个数

        for (i = 0 i < cnt ++i) {

            if (arr[i].____________ >= 0)

                continue

            ++root_node

            if (min1 < 0) {

                min1 = i

            } else if (arr[i].val < ____________) { 

                min2 = min1

                min1 = i

            } else if (min2 < 0) {

                min2 = i

            } else if (arr[i].val < ____________) { 

                min2 = i

            }

        }

        if (root_node < ____________)

            break

        arr[cnt].left = min2

        arr[cnt].right = min1

        arr[cnt].val = arr[min1].val + ____________ 

        arr[cnt].parent = -1

        arr[min1].parent = cnt

        arr[min2].parent = cnt

        ++cnt

    }

    return cnt

}

```

输入描述： 第一行为数据个数 第二行为权值（整数）输入样例： 5 15 7 6 6 5 输出描述： 构建的二叉树（用于绘图软件生成对应的二叉树图形）输出样例 ```mermaid graph TD n0[n0:15] n0 --> n8 n1[n1:7] n1 --> n6 n2[n2:6] n2 --> n5 n3[n3:6] n3 --> n6 n4[n4:5] n4 --> n5 n5((11)) n5 --> n7 n6((13)) n6 --> n7 n7((24)) n7 --> n8 n8((39)) ```