1package MyPackage;
2
3public class Tree {
4 static class Node {
5 int value;
6 Node left, right;
7
8 Node(int value){
9 this.value = value;
10 left = null;
11 right = null;
12 }
13 }
14
15 public void insert(Node node, int value) {
16 if (value < node.value) {
17 if (node.left != null) {
18 insert(node.left, value);
19 } else {
20 System.out.println(" Inserted " + value + " to left of " + node.value);
21 node.left = new Node(value);
22 }
23 } else if (value > node.value) {
24 if (node.right != null) {
25 insert(node.right, value);
26 } else {
27 System.out.println(" Inserted " + value + " to right of "
28 + node.value);
29 node.right = new Node(value);
30 }
31 }
32 }
33 public void traverseInOrder(Node node) {
34 if (node != null) {
35 traverseInOrder(node.left);
36 System.out.print(" " + node.value);
37 traverseInOrder(node.right);
38 }
39 }
40
41 public static void main(String args[])
42 {
43 Tree tree = new Tree();
44 Node root = new Node(5);
45 System.out.println("Binary Tree Example");
46 System.out.println("Building tree with root value " + root.value);
47 tree.insert(root, 2);
48 tree.insert(root, 4);
49 tree.insert(root, 8);
50 tree.insert(root, 6);
51 tree.insert(root, 7);
52 tree.insert(root, 3);
53 tree.insert(root, 9);
54 System.out.println("Traversing tree in order");
55 tree.traverseLevelOrder();
56
57 }
58}
59
60
1public class BinaryTree {
2
3 private int key;
4
5 private BinaryTree left, right;
6
7 /**
8 * Simple constructor.
9 *
10 * @param key
11 * to set as key.
12 */
13 public BinaryTree(int key) {
14 this.key = key;
15 }
16
17 /**
18 * Extended constructor.
19 *
20 * @param key
21 * to set as key.
22 * @param left
23 * to set as left child.
24 * @param right
25 * to set as right child.
26 */
27 public BinaryTree(int key, BinaryTree left, BinaryTree right) {
28 this.key = key;
29 setLeft(left);
30 setRight(right);
31 }
32
33 public int getKey() {
34 return key;
35 }
36
37 /**
38 * @return the left child.
39 */
40 public BinaryTree getLeft() {
41 return left;
42 }
43
44 /**
45 * @return the right child.
46 */
47 public BinaryTree getRight() {
48 return right;
49 }
50
51 public boolean hasLeft() {
52 return left != null;
53 }
54
55 public boolean hasRight() {
56 return right != null;
57 }
58
59 //Return a String representation of the BinaryTree using level order traversal
60 public String toString(){
61 int h = height(this);
62 int i;
63 String result = "";
64 for (i=1; i<=h; i++) {
65 result += printGivenLevel(this, i);
66 }
67 return result;
68 }
69
70 //returns the number of nodes in the BinaryTree
71 public int size(){
72 return size(this);
73 }
74
75 public static int size(BinaryTree tree){
76 if(tree == null) return 0;
77 return 1 + size(tree.getLeft()) + size(tree.getRight());
78 }
79
80 public int height(){ return height(this);}
81
82 public static int height(BinaryTree tree){
83 if(tree == null) return 0;
84 int left = height(tree.getLeft());
85 int right = height(tree.getRight());
86 return Math.max(left, right) + 1;
87 }
88
89 public String printGivenLevel (BinaryTree root ,int level) {
90 if (root == null) return "";
91 String result = "";
92 if (level == 1) {
93 result += root.getKey() + " ";
94 return result;
95 }else if (level > 1) {
96 String left = printGivenLevel(root.left, level-1);
97 String right = printGivenLevel(root.right, level-1);
98 return left + right;
99 }else{
100 return "";
101 }
102 }
103
104 /**
105 * @param left
106 * to set
107 */
108 public void setLeft(BinaryTree left) {
109 this.left = left;
110 }
111
112 /**
113 * @param right
114 * to set
115 */
116 public void setRight(BinaryTree right) {
117 this.right = right;
118 }
119}