二叉树的构建

发布网友发布时间：2022-04-29 18:26

共1个回答

热心网友时间：2022-06-19 01:09

关于这道题，从叶子层到根构造一颗二叉树，父节点为左右孩子的平均数，我们可以采取类似线段树的做法。

线段树是一种极其简单的数据结构，无需赘述，直接给出代码。

#include<stdio.h>
#include<string.h>

#define MAXN 1000

bool f[MAXN+1];
int n;
double a[MAXN+1],tree[MAXN<<2];//线段树的空间要开4倍

void Build(int k,int l,int r){
if(l==r)
tree[k]=a[l],f[k]=true;//如果区间长度为1，则没有左右子树，直接赋值
else{
f[k]=true;
Build(k<<1,l,l+r>>1);
Build(k<<1|1,(l+r>>1)+1,r);//递归构造左右子树
tree[k]=(tree[k<<1]+tree[k<<1|1])/2;//算平均值
}
return;
}

int main(void){
memset(tree,0XFF,sizeof(tree));//初始化
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf",&a[i]);
Build(1,1,n);//构造
for(int i=1;f[i];i++)
printf("%d %.2f *l=%d left=%.2f *r=%d right=%.2f\n",i,tree[i],i<<1,tree[i<<1],i<<1|1,tree[i<<1|1]);
return 0;
}

例：

输入为：

4
1 2 3 4

输出为：

1 2.50 *l=2 left=1.50 *r=3 right=3.50
2 1.50 *l=4 left=1.00 *r=5 right=2.00
3 3.50 *l=6 left=3.00 *r=7 right=4.00
4 1.00 *l=8 left=-1.#R *r=9 right=-1.#R
5 2.00 *l=10 left=-1.#R *r=11 right=-1.#R
6 3.00 *l=12 left=-1.#R *r=13 right=-1.#R
7 4.00 *l=14 left=-1.#R *r=15 right=-1.#R

对于每一行输出：

第一个数是当前节点的编号，第二个数表示此节点的值；

第三个数是左子树的编号，第四个数是左子树的值；

第五个数是右子树的编号，第六个数是右子树的值。子树不存在则值为-1.#R。

对于这组输出数据，它的含义如下图。

图中每个节点前一个数字代表它的编号，后一个数字为它的值。

如果n为2的正整数次幂，则生成的二叉树是一颗满二叉树，否则是一颗完全二叉树。