class TreeNode
public class Tree
1: // Fig. 17.17: Tree.java
2: // Definition of class TreeNode and class Tree.
3: package com.deitel.jhtp6.ch17;
4:
5: // class TreeNode definition
6: class TreeNode
7: {
8: // package access members
9: TreeNode leftNode; // left node
10: int data; // node value
11: TreeNode rightNode; // right node
12:
13: // constructor initializes data and makes this a leaf node
14: public TreeNode( int nodeData )
15: {
16: data = nodeData;
17: leftNode = rightNode = null; // node has no children
18: } // end TreeNode no-argument constructor
19:
20: // locate insertion point and insert new node; ignore duplicate values
21: public void insert( int insertValue )
22: {
23: // insert in left subtree
24: if ( insertValue < data )
25: {
26: // insert new TreeNode
27: if ( leftNode == null )
28: leftNode = new TreeNode( insertValue );
29: else // continue traversing left subtree
30: leftNode.insert( insertValue );
31: } // end if
32: else if ( insertValue > data ) // insert in right subtree
33: {
34: // insert new TreeNode
35: if ( rightNode == null )
36: rightNode = new TreeNode( insertValue );
37: else // continue traversing right subtree
38: rightNode.insert( insertValue );
39: } // end else if
40: } // end method insert
41: } // end class TreeNode
42:
43: // class Tree definition
44: public class Tree
45: {
46: private TreeNode root;
47:
48: // constructor initializes an empty Tree of integers
49: public Tree()
50: {
51: root = null;
52: } // end Tree no-argument constructor
53:
54: // insert a new node in the binary search tree
55: public void insertNode( int insertValue )
56: {
57: if ( root == null )
58: root = new TreeNode( insertValue ); // create the root node here
59: else
60: root.insert( insertValue ); // call the insert method
61: } // end method insertNode
62:
63: // begin preorder traversal
64: public void preorderTraversal()
65: {
66: preorderHelper( root );
67: } // end method preorderTraversal
68:
69: // recursive method to perform preorder traversal
70: private void preorderHelper( TreeNode node )
71: {
72: if ( node == null )
73: return;
74:
75: System.out.printf( "%d ", node.data ); // output node data
76: preorderHelper( node.leftNode ); // traverse left subtree
77: preorderHelper( node.rightNode ); // traverse right subtree
78: } // end method preorderHelper
79:
80: // begin inorder traversal
81: public void inorderTraversal()
82: {
83: inorderHelper( root );
84: } // end method inorderTraversal
85:
86: // recursive method to perform inorder traversal
87: private void inorderHelper( TreeNode node )
88: {
89: if ( node == null )
90: return;
91:
92: inorderHelper( node.leftNode ); // traverse left subtree
93: System.out.printf( "%d ", node.data ); // output node data
94: inorderHelper( node.rightNode ); // traverse right subtree
95: } // end method inorderHelper
96:
97: // begin postorder traversal
98: public void postorderTraversal()
99: {
100: postorderHelper( root );
101: } // end method postorderTraversal
102:
103: // recursive method to perform postorder traversal
104: private void postorderHelper( TreeNode node )
105: {
106: if ( node == null )
107: return;
108:
109: postorderHelper( node.leftNode ); // traverse left subtree
110: postorderHelper( node.rightNode ); // traverse right subtree
111: System.out.printf( "%d ", node.data ); // output node data
112: } // end method postorderHelper
113: } // end class Tree
114:
115: /**************************************************************************
116: * (C) Copyright 1992-2005 by Deitel & Associates, Inc. and *
117: * Pearson Education, Inc. All Rights Reserved. *
118: * *
119: * DISCLAIMER: The authors and publisher of this book have used their *
120: * best efforts in preparing the book. These efforts include the *
121: * development, research, and testing of the theories and programs *
122: * to determine their effectiveness. The authors and publisher make *
123: * no warranty of any kind, expressed or implied, with regard to these *
124: * programs or to the documentation contained in these books. The authors *
125: * and publisher shall not be liable in any event for incidental or *
126: * consequential damages in connection with, or arising out of, the *
127: * furnishing, performance, or use of these programs. *
128: *************************************************************************/