Java Reference
In-Depth Information
tree would not embody the following characteristic of binary search trees (with no duplicate val-
ues):
The values in any left subtree are less than the value in the parent node, and the values in any right
subtree are greater than the value in the parent node.
Which node is used as a
replacement node
to maintain this characteristic? It's either the node
containing the largest value in the tree less than the value in the node being deleted, or the node
containing the smallest value in the tree greater than the value in the node being deleted. Let's con-
sider the node with the smaller value. In a binary search tree, the largest value less than a parent's
value is located in the left subtree of the parent node and is guaranteed to be contained in the right-
most node of the subtree. This node is located by walking down the left subtree to the right until
the reference to the right child of the current node is null. We're now referencing the replacement
node, which is either a leaf node or a node with one child to its left. If the replacement node is a
leaf node, the steps to perform the deletion are as follows:
a) Store the reference to the node to be deleted in a temporary reference variable.
b) Set the reference in the parent of the node being deleted to reference the replacement
node.
c) Set the reference in the parent of the replacement node to
null
.
d) Set the reference to the right subtree in the replacement node to reference the right sub-
tree of the node to be deleted.
e) Set the reference to the left subtree in the replacement node to reference the left subtree
of the node to be deleted.
The deletion steps for a replacement node with a left child are similar to those for a replace-
ment node with no children, but the algorithm also must move the child into the replacement
node's position in the tree. If the replacement node is a node with a left child, the steps to perform
the deletion are as follows:
a) Store the reference to the node to be deleted in a temporary reference variable.
b) Set the reference in the parent of the node being deleted to refer to the replacement
node.
c) Set the reference in the parent of the replacement node to reference the left child of the
replacement node.
d) Set the reference to the right subtree in the replacement node to reference the right sub-
tree of the node to be deleted.
e) Set the reference to the left subtree in the replacement node to reference the left subtree
of the node to be deleted.
Write m eth od
deleteNode
, which takes as its argument the value to delete. Method
delete-
Node
should locate in the tree the node containing the value to delete and use the algorithms dis-
cussed here to delete the node. If the value is not found in the tree, the method should display a
message saying so. Modify the program of Figs. 21.17 and 21.18 to use this method. After deleting
an item, call the methods
inorderTraversal
,
preorderTraversal
and
postorderTraversal
to con-
firm that the delete operation was performed correctly.
21.23
(Binary Tree Search)
Modify class
Tree
of Fig. 21.17 to include method
contains
, which
attempts to locate a specified value in a binary-search-tree object. The method should take as an ar-
gument a search key to locate. If the node containing the search key is found, the method should
return a reference to that node's data; otherwise, it should return
null
.
21.24
(Level-Order Binary Tree Traversal)
The program of Figs. 21.17 and 21.18 illustrated
three recursive methods of traversing a binary tree—inorder, preorder and postorder traversals. This
exercise presents the
level-order traversal
of a binary tree, in which the node values are printed level
by level, starting at the root node level. The nodes on each level are printed from left to right. The
level-order traversal is not a recursive algorithm. It uses a queue object to control the output of the
nodes. The algorithm is as follows:
a)
Insert the root node in the queue.
