Binary search tree

BSTree.h

#include <deque>

 

 

using namespace std;

#ifndef BSTREE_H_INCLUDED
#define BSTREE_H_INCLUDED

typedef int ElementType;
struct TreeNode;

/*struct TreeNode
{
    ElementType Element;
    struct TreeNode* Left;
    struct TreeNode* Right;
} ;*/

typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

// re-use the TreeNode to create a doulbe linklist
typedef struct TreeNode *DoubleLink;

DoubleLink convertBST2DLink( SearchTree T, DoubleLink dl );
DoubleLink InitDoubleLink( DoubleLink DL );
void traverseDL ( DoubleLink dl );

void traverseDL2 ( DoubleLink dl );

Position Find( ElementType X, SearchTree T );
Position FindMin( SearchTree T );
Position FindMax( SearchTree T );

SearchTree MakeEmpty( SearchTree T );
SearchTree Insert( ElementType X, SearchTree T );
SearchTree Delete( ElementType X, SearchTree T );

ElementType Retrieve( Position P );

void Print_InOrder( SearchTree T );

void Print_PreOrder( SearchTree T );

int Tree_Height( SearchTree T, int *height );

int IS_Balance_Tree( SearchTree T, int *isBalanced );

/**
* given 2 node p1, p2, find the common and closet parent
**/
int find_Common_Closest_Ancestor( SearchTree T, Position p1, Position p2, Position **ancestor );

/**
* bfs travel the tree, level by level
**/
void Breadth_First_Traversal( SearchTree T );

void Print_Tree_By_Level( SearchTree T );

void Print_Tree_For_Certain_Level( SearchTree T, int Level );

void Find_Sum_Path( SearchTree T, int *sum );

void Node_Path( SearchTree T, const int value, int sum, deque<int>& dq );

void Print_Node_Path(const SearchTree T, int value);

void Make_Tree_Mirror( const SearchTree T );

#endif

 

BSTree.cpp

#include "BSTree.h"
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <deque>

using namespace std;

struct TreeNode
{
    ElementType Element;
    SearchTree Left;
    SearchTree Right;
};

SearchTree MakeEmpty( SearchTree T )
{
    if( T != NULL )
    {
        MakeEmpty( T->Left );
        MakeEmpty( T->Right);
        free( T );
    }
    return NULL;
}

Position Find( ElementType X, SearchTree T )
{
    if( T == NULL )
    {
        return NULL;
    }
    if( X < T->Element )
    {
        return Find( X, T->Left );
    }
    else if( X > T->Element )
    {
        return Find(X, T->Right );
    }
    else
    {
        return T;
    }
}

Position FindMin( SearchTree T )
{
    if( T == NULL )
    {
        return NULL;
    }
    // if T's left child is null, then T should be the min
    else if( T->Left == NULL )
    {
        return T;
    }
    // if T has left and T->left is not null, go to its left
    else
    {
        return FindMin( T->Left );
    }
}

Position FindMax( SearchTree T )
{
    if( T == NULL )
    {
        return NULL;
    }
    else if( T->Right == NULL )
    {
        return T;
    }
    else
    {
        return FindMax( T->Right );
    }
}

SearchTree Insert( ElementType X, SearchTree T )
{
    if( T == NULL )
    {
        // create and return a one-node tree
        T = (SearchTree )malloc( sizeof( struct TreeNode ) );
        // allocate memory failed
        if( T == NULL )
        {
            printf( "out of memory...!!!\n" );
        }
        else
        {
            T->Element = X;
            T->Left = NULL;
            T->Right = NULL;
        }
    }
    else if( X < T->Element )
    {
        // when you find the position to insert X , you need to the connection between
        // the new added node and its parent. otherwise, after you find the position, you
        // would create a TreeNode 'T', but you didn't link it, the newly created node
        // would be a isolated node. When X < T->Element, it would be T's left Child, so
        // you need T->Left = *** instead of Just call 'Insert( X, T->Left )'
        T->Left = Insert( X, T->Left );
    }
    else if( X > T->Element )
    {
        T->Right = Insert( X, T->Right );
    }
    // if X == T->Element, do nothing
    return  T;
}

