binary_search_tree.cpp File Reference

A simple tree implementation using structured nodes. More...

#include <iostream>

Include dependency graph for binary_search_tree.cpp:

Classes
class	node< Kind >
class	Queue

Functions
void	enqueue (node *n)
node *	dequeue ()
void	Insert (node *n, int x)
int	findMaxInLeftST (node *n)
void	Remove (node *p, node *n, int x)
void	BFT (node *n)
void	Pre (node *n)
void	In (node *n)
void	Post (node *n)
int	main ()

Variables
Queue	queue

Detailed Description

A simple tree implementation using structured nodes.

Todo:

update code to use C++ STL library features and OO structure

Warning

This program is a poor implementation - C style - and does not utilize any of the C++ STL features.

Function Documentation

BFT()

void BFT

(

node *

n

)

                  {
    if (n != NULL) {
        std::cout << n->val << "  ";
        enqueue(n->left);
        enqueue(n->right);
        BFT(dequeue());
    }
}

dequeue()

node * dequeue

(

)

{ return (queue.t[queue.front++]); }

enqueue()

void enqueue

(

node *

n

)

{ queue.t[queue.rear++] = n; }

findMaxInLeftST()

int findMaxInLeftST

(

node *

n

)

                             {
    while (n->right != NULL) {
        n = n->right;
    }
    return n->val;
}

In()

void In

(

node *

n

)

                 {
    if (n != NULL) {
        In(n->left);
        std::cout << n->val << "  ";
        In(n->right);
    }
}

Insert()

void Insert	(	node *	n,
		int	x
	)

                            {
    if (x < n->val) {
        if (n->left == NULL) {
            node *temp = new node;
            temp->val = x;
            temp->left = NULL;
            temp->right = NULL;
            n->left = temp;
        } else {
            Insert(n->left, x);
        }
    } else {
        if (n->right == NULL) {
            node *temp = new node;
            temp->val = x;
            temp->left = NULL;
            temp->right = NULL;
            n->right = temp;
        } else {
            Insert(n->right, x);
        }
    }
}

main()

int main

(

void

)

           {
    queue.front = 0;
    queue.rear = 0;
    int value;
    int ch;
    node *root = new node;
    std::cout << "\nEnter the value of root node :";
    std::cin >> value;
    root->val = value;
    root->left = NULL;
    root->right = NULL;
    do {
        std::cout << "\n1. Insert"
                  << "\n2. Delete"
                  << "\n3. Breadth First"
                  << "\n4. Preorder Depth First"
                  << "\n5. Inorder Depth First"
                  << "\n6. Postorder Depth First";
 
        std::cout << "\nEnter Your Choice : ";
        std::cin >> ch;
        int x;
        switch (ch) {
        case 1:
            std::cout << "\nEnter the value to be Inserted : ";
            std::cin >> x;
            Insert(root, x);
            break;
        case 2:
            std::cout << "\nEnter the value to be Deleted : ";
            std::cin >> x;
            Remove(root, root, x);
            break;
        case 3:
            BFT(root);
            break;
        case 4:
            Pre(root);
            break;
        case 5:
            In(root);
            break;
        case 6:
            Post(root);
            break;
        }
    } while (ch != 0);
 
    return 0;
}

Post()

void Post

(

node *

n

)

                   {
    if (n != NULL) {
        Post(n->left);
        Post(n->right);
        std::cout << n->val << "  ";
    }
}

Pre()

void Pre

(

node *

n

)

                  {
    if (n != NULL) {
        std::cout << n->val << "  ";
        Pre(n->left);
        Pre(n->right);
    }
}

Remove()

void Remove	(	node *	p,
		node *	n,
		int	x
	)

                                     {
    if (n->val == x) {
        if (n->right == NULL && n->left == NULL) {
            if (x < p->val) {
                p->right = NULL;
            } else {
                p->left = NULL;
            }
        } else if (n->right == NULL) {
            if (x < p->val) {
                p->right = n->left;
            } else {
                p->left = n->left;
            }
        } else if (n->left == NULL) {
            if (x < p->val) {
                p->right = n->right;
            } else {
                p->left = n->right;
            }
        } else {
            int y = findMaxInLeftST(n->left);
            n->val = y;
            Remove(n, n->right, y);
        }
    } else if (x < n->val) {
        Remove(n, n->left, x);
    } else {
        Remove(n, n->right, x);
    }
}