|
package com.chaojilaji.book.tree;
import com.chaojilaji.auto.autocode.utils.Json;
import com.chaojilaji.auto.autocode.utils.MathUtils;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
public class Handle {
/**
* 前序建树
*
* @param input
* @param index
* @return
*/
public static Tree buildTreePrologue(int[] input, int index) {
// TODO: 2022/1/12 根节点就是当前index这个节点
Tree tree = new Tree();
tree.setValue(input[index]);
// TODO: 2022/1/12 左右两个节点分别为 2*index-1和2*index+1
int[] children = new int[]{2 * index + 1, 2 * index + 2};
if (children[0] < input.length) {
tree.setLeftChild(buildTreePrologue(input, children[0]));
}
if (children[1] < input.length) {
tree.setRightChild(buildTreePrologue(input, children[1]));
}
return tree;
}
/**
* 中序建树
*
* @param input
* @param height
* @param maxHeight
* @return
*/
public static Tree buildTree2(Queue<Integer> input, int height, int maxHeight) {
// TODO: 2022/1/12 根节点就是当前index这个节点
Tree tree = new Tree();
if (height < maxHeight) {
tree.setLeftChild(buildTree2(input, height + 1, maxHeight));
}
if (!input.isEmpty()) {
tree.setValue(input.poll());
}
if (height < maxHeight) {
tree.setRightChild(buildTree2(input, height + 1, maxHeight));
}
return tree;
}
/**
* 后序建树
*
* @return
*/
public static Tree buildTree3(Queue<Integer> input, int height, int maxHeight) {
// TODO: 2022/1/12 根节点就是当前index这个节点
Tree tree = new Tree();
if (height < maxHeight) {
tree.setLeftChild(buildTree3(input, height + 1, maxHeight));
}
if (height < maxHeight) {
tree.setRightChild(buildTree3(input, height + 1, maxHeight));
}
if (!input.isEmpty()) {
tree.setValue(input.poll());
}
return tree;
}
public static void print1(Tree tree) {
if (Objects.isNull(tree)) return;
if (Objects.nonNull(tree.getValue())) {
System.out.print(tree.getValue());
}
if (Objects.nonNull(tree.getLeftChild())) {
print1(tree.getLeftChild());
}
if (Objects.nonNull(tree.getRightChild())) {
print1(tree.getRightChild());
}
}
public static void print2(Tree tree) {
if (Objects.isNull(tree)) return;
if (Objects.nonNull(tree.getLeftChild())) {
print2(tree.getLeftChild());
}
if (Objects.nonNull(tree.getValue())) {
System.out.print(tree.getValue());
}
if (Objects.nonNull(tree.getRightChild())) {
print2(tree.getRightChild());
}
}
public static void print3(Tree tree) {
if (Objects.isNull(tree)) return;
if (Objects.nonNull(tree.getLeftChild())) {
print3(tree.getLeftChild());
}
if (Objects.nonNull(tree.getRightChild())) {
print3(tree.getRightChild());
}
if (Objects.nonNull(tree.getValue())) {
System.out.print(tree.getValue());
}
}
public static void demoPrint() {
int[] a = new int[]{1, 2, 3, 4, 5, 6, 7};
Tree tree = buildTreePrologue(a, 0);
print1(tree);
System.out.println();
print2(tree);
System.out.println();
print3(tree);
}
public static void main(String[] args) {
demoPrint();
}
}
|
