import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main4 {
public class Node{
public String value;
public Node left;
public Node right;
public Node(String value,Node left,Node right){
this.value = value;
this.left = left;
this.right = right;
}
public Node(String value) {
this.value = value;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
public static List<Node> list = new ArrayList<Node>();
class Creater{
public void createTree(String[] arr){
for(int i = 0;i < arr.length;i++){
if (!arr[i].equals("#")) {
Node node = new Node(arr[i], null, null);
list.add(node);
}else{
Node node = null;
list.add(node);
}
}
if (list.size() > 0) {
for(int i = 0;i < arr.length/2-1;i++){
if (list.get(2*i+1) != null) {
list.get(i).left = list.get(2*i+1);
}
if (list.get(2*i+2) != null) {
list.get(i).right = list.get(2*i+2);
}
}
}
int lastIndex = arr.length/2-1;
list.get(lastIndex).left = list.get(lastIndex*2+1);
if (arr.length % 2 == 1) {
list.get(lastIndex).right = list.get(lastIndex*2+2);
}
}
}
public static void prePrint(Node node){
if (node != null) {
System.out.print(node.value + " ");
prePrint(node.left);
prePrint(node.right);
}
}
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
public static void theFirstTraversal(Node root) { //先序遍历
System.out.print(root.getValue() + " ");
if (root.getLeft() != null) { //使用递归进行遍历左孩子
theFirstTraversal(root.getLeft());
}
if (root.getRight() != null) { //递归遍历右孩子
theFirstTraversal(root.getRight());
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String string = in.nextLine();
String[] arrString = string.split(" ");
for (int i = 0; i < arrString.length; i++) {
arrString[i] = arrString[i].toString();
}
Main4 m4 = new Main4();
Creater c = m4.new Creater();
c.createTree(arrString);
printTree(list.get(0));
theFirstTraversal(list.get(0));
System.out.println();
prePrint(list.get(0));
}
}
测试结果：
1 2 3 # # 6 7 # # # # # # # 8
Binary Tree:
v8v
v7v
v3v
^6^
H1H
^2^
网友评论