Java Reference
In-Depth Information
You can use the following tree to help remember inorder, postorder, and preorder.
+
1
2
The inorder is
1 + 2
, the postorder is
1 2 +
, and the preorder is
+ 1 2
.
25.2.5 The
BST
Class
Following the design pattern of the Java Collections Framework API, we use an interface
named
Tree
to define all common operations for trees and provide an abstract class named
AbstractTree
that partially implements
Tree
, as shown in Figure 25.7. A concrete
BST
class can be defined to extend
AbstractTree
, as shown in Figure 25.8.
«interface»
java.lang.Iterable<E>
+
iterator(): Iterator<E>
Returns an iterator for traversing the elements in this collection
«interface»
Tree<E>
+
search(e: E): boolean
Returns true if the specified element is in the tree.
Returns true if the element is added successfully.
Returns true if the element is removed from the tree successfully.
Prints the nodes in inorder traversal.
+
insert(e: E): boolean
+
delete(e: E): boolean
+
inorder(): void
+
preorder(): void
+
postorder(): void
Prints the nodes in postorder traversal.
Returns the number of elements in the tree.
Returns true if the tree is empty.
Removes all elements from the tree.
+
getSize(): int
+
isEmpty(): boolean
+
clear(): void
AbstractTree<E>
F
IGURE
25.7
The
Tree
interface defines common operations for trees, and the
AbstractTree
class partially
implements
Tree
.
Listings 25.3, 25.4, and 25.5 give the implementations for
Tree
,
AbstractTree
, and
BST
.
L
ISTING
25.3
Tree.java
1
public interface
Tree<E>
extends
Iterable<E> {
2
interface
/** Return true if the element is in the tree */
3
public boolean
search(E e);
search
4
5
/** Insert element e into the binary search tree.
6
* Return true if the element is inserted successfully. */
7
public boolean
insert(E e);
insert
8
Search WWH ::
Custom Search