【必做】最优二叉树_牛客题霸_牛客网

有一个节点数组，需要创建一棵最优二叉树，即每个节点的权值乘以节点在树中的长度，然后相加得到的值最小。以下图一为例，节点数组的[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 if (arr[i].____________ = 0) continue; ++root_node; if (min1 min1 = i; } else if (arr[i].val min2 = min1; min1 = i; } else if (min2 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; } ```

输入描述:

第一行为数据个数 第二行为权值（整数）

输出描述:

构建的二叉树（用于绘图软件生成对应的二叉树图形）

示例1

输入

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))
```

说明

1.grath TD下面的输出都是\t开头
2.n0 ---> n8 的意思是n0的父节点是n8

加载中...

#include <stdio.h>
#include <limits.h>
#include <assert.h>
#include <malloc.h>

struct node {
    int left, right, parent;
    int val;
};

void tree_print(const struct node arr[], int cnt)
{
    int i;
    for (i = 0; i < cnt; ++i) {
        fprintf(stderr, "%d: {left:%d,right:%d,parent:%d,val:%d}\n"
            , i, arr[i].left, arr[i].right, arr[i].parent, arr[i].val);
    }
}

void tree_output(FILE *fp, const struct node arr[], int old_cnt, int cnt)
{
    int i;
    fprintf(fp, "```mermaid\n");
    fprintf(fp, "graph TD\n");
    for (i = 0; i < cnt; ++i) {
        if (i < old_cnt)
            fprintf(fp, "\tn%d[n%d:%d]\n", i, i, arr[i].val);
        else
            fprintf(fp, "\tn%d((%d))\n", i, arr[i].val);

if (arr[i].parent >= 0) {
            fprintf(fp, "\tn%d --> n%d\n", i, arr[i].parent);
        }
    }
    fprintf(fp, "```\n");
}

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

static int input(int **arr, int *size)
{
    int i;
    int ret;

ret = fscanf(stdin, "%d\n", size);
    if (ret != 1)
        return -1;
    if (*size <= 0)
        return -1;
    *arr = (int *)malloc(sizeof(int) * (*size));
    for (i = 0; i < *size; ++i) {
        fscanf(stdin, "%d ", &(*arr)[i]);
    }
    return 0;
}
int main(int argc, char *argv[])
{
    int *vals = NULL;
    int cnt = 0;
    struct node *arr;
    int i;

if (input(&vals, &cnt) < 0) {
        fprintf(stderr, "input error\n");
        return 0;
    }
    arr = (struct node *)malloc(sizeof(struct node) * cnt * 3);

for (i = 0; i < cnt; ++i) {
        arr[i].left = -1;
        arr[i].right = -1;
        arr[i].parent = -1;
        arr[i].val = vals[i];
    }

build_tree(arr, cnt);

free(vals);
    free(arr);
    return 0;
}

//  建树，返回树的根节点
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;
}