Java Reference
In-Depth Information
/
**
GeneraltreenodeADT
*
/
interfaceGTNode<E>{
publicEvalue();
publicbooleanisLeaf();
publicGTNode<E>parent();
publicGTNode<E>leftmostChild();
publicGTNode<E>rightSibling();
publicvoidsetValue(Evalue);
publicvoidsetParent(GTNode<E>par);
publicvoidinsertFirst(GTNode<E>n);
publicvoidinsertNext(GTNode<E>n);
publicvoidremoveFirst();
publicvoidremoveNext();
}
/
**
GeneraltreeADT
*
/
interfaceGenTree<E>{
publicvoidclear(); //Clearthetree
publicGTNode<E>root();//Returntheroot
//Makethetreehaveanewroot,givefirstchildandsib
publicvoidnewroot(Evalue,GTNode<E>first,
GTNode<E>sib);
publicvoidnewleftchild(Evalue);//Addleftchild
}
Figure6.2
Interfaces for the general tree and general tree node
One choice would be to provide a function that takes as its parameter the index
for the desired child. That combined with a function that returns the number of
children for a given node would support the ability to access any node or process
all children of a node. Unfortunately, this view of access tends to bias the choice for
node implementations in favor of an array-based approach, because these functions
favor random access to a list of children. In practice, an implementation based on
a linked list is often preferred.
An alternative is to provide access to the first (or leftmost) child of a node, and
to provide access to the next (or right) sibling of a node. Figure 6.2 shows class
declarations for general trees and their nodes. Based on these two access functions,
the children of a node can be traversed like a list. Trying to find the next sibling of
the rightmost sibling would return
null
.
6.1.2
General Tree Traversals
In Section 5.2, three tree traversals were presented for binary trees: preorder, pos-
torder, and inorder. For general trees, preorder and postorder traversals are defined
with meanings similar to their binary tree counterparts. Preorder traversal of a gen-
eral tree first visits the root of the tree, then performs a preorder traversal of each
subtree from left to right. A postorder traversal of a general tree performs a pos-
torder traversal of the root's subtrees from left to right, then visits the root. Inorder
