1 // Fig. 17.16: Tree.java
2 package com.deitel.jhtp2.ch17;
3
4 // Class TreeNode definition
5 class TreeNode {
6 // friendly access members
7 TreeNode left; // left node
8 int data; // data item
9 TreeNode right; // right node
10
11 // Constructor: initialize data to d and make this a leaf node
12 public TreeNode( int d )
13 {
14 data = d;
15 left = right = null; // this node has no children
16 }
17
18 // Insert a TreeNode into a Tree that contains nodes.
19 // Ignore duplicate values.
20 public synchronized void insert( int d )
21 {
22 if ( d < data ) {
23 if ( left == null )
24 left = new TreeNode( d );
25 else
26 left.insert( d );
27 }
28 else if ( d > data ) {
29 if ( right == null )
30 right = new TreeNode( d );
31 else
32 right.insert( d );
33 }
34 }
35 }
36
37 // Class Tree definition
38 public class Tree {
39 private TreeNode root;
40
41 // Construct an empty Tree of integers
42 public Tree() { root = null; }
43
44 // Insert a new node in the binary search tree.
45 // If the root node is null, create the root node here.
46 // Otherwise, call the insert method of class TreeNode.
47 public synchronized void insertNode( int d )
48 {
49 if ( root == null )
50 root = new TreeNode( d );
51 else
52 root.insert( d );
53 }
54
55 // Preorder Traversal
56 public void preorderTraversal() { preorderHelper( root ); }
57
58 // Recursive method to perform preorder traversal
59 private void preorderHelper( TreeNode node )
60 {
61 if ( node == null )
62 return;
63
64 System.out.print( node.data + " " );
65 preorderHelper( node.left );
66 preorderHelper( node.right );
67 }
68
69 // Inorder Traversal
70 public void inorderTraversal() { inorderHelper( root ); }
71
72 // Recursive method to perform inorder traversal
73 private void inorderHelper( TreeNode node )
74 {
75 if ( node == null )
76 return;
77
78 inorderHelper( node.left );
79 System.out.print( node.data + " " );
80 inorderHelper( node.right );
81 }
82
83 // Postorder Traversal
84 public void postorderTraversal() { postorderHelper( root ); }
85
86 // Recursive method to perform postorder traversal
87 private void postorderHelper( TreeNode node )
88 {
89 if ( node == null )
90 return;
91
92 postorderHelper( node.left );
93 postorderHelper( node.right );
94 System.out.print( node.data + " " );
95 }
96 }