Article 123 - Data Structure Container

A Data Structure Container is one that wraps functions into one variable, which a client can call to operate on the data structure. In this article, we will create a Binary Search Tree Container with the common operations involving a Binary Search Tree such as adding, removing, and searching nodes.

For information about the Binary Tree Structure, see Article 31 - Programming Data Structures.

Interface

The container will combine the tree construction and search functionalities from the Binary Tree Implementation and Binary Search Tree Implementation articles.

For information about the Binary Search Tree Structure, see Article 121 - Binary Tree Implementation.
For information about the Binary Search Tree Structure, see Article 107 - Binary Search Tree Implementation.

Some common data structure function typically involve one or more of the following operations. Its interface can be summarized as the following.

  • New
  • Add
  • Remove
  • Get

Implementation

The example of Binary Search Tree Container requires at least the functions: New Binary Search Tree, Add Node, Remove Node, Search Node (Get).

Container Structure

typedef struct BinarySearchTree{
    int (*add)(Node **, int);
    int (*remove)(Node **, int);
    int (*search)(Node **, int);

} BinarySearchTree;

BinarySearchTree BinarySearchTreeContainer = {
    .add = addBSTNode;
    .remove = removeBSTNode;
    .search = searchBSTNode;
}

New Function

Not required for C implementation.

Add Node Function

static int addBSTNode( Node ** tree, int content ){
    return addNode( tree, content );
}

Remove Node Function

static int removeBSTNode( Node ** tree, int content ){
    return removeNode( tree, content );
}

Search Node Function

static int searchBSTNode( Node ** tree, int content ){
    return binarySearch( *tree, content ) != 0;    
}

Example Usage

int main(){
    Node * tree = 0;

    BinarySearchTreeContainer.add( &tree, 5 );
    BinarySearchTreeContainer.add( &tree, 10 );
    BinarySearchTreeContainer.add( &tree, 2 );
    BinarySearchTreeContainer.add( &tree, 3 );
    BinarySearchTreeContainer.add( &tree, 7 );
    BinarySearchTreeContainer.add( &tree, 1 );
    BinarySearchTreeContainer.add( &tree, 8 );

    BinarySearchTreeContainer.search( &tree, 7 );

    BinarySearchTreeContainer.remove( &tree, 3 );
    BinarySearchTreeContainer.search( &tree, 7 );
    BinarySearchTreeContainer.search( &tree, 3 );

    return 0;
}

Comments (0)

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


Vantasy World Copyright 2011 - 2017. Vantasy World is a project developed by Vantasy Online. Privacy Policy.