Java Reference
In-Depth Information
/
**
Binarytreenodeimplementation:Pointerstochildren
@paramEThedataelement
@paramKeyTheassociatedkeyfortherecord
*
/
classBSTNode<Key,E>implementsBinNode<E>{
privateKeykey; //Keyforthisnode
privateEelement; //Elementforthisnode
privateBSTNode<Key,E>left;//Pointertoleftchild
privateBSTNode<Key,E>right;//Pointertorightchild
/
**
Constructors
*
/
publicBSTNode(){left=right=null;}
publicBSTNode(Keyk,Eval)
{left=right=null;key=k;element=val;}
publicBSTNode(Keyk,Eval,
BSTNode<Key,E>l,BSTNode<Key,E>r)
{left=l;right=r;key=k;element=val;}
/
**
Getandsetthekeyvalue
*
/
publicKeykey(){returnkey;}
publicvoidsetKey(Keyk){key=k;}
/
**
Getandsettheelementvalue
*
/
publicEelement(){returnelement;}
publicvoidsetElement(Ev){element=v;}
/
**
Getandsettheleftchild
*
/
publicBSTNode<Key,E>left(){returnleft;}
publicvoidsetLeft(BSTNode<Key,E>p){left=p;}
/
**
Getandsettherightchild
*
/
publicBSTNode<Key,E>right(){returnright;}
publicvoidsetRight(BSTNode<Key,E>p){right=p;}
/
**
@returnTrueifaleafnode,falseotherwise
*
/
publicbooleanisLeaf()
{return(left==null)&&(right==null);}
}
Figure5.7
A binary tree node class implementation.
As an example of a tree that stores different information at the leaf and inter-
nal nodes, consider the expression tree illustrated by Figure 5.9. The expression
tree represents an algebraic expression composed of binary operators such as ad-
dition, subtraction, multiplication, and division. Internal nodes store operators,
while the leaves store operands. The tree of Figure 5.9 represents the expression
4x(2x + a) c. The storage requirements for a leaf in an expression tree are quite
different from those of an internal node. Internal nodes store one of a small set of
operators, so internal nodes could store a small code identifying the operator such
as a single byte for the operator's character symbol. In contrast, leaves store vari-
able names or numbers, which is considerably larger in order to handle the wider
range of possible values. At the same time, leaf nodes need not store child pointers.
