Created
March 18, 2019 08:57
-
-
Save LeeReindeer/9db8eaaad28e175a4a95e561876db752 to your computer and use it in GitHub Desktop.
Binary Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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