Java Reference
In-Depth Information
5
// class TreeNode definition
6
7
class
TreeNode<T extends Comparable<T>>
{
8
// package access members
9
TreeNode<T> leftNode;
10
T data;
// node value
11
TreeNode<T> rightNode;
12
13
// constructor initializes data and makes this a leaf node
14
public
TreeNode(T nodeData)
15
{
16
data = nodeData;
17
leftNode = rightNode =
null
;
// node has no children
18
}
19
20
// locate insertion point and insert new node; ignore duplicate values
21
public void
insert(T insertValue)
22
{
23
// insert in left subtree
24
if
(insertValue.compareTo(data) <
0
)
25
{
26
// insert new TreeNode
27
if
(leftNode ==
null
)
28
leftNode =
new
TreeNode<T>(insertValue);
29
else
// continue traversing left subtree recursively
30
leftNode.insert(insertValue);
31
}
32
// insert in right subtree
33
else if
(insertValue.compareTo(data) >
0
)
34
{
35
// insert new TreeNode
36
if
(rightNode ==
null
)
37
rightNode =
new
TreeNode<T>(insertValue);
38
else
// continue traversing right subtree recursively
39
rightNode.insert(insertValue);
40
}
41
}
42
}
// end class TreeNode
43
44
// class Tree definition
45
46
public class
Tree<T extends Comparable<T>>
{
47
private
TreeNode<T> root;
48
49
// constructor initializes an empty Tree of integers
50
public
Tree()
51
{
52
root =
null
;
53
}
54
55
// insert a new node in the binary search tree
56
public void
insertNode(T insertValue)
57
{
Fig. 21.17
|
TreeNode
and
Tree
class declarations for a binary search tree. (Part 2 of 4.)