The algorithms we present here are all recursive, based on the following class definition:
class TreeNode {
public int key;
public TreeNode lchild;
public TreeNode rchild;
public TreeNode(int k) {
key = k; lchild = null; rchild = null;
}
public TreeNode(int k, TreeNode L, TreeNodeR) {
key = k; lchild = L; rchild = R;
}
};
The class which uses this TreeNode has a member root, initialized to null, effectively
as if the following had been written:
TreeNode root = null;
For the most part, the tree algorithms are generalizations of the recursive list algorithms, but accounting for the fact that there are two "next" pointers, one going left ("lchild") and one going right ("rchild"); hence a tree is a two-dimensional structure compared with one dimensional lists. It is instructive to compare these algorithms with the recursive list algorithms given above, keeping this in mind.
The size of a tree is the number of nodes:
int size( TreeNode p ) {
if( p == null ) {
return 0;
else
return ( 1 + size( lchild ) + size( rchild ) );
}
The height of a tree is the length of the longest path in the tree (i.e., the number of links traversed). Counter-intuitively, the height of a null tree is -1.
int max( int n, int m){
if (n<m)
return m;
else
return n;
}
int height( TreeNode p ) {
if( p == null ) {
return -1;
else
return ( 1 + max(height( lchild ), height( rchild ) ) );
}
This function returns a pointer to the node containing the integer N, or null if not found:
TreeNode find( int N, TreeNode p ) {
if( p == null ) {
return null;
else if ( p.key == N )
return p;
else if ( p.key < N )
return find( N, p.rchild );
else
return find( N, p.lchild );
}
This function uses a reference parameter to simplify the case involving the empty tree; otherwise, it is very similar to find:
insert( int N, TreeNode p ) {
if( p == null )
p = TreeNode( N, null, null );
else if ( p.key == N )
;
else if ( p.key < N )
insert( N, p.rchild );
else
insert( N, p.lchild );
}
Here, we will simply print out the key in the nodes; but we could perform any arbitrary action on the tree nodes. We start with a simple inorder traversal:
void traverse( TreeNode t ) {
if (t != null) {
traverse( t.lchild ); // L
System.out.println(t.key); // V
traverse( t.rchild ); // R
}
}
By rearranging the three statements L, V, and R in the body of the if, we can
print the nodes in any order we desire:
Preorder V L R
Inorder L V R
Postorder L R V
Reverse Preorder V R L
ReverseInorder R V L
ReversePostorder R L V
This algorithm is a little complex, due to the number of special cases.
delete( int n, TreeNode t ) {
TreeNode p;
if (t == null)
;
else if (n < t.key)
delete( n, t.lchild );
else if (n > t.key)
delete( n, t.rchild );
else if (t.lchild == null) {// Must have: n == t.key
p = t; // so want to delete this node
t = t.rchild;
delete p;
}
else if (t.rchild == null) {
p = t;
t = t.lchild;
delete p;
}
else if (t.rchild.lchild == null) {
p = t;
t.rchild.lchild = t.lchild;
t = t.rchild;
delete p;
}
else {
TreeNode q;
for(p = t.rchild; p.lchild != null; q = p, p = p.lchild)
;
q.lchild = p.rchild;
p.rchild = t.rchild;
p.lchild = t.lchild;
delete t;
t = p;
}
}
Some other algorithms you might want to write to manipulate trees are: