[next] [prev] [prev-tail] [tail] [up]

3.1.1 Data representation

A binary tree can be implemented in many ways. Here, we use a linked representation. The internal representation of a tree is illustrated in listing 1.


Listing 1:structtree
 
1struct _Node; 
2struct _Tree 
3{ 
4  struct _Node *pRoot; 
5};

In other words, a (struct _Tree) is just a pointer to a (struct _Node). Note how I declare (struct _Node) without defining it. An empty tree is represented by a NULL value in pRoot.

Next, we can define what a node looks like. Let us assume that v maps nodes to integers, then listing 2 illustrates how (struct _Node) should be defined:


Listing 2:structnode
 
1struct _Node 
2{ 
3  int value; 
4  struct _Tree left, right; 
5};

Both (struct _Tree) and (struct _Node) should be visible only in the implementation of binary search tree, but not to any consumer code. To the consumer code (exposed in the header file), only (struct Tree) should be visible, it is defined in listing 3.


Listing 3:fakestructtree
 
1struct Tree {};

[next] [prev] [prev-tail] [front] [up]