Java Reference
In-Depth Information
/
**
ADTforbinarytreenodes
*
/
publicinterfaceBinNode<E>{
/
**
Getandsettheelementvalue
*
/
publicEelement();
publicvoidsetElement(Ev);
/
**
@returnTheleftchild
*
/
publicBinNode<E>left();
/
**
@returnTherightchild
*
/
publicBinNode<E>right();
/
**
@returnTrueifaleafnode,falseotherwise
*
/
publicbooleanisLeaf();
}
Figure5.5
A binary tree node ADT.
Example5.1
The preorder enumeration for the tree of Figure 5.1 is
ABDCEGFHI:
The first node printed is the root. Then all nodes of the left subtree are
printed (in preorder) before any node of the right subtree.
Alternatively, we might wish to visit each node only after we visit its children
(and their subtrees). For example, this would be necessary if we wish to return
all nodes in the tree to free store. We would like to delete the children of a node
before deleting the node itself. But to do that requires that the children's children
be deleted first, and so on. This is called a postorder traversal.
Example5.2
The postorder enumeration for the tree of Figure 5.1 is
DBGEHIFCA:
An inorder traversal first visits the left child (including its entire subtree), then
visits the node, and finally visits the right child (including its entire subtree). The
binary search tree of Section 5.4 makes use of this traversal to print all nodes in
ascending order of value.
Example5.3
The inorder enumeration for the tree of Figure 5.1 is
BDAGECHFI:
A traversal routine is naturally written as a recursive function. Its input param-
eter is a pointer to a node which we will call
rt
because each node can be viewed
