Java Reference
In-Depth Information
Display 15.40
A Binary Search Tree for Integers
(part 2 of 2)
37
/**
38
Returns the root node of a tree that is the tree with root node
39
subTreeRoot, but with a new node added that contains item.
40
*/
41
private
static
IntTreeNode insertInSubtree(
int
item,
42
IntTreeNode subTreeRoot)
43
{
44
if
(subTreeRoot ==
null
)
45
return
new
IntTreeNode(item,
null
,
null
);
46
else
if
(item < subTreeRoot.data)
47
{
48
subTreeRoot.leftLink = insertInSubtree(item, subTreeRoot.leftLink);
49
return
subTreeRoot;
50
}
51
else
//item >= subTreeRoot.data
52
{
53
subTreeRoot.rightLink = insertInSubtree(item, subTreeRoot.rightLink);
54
return
subTreeRoot;
55
}
56
}
57
private
static
boolean
isInSubtree(
int
item, IntTreeNode subTreeRoot)
58
{
59
if
(subTreeRoot ==
null
)
60
return
false
;
61
else
if
(subTreeRoot.data == item)
62
return
true
;
63
else
if
(item < subTreeRoot.data)
64
return
isInSubtree(item, subTreeRoot.leftLink);
65
else
//item >= link.data
66
return
isInSubtree(item, subTreeRoot.rightLink);
67
}
68
private
static
void
showElementsInSubtree(IntTreeNode subTreeRoot)
69
{
//Uses inorder traversal.
70
if
(subTreeRoot !=
null
)
71
{
72
showElementsInSubtree(subTreeRoot.leftLink);
73
System.out.print(subTreeRoot.data + " ");
74
showElementsInSubtree(subTreeRoot.rightLink);
75
}
//else do nothing. Empty tree has nothing to display.
76
}
77
}