SearchTree Delete( ElementType X, SearchTree T )
{
    Position tempCell;

    if( T == NULL )
    {
        printf( "Element not found...\n" );
    }
    else if( X < T->Element )
    {
        T->Left = Delete( X, T->Left );
    }
    else if( X > T->Element )
    {
        T->Right = Delete( X, T->Right );
    }
    // found the element to be deleted, and the element has both children
    else if( T->Left && T->Right )
    {
        tempCell = FindMin( T->Right );
        // replace need to be deleted element's value with the min value in right substree
        T->Element = tempCell->Element;
        // then remove the min value from right subtree
        T->Right = Delete( T->Element, T->Right );
    }
    // found the element, and the element has only 1 or 0 children
    else
    {
        tempCell = T;
        if( T->Left == NULL )
        {
            T = T->Right;
        }
        else if( T->Right == NULL )
        {
            T = T->Left;
        }
        free( tempCell );
    }
    return T;
}

ElementType Retrieve( Position P )
{
    return P->Element;
}

void Print_InOrder( SearchTree T )
{
    if( T != NULL )
    {
        Print_InOrder( T->Left );
        printf( "element : %d\n ", T->Element );
        Print_InOrder( T->Right );
    }
/*    else
    {
        printf( "empty tree\n" );
    }*/
}

void Print_PreOrder( SearchTree T )
{
    if( T != NULL )
    {
        printf( "element : %d\n ", T->Element );
        Print_PreOrder( T->Left );
        Print_PreOrder( T->Right );
    }
}

DoubleLink InitDoubleLink( DoubleLink DL )
{
    if( DL == NULL )
    {
        // create and return a one-node tree
        DL = (DoubleLink )malloc( sizeof( struct TreeNode ) );
        // allocate memory failed
        if( DL == NULL )
        {
            printf( "out of memory...!!!\n" );
        }
        else
        {
            DL->Element = -1;
            DL->Left = NULL;
            DL->Right = NULL;
        }
    }
    return DL;
}

// convert an binary search tree to double link
// pre-order to traverse the tree( left child -> node -> right child )
// convert the   A
//              / \
//              B  C
// to be    NULL<-(left)-B-(right)-><-(left)-A-(right)-><-(left)-C-(left)->NULL
// parent's left pointer points to left child, its right pointer point to right child
// left child's left pointer points to preceding node(if any ), its right pointer points to parent
// right child's left pointer points to parent, its right pointer points to following node
// recursively build such a link
DoubleLink convertBST2DLink( SearchTree T, DoubleLink dl )
{
    if( T== NULL )
        return NULL;
    // pre-order, firstly go to its left child to do conversion
    if( T->Left != NULL )
    {
        dl = convertBST2DLink( T->Left, dl );
    }
    // got this : NULL<-(left)-B and B<-(left)-A
    T->Left = dl;
    if( dl != NULL )
    {
        // got this : B-(right)->A and A-(right)->C
        dl->Right = T;
    }
    // dl would B A C recursively
    dl = T;
    // pre-order, go to rights
    if( T->Right != NULL )
    {
        dl = convertBST2DLink( T->Right, dl );
    }
    return dl;
}

void traverseDL ( DoubleLink dl )
{
    while( dl->Right != NULL )
    {
        printf( "%d\n", dl->Element );
        dl = dl->Right;
    }
}

void traverseDL2 ( DoubleLink dl )
{
    while( dl->Left != NULL )
    {
        printf( "%d\n", dl->Element );
        dl = dl->Left;
    }
}

