package Tree_Java; import java.io.*; public class BinaryTree2{ //Part 1/2. Define the tree node. //A generic verions using for types. Or can be deleted, type "E" can be changed to "Object". //Binary trees can also be implemented using Java arrays. protected static class Node{ protected E data; protected Node left; protected Node right; public Node(E data) { this.data = data; left = null; right = null; } public String toString() { return data.toString(); } } //Part 2/2. Define the tree. //instance variable protected Node root; //Three versions of constructors public BinaryTree2() { root = null; } protected BinaryTree2(Node root) { this.root = root; } public BinaryTree2(E data, BinaryTree2 leftTree, BinaryTree2 rightTree) { root = new Node(data); if (leftTree != null) root.left = leftTree.root; else root.left = null; if (rightTree != null) root.right = rightTree.root; else root.right = null; } public BinaryTree2 getLeftSubtree() { if (root != null && root.left != null) return new BinaryTree2(root.left); else return null; } public BinaryTree2 getRightSubtree() { if (root != null && root.right != null) return new BinaryTree2(root.right); else return null; } boolean isLeaf() { return (root.left == null && root.right == null); } //Define private utility methods for pre-, post-, and in-order traversals. //Not parts of the application interface. Not be called by testers. private void preOrderTraverse(Node node, int depth, StringBuffer sb) { if (node == null) sb.append(""); else { for (int i = 0; i < depth; i++) sb.append(" "); sb.append(node.toString()); sb.append("\n"); preOrderTraverse(node.left, depth + 1, sb); preOrderTraverse(node.right, depth + 1, sb); } } private void postOrderTraverse(Node node, int depth, StringBuffer sb) { if (node == null) sb.append(""); else { postOrderTraverse(node.left, depth + 1, sb); postOrderTraverse(node.right, depth + 1, sb); for (int i = 0; i < depth; i++) sb.append(" "); sb.append(node.toString()); sb.append("\n"); } } private void inOrderTraverse(Node node, int depth, StringBuffer sb) { if (node == null) sb.append(""); else { inOrderTraverse(node.left, depth + 1, sb); for (int i = 0; i < depth; i++) sb.append(" "); sb.append(node.toString()); sb.append("\n"); inOrderTraverse(node.right, depth + 1, sb); } } public String toString() { StringBuffer sb = new StringBuffer(); sb.append("Pre-order traversal of the tree is:\n"); preOrderTraverse(root, 0, sb); sb.append("Post-order traversal of the tree is:\n"); postOrderTraverse(root, 0, sb); sb.append("In-order traversal of the tree is:\n"); inOrderTraverse(root, 0, sb); return sb.toString(); } }