Skip to content

Instantly share code, notes, and snippets.

@LeeReindeer
Created March 18, 2019 08:57
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save LeeReindeer/9db8eaaad28e175a4a95e561876db752 to your computer and use it in GitHub Desktop.
Binary Tree
import java.util.ArrayList;
import java.util.Scanner;
/**
* @author leer
* Created at 3/15/19 8:19 PM
*/
public class BinaryTree<T> {
public static class TreeNode<T> {
TreeNode left, right;
Comparable<T> key;
public TreeNode() {
}
public TreeNode(TreeNode left, TreeNode right, Comparable<T> key) {
this.left = left;
this.right = right;
this.key = key;
}
@Override
public String toString() {
return key.toString() + " ";
}
}
private TreeNode root = new TreeNode();
public BinaryTree() {
System.out.println("Input node in preOrder:");
root = buildTree(root);
}
public BinaryTree(TreeNode root) {
this.root = root;
}
private ArrayList<TreeNode> preOrderList = new ArrayList<>();
private ArrayList<TreeNode> inOrderList = new ArrayList<>();
private ArrayList<TreeNode> postOrderList = new ArrayList<>();
private void preOrder(TreeNode root) {
if (root == null) {
return;
}
preOrderList.add(root);
preOrder(root.left);
preOrder(root.right);
}
private void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
inOrderList.add(root);
inOrder(root.right);
}
private void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
postOrderList.add(root);
}
public ArrayList<TreeNode> getPreOrderList() {
preOrderList.clear();
preOrder(root);
return preOrderList;
}
public ArrayList<TreeNode> getInOrderList() {
inOrderList.clear();
inOrder(root);
return inOrderList;
}
public ArrayList<TreeNode> getPostOrderList() {
postOrderList.clear();
postOrder(root);
return postOrderList;
}
private Scanner scanner = new Scanner(System.in);
public TreeNode buildTree(TreeNode root) {
int key = scanner.nextInt();
if (key == -1) {
root = null;
} else {
root = new TreeNode(null, null, key);
root.left = buildTree(root.left);
root.right = buildTree(root.right);
}
// return back the copy
return root;
}
public static void main(String[] args) {
// TreeNode<Integer> node1 = new TreeNode<>(null, null, 1);
// TreeNode<Integer> node2 = new TreeNode<>(null, null, 2);
// TreeNode<Integer> node3 = new TreeNode<>(null, null, 10);
// TreeNode<Integer> node4 = new TreeNode<>(node1, node2, 7);
// TreeNode<Integer> node5 = new TreeNode<>(node3, null, 6);
// TreeNode<Integer> root = new TreeNode<>(node4, node5, 5);
// BinaryTree<Integer> binaryTree = new BinaryTree<>(root);
// input 5 7 1 -1 -1 2 -1 -1 6 10 -1 -1 -1
BinaryTree<Integer> binaryTree = new BinaryTree<>();
System.out.println(binaryTree.getPreOrderList().toString());
System.out.println(binaryTree.getInOrderList().toString());
System.out.println(binaryTree.getPostOrderList().toString());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment