按照层次遍历结果打印完全二叉树

按照层次遍历结果打印完全二叉树

按照推论结果：

• l 层首个节点位置 2^h-l - 1
• l 层节点间距：2^h-l+1 - 1

编码实现

 public static<E> void print(BinaryTree<E> tree) {List<List<Node<E>>> levelNodeList = levelOrderTraversal(tree);int height = levelNodeList.size();for (int level = 1; level <= height; level++) {List<Node<E>> nodelist = levelNodeList.get(level - 1);// 打印首个节点int firstNodePosition = (int) Math.pow(2, (height - level)) - 1;System.out.print(getBlankSpace(firstNodePosition) + nodelist.get(0).element);int separation = (int)Math.pow(2, (height-level+1)) - 1;String separationBlankSpace = getBlankSpace(separation);for (int i = 1; i < nodelist.size(); i++) {// 打印中间节点System.out.print(separationBlankSpace + nodelist.get(i).element);}System.out.println();}}public static<E>List<List<Node<E>>> levelOrderTraversal(BinaryTree<E> tree) {Queue<Node<E>> queue = new LinkedList<>();queue.offer(tree.root);List<List<Node<E>>> result = new ArrayList<>();while (!queue.isEmpty()) {// 此时队列的容量就是当前层的节点个数int levelSize = queue.size();ArrayList<Node<E>> levelNodes = new ArrayList<>();for (int i = 0; i < levelSize; i++) {Node<E> node = queue.poll();levelNodes.add(node);if (node.left != null) {queue.offer(node.left);}if (node.right!= null) {queue.offer(node.right);}}result.add(levelNodes);}return result;}private static String getBlankSpace(int n) {StringBuilder builder = new StringBuilder();while (n > 0) {builder.append(" ");n--;}return builder.toString();}

打印效果

似乎更预想的不一样，猜测是因为 像 11，12这种两位数实际占了两个字符，导致的。将所有数都改成 1：

显示完美。

将空格改为 \t

显示还是有问题。考虑将最后一层间距修改为 2，通过双 \t 控制显示格式

完整代码

package com.wy.algo.tree;import cn.hutool.core.lang.Assert;import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;/*** @author HelloWorld* @date 2024/1/2 18:32* @email helloworld.dng@gmail.com*/
public class BinaryTree<E> {public static void main(String[] args) {BinaryTree<Integer> binaryTree = init(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);//BinaryTree<Integer> binaryTree = init(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);print(binaryTree);}Node<E> root;/*** @description 初始化二叉树(层次遍历)* @author HelloWorld* @create 2024/1/2 18:57* @param elements* @return com.wy.algo.tree.BinaryTree<E>*/@SafeVarargspublic static<E> BinaryTree<E> init(E... elements) {Assert.notEmpty(elements, "elements must not be empty");BinaryTree<E> tree = new BinaryTree<>();tree.root = new Node<>(elements[0]);Queue<Node<E>> queue = new LinkedList<>();queue.offer(tree.root);int index = 1;while (!queue.isEmpty()) {Node<E> node = queue.poll();if (index < elements.length) {node.left = new Node<>(elements[index]);queue.offer(node.left);}index++;if (index < elements.length) {node.right = new Node<>(elements[index]);queue.offer(node.right);}index++;}return tree;}public static<E> void print(BinaryTree<E> tree) {List<List<Node<E>>> levelNodeList = levelOrderTraversal(tree);int height = levelNodeList.size();for (int level = 1; level <= height; level++) {List<Node<E>> nodelist = levelNodeList.get(level - 1);// 打印首个节点int firstNodePosition = (int) Math.pow(2, (height - level)) - 1;System.out.print(getBlankSpace(firstNodePosition) + nodelist.get(0).element);// 优化显示效果，将间距修改为2int separation = (int)Math.pow(2, (height-level+1));String separationBlankSpace = getBlankSpace(separation);for (int i = 1; i < nodelist.size(); i++) {// 打印中间节点System.out.print(separationBlankSpace + nodelist.get(i).element);}System.out.println();}}public static<E>List<List<Node<E>>> levelOrderTraversal(BinaryTree<E> tree) {Queue<Node<E>> queue = new LinkedList<>();queue.offer(tree.root);List<List<Node<E>>> result = new ArrayList<>();while (!queue.isEmpty()) {// 此时队列的容量就是当前层的节点个数int levelSize = queue.size();ArrayList<Node<E>> levelNodes = new ArrayList<>();for (int i = 0; i < levelSize; i++) {Node<E> node = queue.poll();levelNodes.add(node);if (node.left != null) {queue.offer(node.left);}if (node.right!= null) {queue.offer(node.right);}}result.add(levelNodes);}return result;}private static String getBlankSpace(int n) {StringBuilder builder = new StringBuilder();while (n > 0) {builder.append("\t");n--;}return builder.toString();}/*** @description 根据节点个数，计算完全二叉树的高度* @author HelloWorld* @create 2024/1/2 19:48* @param nodeNums* @return int*/public static int getHeight(int nodeNums) {int level = 1;while (!(Math.pow(2, level - 1) <= nodeNums && Math.pow(2, level) > nodeNums)) {level++;}return level;}static class Node<E> {E element;Node<E> left;Node<E> right;public Node(E element) {this.element = element;this.left = null;this.right = null;}}
}