Article 121 - Binary Tree Implementation

This article describes an implementation of the Binary Tree Structure with the binary search property.

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

To program a Binary Tree, we need to understand the interface of a Binary Tree.

Interface

  • New Node
  • Add Node
  • Remove Node

Implementation

Node Structure.

typedef struct Node{
    struct Node * leftChild;
    struct Node * rightChild;
    int content;
} Node;

New Node Function

Allocate a new node and initialize it.

Node * newNode( int content ){
    Node * newNode = (Node *)malloc( sizeof( Node ) );

    if( newNode ){
        newNode->leftChild = 0;
        newNode->rightChild = 0;
        newNode->content = content;
    }

    return newNode;
}

Add Node Function

Adding a node is a simple application of binary search tree traversal until a leaf node is found. At the leaf node, we can add a child node for the new value.

Add Node Function.

int addNode( Node ** tree, int content ){
    Node * childNode;

    if( !tree ){
        return -1;
    }

    if( !*tree ){
        *tree = newNode( content );
        return (*tree) != 0;
    }

    if( content == (*tree)->content ){
        //duplicate entry
        return 0;
    }
    else if( content < (*tree)->content ){
        if( (*tree)->leftChild ){
            //left child exists, recurse
            return addNode( &(*tree)->leftChild, content );
        }
        else{
            //no left child, add node
            (*tree)->leftChild = newNode( content );
            return (*tree)->leftChild != 0;
        }
    }
    else{
        if( (*tree)->rightChild ){
            //right child exists, recurse
            return addNode( &(*tree)->rightChild, content );
        }
        else{
            //no right child, add node
            (*tree)->rightChild = newNode( content );
            return (*tree)->rightChild != 0;
        }
    }
}

Remove Node Function

Removing a node is a simple application of binary search tree traversal until the node is found but a series of complex fixes to update roots up to the root or first node with a single child.

Remove Node Function.

int removeNode( Node ** tree, int content ){
    Node * nodePointer;
    Node * swapRightChild;

    if( !tree ){
        return -1;
    }

    if( !*tree ){
        return 0;
    }

    if( content == (*tree)->content ){
        //found entry, remove it
    
        if( (*tree)->leftChild && (*tree)->rightChild ){
            //have two children
            //move left up 
            //recurse right children of left until null
            //append current (dangling) right child
            nodePointer = *tree;
            swapRightChild = (*tree)->rightChild;
            (*tree) = (*tree)->leftChild;

            free( nodePointer );

            for( nodePointer = (*tree)->rightChild; ; ){
                if( !nodePointer->rightChild ){
                    nodePointer->rightChild = swapRightChild;
                    break;
                }
        
                nodePointer = nodePointer->rightChild;
            }            
        }
        else if( (*tree)->leftChild ){
            //no right, have left, move left up

            nodePointer = *tree;
            (*tree) = (*tree)->leftChild;

            free( nodePointer );
        }
        else if( (*tree)->rightChild ){
            //no left, have right, move right up

            nodePointer = *tree;
            (*tree) = (*tree)->rightChild;

            free( nodePointer );
        }
        else{
            //no children, simple remove
            free( *tree );
            *tree = 0;
        }
        
        return 0;
    }
    else if( content < (*tree)->content ){
        return removeNode( &(*tree)->leftChild, content );
    }
    else{
        return removeNode( &(*tree)->rightChild, content );
    }
}

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.