// got the furthest node distance between 2 nodes in a bst
// we just need to get the max{tree's left height} + max{tree's right height}
int Tree_Height( SearchTree T, int *height )
{
    int left_height = 0;
    int right_height = 0;
    // got tree's left height
    if( T->Left != NULL )
    {
        left_height = Tree_Height( T->Left, height ) + 1;
    }
    // go tree's right height
    if( T->Right != NULL )
    {
        right_height = Tree_Height( T->Right, height ) + 1;
    }
    // got the sum of left height and right height
    if( *height < left_height + right_height )
    {
        *height = left_height + right_height;
    }
    // a tree's height is the max{left height, right right}
    return (left_height > right_height ? left_height : right_height );
}

int IS_Balance_Tree( SearchTree T, int *isBalanced )
{
    int left_height = 0;
    int right_height = 0;
    if( T->Left != NULL )
    {
        left_height = IS_Balance_Tree( T->Left, isBalanced ) + 1;
    }
    if( T->Right != NULL )
    {
        right_height = IS_Balance_Tree( T->Right, isBalanced ) + 1;
    }
    if( left_height - right_height > 1 || right_height - left_height > 1 )
    {
        *isBalanced = 0;
        // return 0;
    }

    return (left_height > right_height ? left_height : right_height );
}

int find_Common_Closest_Ancestor( SearchTree T, Position p1, Position p2, Position **ancestor )
{
    int left = 0, right = 0;
    if( T->Left )
    {
        left = find_Common_Closest_Ancestor( T->Left, p1, p2, ancestor );
    }
    if( *ancestor != NULL )
    {
        return 0;
    }
    if( T->Right )
    {
        right = find_Common_Closest_Ancestor( T->Right, p1, p2, ancestor );
    }
    if( *ancestor != NULL )
    {
        return 0;
    }
    int mid = ( T == p1 ) + ( T == p2 );
    int ret = left + right + mid;
    if( ret == 2 )
    {
        //sancestor = &T;   
        *ancestor = &T;
    }

    return ret;
}

void Breadth_First_Traversal( SearchTree T )
{
    if( T == NULL )
        return;
    // using queue to store the node
    deque<const Position> dq;

    while( true )
    {
        if( T->Left != NULL )
        {
            dq.push_back( T->Left );
        }
        if( T->Right != NULL )
        {
            dq.push_back( T->Right );
        }
        cout << "data is : " << T->Element << " " ;
        if( dq.empty() )
        {
            break;
        }

        T = dq.front( );
        dq.pop_front( );
    }
}

void Print_Tree_By_Level( SearchTree T )
{

    if( T == NULL )
        return;
    // using queue to store the node
    deque<const Position> dq;

    Position end = T;

    while( true )
    {
        if( T->Left != NULL )
        {
            dq.push_back( T->Left );
        }
        if( T->Right != NULL )
        {
            dq.push_back( T->Right );
        }
        cout << "data is : " << T->Element ;
        if( T != end )
        {
            cout << " " ;
        }
        else
        {
            if( dq.empty() )
            {
                break;
            }
            cout << "\n" ;
            end = dq.back( );
        }
        T = dq.front( );
        dq.pop_front( );
    }
}

void Print_Tree_For_Certain_Level( SearchTree T, int Level )
{

    if( T == NULL || Level < 0 )
        return;
    // using queue to store the node
    deque<const Position> dq;

    Position end = T;

    int lev = 0;

    while( true )
    {
        if( T->Left != NULL )
        {
            dq.push_back( T->Left );
        }
        if( T->Right != NULL )
        {
            dq.push_back( T->Right );
        }
        if( Level == lev )
        {
            cout << "data is : " << T->Element ;
        }
        if( T != end )
        {
            cout << " " ;
        }
        else
        {
            if( dq.empty() )
            {
                break;
            }
            lev++;
            cout << "\n" ;
            end = dq.back( );
        }
        T = dq.front( );
        dq.pop_front( );
    }

    if( Level > lev )
    {
        cout<< " level too big..." << endl;
    }

}

