37. 数组二叉树
一、题目描述
二叉树只也可以用数组来存储，给定一个数组，树的根节点的值储存在下标1，对于储存在下标n的节点，他的左子节点和右子节点分别储存在下标2n和2n+1，并且我们用-1代表一个节点为空，给定一个数组存储的二叉树，试求从根节点到最小的 叶子节点只的路径，路径由节点的值组成。二、输入描述
输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分割，注意第一个元素即为根节点的值，即数组的第n元素对应下标n，下标0在树的表示中没有使用，所以我们省略了，输入的树最多为7层。三、输出描述
输出从根节点到最小叶子节点的路径上各个节点的值，由空格分割，用例保证最小叶子节点只有一个。示例 1
输入:3 5 7 -1 -1 2 4
输出:3 7 2
示例 2
输入:5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6
输出:5 8 7 6
————————————————版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/lbp0123456/article/details/143730774
一、问题分析
首先读题，仔细看描述中的内容，发现需求是
1.二叉树也可以用数组来存储，
2.给定一个数组，树的根节点的值储存在下标1，
3.对于储存在下标n的节点，它的左子节点和右子节点分别储存在下标2n和2n+1，
4.并且我们用-1代表一个节点为空，给定一个数组存储的二叉树
5.试求从根节点到最小的叶子节点的路径，
6.路径由节点的值组成
7.输入描述：输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分割，注意第一个元素即为根节点的值，即数组的第n元素对应下标n，下标0在树的表示中没有使用，所以我们省略了，输入的树最多为7层。
8.输出描述：输出从根节点到最小叶子节点的路径上各个节点的值，由空格分割，用例保证最小叶子节点只有一个。
二、解题思路
1.
2.
3.首先理解一下题目，题目的意思是找到二叉树中最小的节点值，并且返回从根节点到达该叶子节点的路径上各个节点的值。
所以对于第一棵树，最小值是2（-1代表节点为空）我们的输出是3 7 2
第二棵树的最小值是6，所以输出是5 8 7 6
4.
对于在数组中存储的二叉树，如果树的根节点的下标为1时，树中的根节点的左子节点的下标是2n，右子节点的下标是2n+1
5.所以我们先找到最小值，找到最小值之后记录下来最小值的索引，
比如索引值是14，我们将索引值除以2，14/2=7，然后7再除以2=3，3再除以2=1
所以我们从根节点到最小值的索引分别是1 3 7 14
6.还有需要注意的是我们要找的是最小的叶子节点，所以如果是根节点不可以
关于这一点我们可以判断，如果找到的节点*2超过我们所有节点的值，那么这个节点是一个叶子节点
或者如果我们用总节点数除以2，的数字的下一个数字到最后一个节点是叶子节点。
三、具体步骤
使用的语言是C
#include <stdio.h>
#include <limits.h>
int main() {
int arr[1000];
arr[0] = 0;
int idx = 1;
int min = INT_MAX;
int minidx = 0;
while (scanf("%d", &arr[idx++]) != EOF) {
// printf("输入数值%d, 索引值为%d\n", arr[idx - 1], idx - 1);
}
idx--;
for(int i = 1; i < idx; i++) {
if(arr[i] != -1) {
if(arr[i] < min) {
if(((i * 2) > idx)) {
min = arr[i];
minidx = i;
// printf("最小值更新为%d, 索引值为%d\n", min, minidx);
}
}
}
}
int answer[idx];
int aidx = 0;
while (minidx != 1) {
// printf("当前节点为%d值为%d\n", minidx, arr[minidx]);
answer[aidx++] = minidx;
minidx /= 2;
}
printf("%d", arr[1]);
for (int i = aidx - 1; i >= 0; i--) {
printf(" %d", arr[answer[i]]);
}
return 0;
}