数组二叉树

• 二叉树也可以用数组来存储给定一个数组
• 树的根节点的值储存在下标1, 对于储存在下标n的节点， 他的左子节点和右子节点分别储存在下标2*n和2*n+1
• 并且我们用-1代表一个节点为空，给定一个数组存储的二叉树，试求从根节点到最小的叶子节点的路径
• 输入描述
• 输入一行 为数组的内容 数组的每个元素都是正整数，元素间用空格分割
• 注意第一个元素即为根节点的值
• 即数组的第n元素对应下标n
• 输入的树最多为7层
• 输出描述
• 输出从根节点到最小叶子节点的路径上各个节点的值由空格分割

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class Question37 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        scanner.useDelimiter("\n");
	  //输入：4 2 6 1 3 5 7 5 6 3 -1 3 1 9 8 9 7 6 9 8 -1 3 2 5 6 7 9 0 8 7 2
	  //输出：4 6 7 9 0
        String str = scanner.next();
        String[] split = str.split(" ");
        int[] arr = new int[split.length];
        for (int i = 0; i < split.length; i++) {
            arr[i] = Integer.parseInt(split[i]);
        }
        new Question37().answer(arr);
    }

    public void answer(int[] arr) {
        Map<Integer, Tree> map = new HashMap<>();
        //按元素创建好节点，以备后面使用
        for (int i = 1; i <= arr.length; i++) {
            if (arr[i - 1] == -1) {
                map.put(i, null);
            } else {
                map.put(i, new Tree(arr[i - 1]));
            }
        }
        //构建二叉树，同时寻找最小叶子节点的坐标
        int[] min = new int[]{0, Integer.MAX_VALUE};
        for (int i = 1; i <= arr.length; i++) {
            if (map.get(i) != null) {
                if (map.containsKey(2 * i) && map.get(2 * i) != null) {
                    map.get(i).left = map.get(2 * i);
                }
                if (map.containsKey(2 * i + 1) && map.get(2 * i + 1) != null) {
                    map.get(i).right = map.get(2 * i + 1);
                }
                if (map.get(i).left == null && map.get(i).right == null && map.get(i).val < min[1]) {
                    min[0] = i;
                    min[1] = map.get(i).val;
                }
            }
        }
        Stack<Integer> stack = new Stack<>();
        int index = min[0];
        stack.push(map.get(index).val);
        while (index > 1) {
            if (index % 2 != 0) {
                index--;
            }
            index /= 2;
            stack.add(map.get(index).val);
        }
	  //格式化输出
        while (!stack.isEmpty()) {
            if (stack.size() != 1) {
                System.out.print(stack.pop() + " ");
            }else {
                System.out.print(stack.pop());
            }
        }
    }
	//中序遍历
    public void order(Tree tree) {
        if (tree.left != null) {
            Tree left = tree.left;
            order(left);
        }
        System.out.println(tree.val);
        if (tree.right != null) {
            Tree right = tree.right;
            order(right);
        }
    }
}
//自定义二叉树
class Tree {
    int val;
    Tree left;
    Tree right;
    public Tree(int val) {
        this.val = val;
    }
}