Wednesday, May 11, 2011

binary search tree c/c++ - 2

Following example code is another implementation of binary search tree in C++ language. Binary search tree is a data structure that shows log(n) search time.

1. tree node data structure.
typedef struct BTREE {
     char data;
     struct BTREE *left, *right;
} BTREE;


2. traversals for preorder, inorder, postorder.
int preorder(BTREE *t)
{
     if ( t != NULL) {
         printf("%c", t->data);
         preorder(t->left);
         preorder(t->right);
     }
}

int inorder(BTREE *t)
{
     if ( t != NULL) {
         inorder(t->left);
         printf("%c", t->data);
         inorder(t->right);
     }
}

int postorder(BTREE *t)
{
     if ( t != NULL) {
         postorder(t->left);
         postorder(t->right);
         printf("%c", t->data);
     }
}

3. swap_tree routine.
int swap_tree(BTREE *t)
{
    BTREE *p;

    if( t == NULL)
        return NULL;
    else {
        p = (BTREE *) malloc(sizeof(BTREE));
        p->left = swap_tree(t->right);
        p->right = swap_tree(t->left);
        p->data = t->data;
        return p;
    }
}

4. tree copy
int tree_copy(BTREE *t)
{
    BTREE *p;

    if( t == NULL)
        return NULL;
    else {
        p = (BTREE *) malloc(sizeof(BTREE));
        p->left = tree_copy(t->left);
        p->right = tree_copy(t->right);
        p->data = t->data;
        return p;
    }
}

5. getting max depth of the tree.
int max_depth(BTREE *t)
{
    int max = 0, depth;

    if( t == NULL)
        return 0;
    else {
         depth = max_depth(t->left) + 1;
         if( depth > max)
              max = depth;
         depth = max_depth(t->right) + 1;
         if( depth > max)
              max = depth;
         return max;
    }


}