Java實現根據前序遍歷構建二叉樹（前序遍歷、中序遍歷、後序遍歷）

前言

Java關於ACM的代碼真的好少，想參考如何用java實現二叉樹google了一上午都沒找到資料，只能自己仿照之前寫的c代碼，實現一遍，供大家吐槽參考

題目

根據二叉樹前序遍歷序列例如：7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#，構建二叉樹，並且用前序、中序、後序進行遍歷

代碼

import java.util.Scanner;

public class BinaryTree {
public static String[] str;
public static int count;

/**
* 靜態內部類，定義二叉樹節點
*/
static class TreeNode {
public String data;
TreeNode lchild;
TreeNode rchild;

public TreeNode(String x) {
this.data = x;
}
}

/**
* 根據前序序列遞歸構建二叉樹
*
* @return
*/
public static TreeNode createBtree() {
TreeNode root = null;

if (count >= str.length || str[count++].equals("#")) {
root = null;
} else {
root = new TreeNode(str[count - 1]);
root.lchild = createBtree();
root.rchild = createBtree();
}

return root;
}

/**
* 前序遍歷
*
* @param root
*/
public static void preTraverse(TreeNode root) {
if (root != null) {
System.out.print(root.data + " ");
preTraverse(root.lchild);
preTraverse(root.rchild);
}
}

/**
* 中序遍歷
*
* @param root
*/
public static void inTraverse(TreeNode root) {
if (root != null) {
inTraverse(root.lchild);
System.out.print(root.data + " ");
inTraverse(root.rchild);
}
}

/**
* 後序遍歷
*
* @param root
*/
public static void postTraverse(TreeNode root) {
if (root != null) {
postTraverse(root.lchild);
postTraverse(root.rchild);
System.out.print(root.data + " ");
}
}

public static void main(String args[]) {
Scanner cin = new Scanner(System.in);

while (cin.hasNext()) {
String s = cin.nextLine();
str = s.split(",");

count = 0;

TreeNode root = createBtree();

// 前序遍歷
preTraverse(root);
System.out.println();

// 中序遍歷
inTraverse(root);
System.out.println();

// 後序遍歷
postTraverse(root);
System.out.println();
}
}
}