一维数组转二叉树结构输出（2024-01-22）

package com.test.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.tarena.kshop.utils.JackJsonUtil;

import lombok.Data;

@Data
public class Solution {
?? ?
?? ?
?? ?public static void main(String[] args) {
? ? ?? ?String[] arr = new String[] { "91", "60", "96", "13", "35", "65", "46", "65", "10", "30", "20", "31", "77", "81", "22" };
? ? ?? ?System.out.println(JackJsonUtil.arrayToJson(arr));
?? ??? ?TreeNode treeNode = arrayToTree(arr);
?? ??? ?List<List<String>> lists = printTree(treeNode);
?? ??? ?for(List<String> list : ?lists) {
?? ??? ??? ?System.out.println(JackJsonUtil.listToJson(list));
?? ??? ?}
? ? }
?? ?
?? ?public static void intToString(Integer[] arrI) {
?? ??? ?String[] arr = new String[arrI.length];
?? ??? ?for(int i=0;i<arrI.length;i++) {
?? ??? ??? ?arr[i]=String.valueOf(arrI[i]);
?? ??? ?}
?? ??? ?//Arrays.asList( arrI).toArray(arr);
?? ??? ?TreeNode treeNode = arrayToTree(arr);
?? ??? ?List<List<String>> lists = printTree(treeNode);
?? ??? ?for(List<String> list : ?lists) {
?? ??? ??? ?System.out.println(JackJsonUtil.listToJson(list));
?? ??? ?}
?? ?}
?? ?
? ? /**
? ? ?* 将一维数组转换为二叉树
? ? ?* @param arr
? ? ?*/
? ? public static TreeNode arrayToTree(String[] arr) {
? ? ?? ?//数组为空直接返回
? ? ?? ?if(null == arr) {
? ? ?? ??? ?return null;
? ? ?? ?}
? ? ?? ?TreeNode root = new TreeNode();
? ? ?? ?root.setValueS(arr[0]);
? ? ?? ?Queue<TreeNode> queue = new LinkedList<>();
? ? ?? ?queue.add(root);
? ? ?? ?for(int i=1,len=arr.length;i<len;i++) {
? ? ?? ??? ?TreeNode node = queue.peek();
? ? ?? ??? ?TreeNode newNode = new TreeNode(arr[i]);
? ? ?? ??? ?//当前节点 没有左子结点
? ? ?? ??? ?if(null == node.getLeft()) {
? ? ?? ??? ??? ?node.setLeft(newNode);
? ? ?? ??? ??? ?//左子结点加入队列
? ? ?? ??? ??? ?queue.offer(newNode);
? ? ?? ??? ?//当前节点 没有又子结点
? ? ?? ??? ?}else if(null == node.getRight()) {
? ? ?? ??? ??? ?node.setRight(newNode);
? ? ?? ??? ??? ?queue.offer(newNode);
? ? ?? ??? ??? ?//当前节点已经完成，从队列移出，
? ? ?? ??? ??? ?queue.poll();
? ? ?? ??? ?}
? ? ?? ?}
? ? ?? ?return root;
? ? }
?? ?
?? ? public static List<List<String>> printTree(TreeNode root) {
?? ? ? ? ? ?//获取高度
?? ? ? ? ? ?int height = getHeight(root);
?? ? ? ? ? ?int arrHeight = height*2-1;
?? ? ? ? ? ?String[][] ans = new String[arrHeight][(1 << height) - 1];
?? ? ? ? ? ?//System.out.println(height+":"+ans[0].length);
?? ? ? ? ? ?for (String[] arr : ans) {
?? ? ? ? ? ? ? ?Arrays.fill(arr, " ?");
?? ? ? ? ? ?}
?? ? ? ? ? ?List<List<String>> res = new ArrayList<>();
?? ? ? ? ? ?fill(ans, root, 0, 0, ans[0].length,arrHeight);
?? ? ? ? ? ?for (String[] arr : ans) {
?? ? ? ? ? ? ? ?res.add(Arrays.asList(arr));
?? ? ? ? ? ?}
?? ? ? ? ? ?return res;
?? ? ? ?}

?? ? ? ?/**
?? ? ? ? * 填充数组
?? ? ? ? *
?? ? ? ? * @param ans ?数组
?? ? ? ? * @param root 根节点
?? ? ? ? * @param i ? ?第几行
?? ? ? ? * @param l ? ?左节点
?? ? ? ? * @param r ? ?右节点
?? ? ? ? */
?? ? ? ?private static void fill(String[][] ans, TreeNode root, int i, int l, int r,int arrHeight) {
?? ? ? ? ? ?if (root == null) {
?? ? ? ? ? ? ? ?return;
?? ? ? ? ? ?}
?? ? ? ? ? ?int currColumn = (l + r) / 2;
?? ? ? ? ? ?ans[i][(l + r) / 2] = "" + root.getValueS();
?? ? ? ? ? ?if((i+1)>=(arrHeight)) {
?? ? ? ? ? ??? ?return;
?? ? ? ? ? ?}
?? ? ? ? ? ?//数组赋值 / \
? ? ? ? ?? ?int leftSymbol= ((l+currColumn)/2+currColumn)/2;
? ? ? ? ?? ?int rightSymbol= ((currColumn + r + 1) / 2+currColumn)/2;
?? ? ? ? ? ?ans[i+1][leftSymbol] ="/";
?? ? ? ? ? ?ans[i+1][rightSymbol] ="\\";
?? ? ? ? ? ?//TreeNode 赋值给数组
?? ? ? ? ? ?fill(ans, root.getLeft(), i + 2, l, (l + r) / 2,arrHeight);
?? ? ? ? ? ?fill(ans, root.getRight(), i + 2, (l + r + 1) / 2, r,arrHeight);
?? ? ? ?}

?? ? ? ?/**
?? ? ? ? * 获取树的高度
?? ? ? ? *
?? ? ? ? * @param root
?? ? ? ? * @return
?? ? ? ? */
?? ? ? ?private static int getHeight(TreeNode root) {
?? ? ? ? ? ?if (root == null) {
?? ? ? ? ? ? ? ?return 0;
?? ? ? ? ? ?}
?? ? ? ? ? ?return Math.max(getHeight(root.getLeft()), getHeight(root.getRight())) + 1;
?? ? ? ?}

}

了解知识点

1、一维数组自动生成二叉树，其它的文章基本都是生成二维数组，结构图形输出的很少。我当时无法理解整个过程，写个结构输出便于堆排序的演示理解。

2、结构输出有“”/“\” 便于识别。这导致二维数组的高度算法有改变。