void Find_Sum_Path( SearchTree T, int *tmp )
{
    *tmp += T->Element;

    if( *tmp > 16 )
    {
        cout << "sum is too small..." << endl;
        return;
    }
    else if( *tmp == 16 )
    {
        cout << "find..." << endl;
    }
    else
    {
        if( T->Left )
        {
            Find_Sum_Path( T->Left, tmp );
        }
        if( T->Right )
        {
            Find_Sum_Path( T->Right, tmp );
        }
    }
}

void Node_Path( SearchTree T, const int value, int sum, deque<int>& dq )
{
    if( T == NULL )
    {
        return;
    }
    sum += T->Element;
    dq.push_back( T->Element );
    // reach leaf( node has no children at all ) ?
    if( T->Left == NULL && T->Right == NULL )
    {
        // when reach leaf still can't find the path then exit
        if( sum != value )
        {
            cout << endl;
            cout << "no path find..." << endl;
            return;
        }
        // otherwise output whole path, which is stored in queue
        copy( dq.begin( ), dq.end( ), ostream_iterator<int>( cout, " " ) );
    }
    // push the data into queue
    if( T->Left )
    {
        Node_Path( T->Left, value, sum, dq );
    }
    if( T->Right )
    {
        Node_Path( T->Right, value, sum, dq );
    }
    dq.pop_back( );
}

void Print_Node_Path(const SearchTree T, int value)

{

    if (T == NULL) return;

    deque<int> dq;

    Node_Path(T, value, 0, dq);

}

BSTreeTest.cpp

#include "BSTree.h"
#include <stdio.h>

int main()
{
    SearchTree T;
    Position P;
    int i;
    int j = 0;

    int height = 0;

    int isBalanced = 1;

    DoubleLink dl;

    T = MakeEmpty( NULL );

    dl = MakeEmpty( NULL );

    for( i = 0; i < 50; i++, j = ( j + 7 ) % 50 )
    {
        T = Insert( j, T );
    }
    //printf( "root : %d\n", T->Element );

    printf( "root : %d\n", Retrieve( T ) );

    Print_InOrder( T );

    //printf( "pre order : \n" );

    //Print_PreOrder( T );

    for( i = 0; i < 50; i++ )
    {
        if( ( P = Find(i, T ) ) == NULL || Retrieve( P ) != i )
        {
            printf( "Error at %d\n", i );
        }
    }

    for( i = 0; i < 50; i += 2 )
    {
        T = Delete(i, T );
    }
    for( i = 1; i < 50; i += 2 )
    {
        if( ( P = Find(i, T ) ) == NULL || Retrieve( P ) != i )
        {
            printf( "Error at %d\n", i );
        }
    }

    for( i = 0; i < 50; i += 2 )
    {
        if( ( P = Find(i, T ) ) == NULL || Retrieve( P ) != i )
        {
            printf( "Error at %d\n", i );
        }
    }

    printf("after deletion\n");
    Print_InOrder( T );

    printf( "Min is %d, Max is %d\n", Retrieve( FindMin( T ) ), Retrieve( FindMax( T ) ) );

    printf( "convert tree to double link list ...\n" );

/*    DoubleLink dl1 = convertBST2DLink( T, InitDoubleLink( dl ) );

    printf( "<---\n" );

    traverseDL2( dl1 );*/

    int a = Tree_Height( T, &height );

    printf( "maximum height : %d\n", height );

    int b = IS_Balance_Tree( T, &isBalanced );
    if( isBalanced == 1 )
    {
        printf( "balanced\n" );
    }
    else
    {
        printf( "no balance\n" );
    }
    //Position *p2 = MakeEmpty( NULL );

    Position *p2 = NULL;

    find_Common_Closest_Ancestor( T, Find( 23, T ), Find( 33, T ), &p2 );

    printf( "common ancestor : %d\n", Retrieve( *p2 ) );

    //Breadth_First_Traversal( T );

    Print_Tree_By_Level( T );

    Print_Tree_For_Certain_Level( T, 100 );

    int ab = 0;
    int *tmp = &ab;

    //Find_Sum_Path( T, tmp );

    Print_Node_Path( T, 55 );

    return 0;
}

Advertisements
This entry was posted in interview and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s