Binary Search Tree

Peter_APIIT · #1 01-Mar-2008, 02:02

Hello all expert programmer, i truly new to programming, i have a binary search tree.

In C, there is no reference. Therefore, i build another structure to point the root of tree.

My problem is after i build another structure, this is very difficult for me to write a recursion version of searching, insert, delete.

CPP / C++ / C Code:

#ifndef _BST_
#define _BST_
 
struct Tree_Node 
{
    int value;
    struct Tree_Node *leftNode;
    struct Tree_Node *rightNode;
}
 
struct BST
{
    struct Tree_Node *root;
}
 
#endif

CPP / C++ / C Code:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
#include "Binary_Search_Tree.h"
 
 
// -----------------Tree Node Function---------------------------
struct Tree_Node* Tree_Node_Allocate(struct Tree_Node *);
void Tree_Node_Deallocate(struct Tree_Node *);
 
struct Tree_Node* Tree_Node_Initialize(struct Tree_Node *, int *);
 
struct Tree_Node* Searching(struct BST *, int *);
 
// ------------------BST Tree Function-------------------
struct BST* BST_Allocate(struct BST *);
void BST_Deallocate(struct BST *);
 
struct BST* BST_Insert(struct BST *, struct Tree_Node *);
 
void BST_UserInput(int *);
 
// -----------------------------------------------------
struct Tree_Node* Tree_Node_Allocate(struct Tree_Node *Tree_Node)
{
    Tree_Node = malloc(sizeof(struct Tree_Node));
    assert(Tree_Node != 0);
    Tree_Node->leftNode = NULL;
    Tree_Node->rightNode = NULL;
 
    return Tree_Node; 
}
// ------------------------------------------------------
void Tree_Node_Deallocate(struct Tree_Node *Tree_Node)
{
    if (Tree_Node != NULL)
    {
        free(Tree_Node);
        Tree_Node->value = 0;
        Tree_Node->leftNode = NULL;
        Tree_Node->rightNode = NULL;
    }
    else
    {
        exit(0);
    }
}
// ------------------------------------------------------
struct BST* BST_Allocate(struct BST *BST)
{
    BST = malloc(sizeof(struct BST));
    assert(BST != 0);
    BST->root = NULL;
 
    return BST;
}
// ------------------------------------------------------
void BST_Deallocate(struct BST *BST)
{
    if (BST != NULL)
    {
        free(BST);
        BST->root = NULL;
    }
    else
    {
        exit(0);
    }
}
// -----------------------------------------------------
void BST_UserInPut(int *numberptr)
{
    int value;
    printf("\n\n\t\t\tEnter a value : ");
    scanf("%d", &value);
 
    *numberptr = value;
}
// -------------------------------------------------------
struct Tree_Node* Tree_Node_Initialize(struct Tree_Node *Tree_Node,
                                     int *numberptr)
{
    if (Tree_Node != NULL)
    {
        Tree_Node->value = *numberptr;
    }
    else
    {
        exit(0);
    }
 
    return Tree_Node;
}
// -------------------------------------------------------
struct Tree_Node* Searching(struct BST *BST, int *numberptr)
{
    struct Tree_Node *Tree_Node;
 
    if (BST != NULL)
    {
        Tree_Node = BST->root;
 
        while(Tree_Node != NULL)
        {
        }
    }
    else
    {
        exit(0);
    }
 
    return Tree_Node;
}

I hope you all can clear my doubt.

Thanks for your help. Your help is greatly appreciated by me and others.

Peter_APIIT · #2 09-Mar-2008, 04:03

Please help me.

seprich · #3 10-Mar-2008, 07:05

Hi,

Firstly I am not entirely convinced why would you need to use:

Quote:

Originally Posted by Peter_APIIT

CPP / C++ / C Code:

struct BST
{
    struct Tree_Node *root;
}

in header(.h) instead of just declaring in your source file (.c):

CPP / C++ / C Code:

struct Tree_Node *root;

However if you really need to wrap the root node inside a struct then you can still use recursion easily enough by using following kind of simple method:

CPP / C++ / C Code:


/* recursive search function: */
struct TreeNode* search( struct TreeNode* node, int* value ) {
    // write code...
}

/* The search function:*/
struct Tree_Node* Searching(struct BST *BST, int *numberptr) {
    return search( BST->root, numberptr ); 
}

so you see the "unwrapper" function selects the root node and gives it for the actual recursive function. Final result travels back from the recursion and is given to the caller of "Searching()".

Peter_APIIT · #4 12-Mar-2008, 02:55

The search function is not recursive anymore because it call search function from searching function and not from itself.

The reason i wrap root inside a struct is because previously in this forum, davis told me that node and link list struct need to separate.

For instance, if i want insert a node back the link list , i just need to pass the whole link list and a single node.

If i don't do this, then i need reference in order to pass the whole list.

Is it true ?

seprich · #5 12-Mar-2008, 05:35

Quote:

Originally Posted by Peter_APIIT

The search function is not recursive anymore because it call search function from searching function and not from itself.

The fact that the 'search' function is called also from function 'Searching' does not, in my opinion, make the function 'search' non-recursive.

Let me complete my previous example:

CPP / C++ / C Code:

/* recursive search function: */
struct TreeNode* search( struct TreeNode* node, int* value ) {
    
    struct TreeNode *result = NULL;
    
    if( node != NULL ) {
        if( node->value == *value )  result = node;
        else {
            result = search( node->leftNode, value );    // <<recursion.
            if( result == NULL )
                result = search( node->rightNode, value );  // <<recursion.
        }
    }

    return result;
}

/**
 * @param BST the Beast :)
 * @param numberptr pointer to the searched number
 * @return NULL if the number was not found, otherwise pointer to
 *                    the node which contains the searched number
 */
struct Tree_Node* Searching(struct BST *BST, int *numberptr) {
    return search( BST->root, numberptr ); 
}

^^ so you see the function 'search' calls itself which makes it a recursive function .. the Function 'Searching' exists only to make it possible to give "struct BST * " as a parameter instead of node pointer.

Quote:

Originally Posted by Peter_APIIT

The reason i wrap root inside a struct is because previously in this forum, davis told me that node and link list struct need to separate.

Ok. Certainly node and a link list as a concepts are separate. Implementation then depends.
Sometimes it can be beneficial to use separate structures to hold dynamic containers like trees. However having only one member in a struct seems to me redundant and useless. If you had a second member to put into your struct (or plan to insert new members) then that would perfectly justify the using of separate structure for the tree.

Quote:

Originally Posted by Peter_APIIT

For instance, if i want insert a node back the link list , i just need to pass the whole link list and a single node.

If i don't do this, then i need reference in order to pass the whole list.

Is it true ?

Do you mean pointer by "reference" ?
However from the point of view of functions there is no reason why the handling functions wouldn't be able to operate having plain root node pointer passed to them. Also it is equally simple to make the handling functions such that they take a structure as a parameter.

However the purpose of structure is mainly to collect inter-related parameters together and therefore a structure containing one parameter only is not essentially any better than the parameter itself but only increases complexity.

Peter_APIIT · #6 12-Mar-2008, 20:06

Quote:

Reference Parameters In C
We are bumping into a basic "feature" of the C language that changes to local parameters
are never reflected back in the caller's memory. This is a traditional tricky area of C
programming. We will present the traditional "reference parameter" solution to this
problem, but you may want to consult another C resource for further information. (See
Pointers and Memory (cslibrary.stanford.edu) for a detailed explanation of
reference parameters in C and C++.)

from
cslibrary.stanford.edu

As far as i know, reference in C++ must be initialized.

For instance, i have a laptop :

struct node
{
int value;
struct node *next
};

then how can pass whole list to a insert function.

seprich · #7 12-Mar-2008, 23:20

Quote:

Originally Posted by Peter_APIIT

from
http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

Ok thanks. I would have called it passing pointers to function but seems that one can call them references as well.

Quote:

Originally Posted by Peter_APIIT

As far as i know, reference in C++ must be initialized.

Probably a question to ask in C++ forum.

Quote:

Originally Posted by Peter_APIIT

For instance, i have a laptop :

struct node
{
int value;
struct node *next
};

I don't see what you might mean with word 'laptop' in this particular context supposedly having some relation with struct node.

Quote:

Originally Posted by Peter_APIIT

then how can pass whole list to a insert function.

just one possibility: you can pass the list by passing the address of the root pointer for the insert function. (that way if the root pointer happens to point to NULL then the insert function can manipulate the root pointer.
just quickly written example:

CPP / C++ / C Code:

void insert( struct node **root, struct node *newnode );
  // (probably would be more correct to use term 'append_node' or some such)

int main() {
    struct node *root = NULL;
    struct node *newnode = NULL;

    newnode = create_new_node( 345 ); // malloc:s a new node and puts int
    
    insert( &root, newnode );  // after this root points to newnode
    
    print_list( root );  // function to "printf()" all nodes(==items) in the list

    delete_list( &root );

    return 0;
}

Peter_APIIT · #8 13-Mar-2008, 04:59

That was a wrong typing. Sorry to confuse you.

As far as i know,

insert(struct node *, struct node *); // Function prototype

i call it in main with insert(root, newnode) because root contain address of something it pointed.

If insert(struct node **, struct node *)
We need to call it in main with

insert(&root, newnode);

because we passing address of address of root, where address of root is pointing to the first node and first node has left node and right node. Therefore, we can formed a tree by this only. We direct to firstnode.

Do i correct ?

This is the picture form

root
|
firstNode
/ \
leftchild rightchild

IF we pass (root), we still can get to firstNode, but if we pass (&root), we direct pass firstNode to function definition.

If i declare struct node **root, then i need to pass it as insert(root, newnode);

Therefore, memory allocation will be like this
(*root) = malloc(struct node *);

but in order to simplify memory allocate function i follow your previous post techniques.

Link list, and BST is the basic data structure to test your understand of pointer.

Please correct me if i wrong.

A billion thanks for your help.

You are my idol and my GOD who always lighten up my life and my future become ultra bright. You spirit has keep inside my heart.

Thanks again.

Peter_APIIT · #9 14-Mar-2008, 02:48

This is a good website for beginner who want to learn BST.

Quote:

answers.yahoo.com

Peter_APIIT · #10 15-Mar-2008, 05:35

This is all the code i have did so far. I hope this hel pother to learn BST.

CPP / C++ / C Code:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
#include "BST.h"
// --------------------------------------------------------------
/*
	[url]http://www.brpreiss.com/books/opus4/html/page9.html[/url]
	[url]http://www.ccs.neu.edu/home/vkp/csu213-sp05/Assignments/Assignment5/[/url]
*/
// -----------------Tree Node Function---------------------------
struct Tree_Node* Tree_Node_Allocate(struct Tree_Node *);
void Tree_Node_Deallocate(struct Tree_Node *);
 
struct Tree_Node* Tree_Node_Initialize(struct Tree_Node *, int *);
 
struct Tree_Node* Searching(struct BST *, int *);
struct Tree_Node* RecursiveSearch(struct Tree_Node *, int *, ...);
struct Tree_Node* RecursiveMinSearch(struct Tree_Node *);
struct Tree_Node* RecursiveMaxSearch(struct Tree_Node *);
 
// ------------------BST Tree Function---------------------------
struct BST* BST_Allocate(struct BST *);
void BST_Deallocate(struct BST *);
 
struct BST* BST_Insert(struct BST *, struct Tree_Node *);
struct BST* BST_Remove(struct BST *,int *); 

void FindMin(struct BST *);
void FindMax(struct BST *);
void MinHeight(int *);
void MaxHeight(int *);

void BST_UserInput(int *);
int* QuerySearchValue(int *);
int* numberTreeNodes(int *);
int* removeNode(int *);

// Root->Left->Right
/*
	If left node has children, traversal down until left
	has no children
	Or called Depth-First Traversal
*/
void PreorderDisplay(struct BST *);  
void RecursivePreorderDisplay(struct Tree_Node *);

// Left->Root->Right
void InorderDisplay(struct BST *);
void RecursiveInorderDisplay(struct Tree_Node *);

// Left->Right->Root
void PostorderDisplay(struct BST *);
void RecursivePostorderDisplay(struct Tree_Node *);
/*
	Breadth-first traversal - traversal from level 0 
	until lowest level
*/
void RecursivePostOrder_Deallocate(struct Tree_Node *);
void SearchDisplay(struct Tree_Node *);

// --------------------------------------------------------------
int main(int argc, char *argv[])
{
	struct BST *BST = 0;
	struct Tree_Node *Tree_Node = 0, *resultSearched=0;
	
	int number, search = 0, *numberptr, *searchptr,
		numberNodes, removeSpecificNode, 
		*numberNodesptr, *removeptr;

	numberptr = &number;
	searchptr = &search;
	numberNodesptr = &numberNodes;
	removeptr = &removeSpecificNode;

	BST = BST_Allocate(BST);
	
	Tree_Node = Tree_Node_Allocate(Tree_Node);
	BST_UserInput(numberptr);
	Tree_Node = Tree_Node_Initialize(Tree_Node, numberptr);
	BST = BST_Insert(BST, Tree_Node);

	Tree_Node = Tree_Node_Allocate(Tree_Node);
	BST_UserInput(numberptr);
	Tree_Node = Tree_Node_Initialize(Tree_Node, numberptr);
	BST = BST_Insert(BST, Tree_Node);

	Tree_Node = Tree_Node_Allocate(Tree_Node);
	BST_UserInput(numberptr);
	Tree_Node = Tree_Node_Initialize(Tree_Node, numberptr);
	BST = BST_Insert(BST, Tree_Node);

	Tree_Node = Tree_Node_Allocate(Tree_Node);
	BST_UserInput(numberptr);
	Tree_Node = Tree_Node_Initialize(Tree_Node, numberptr);
	BST = BST_Insert(BST, Tree_Node);

	Tree_Node = Tree_Node_Allocate(Tree_Node);
	BST_UserInput(numberptr);
	Tree_Node = Tree_Node_Initialize(Tree_Node, numberptr);
	BST = BST_Insert(BST, Tree_Node);

	Tree_Node = Tree_Node_Allocate(Tree_Node);
	BST_UserInput(numberptr);
	Tree_Node = Tree_Node_Initialize(Tree_Node, numberptr);
	BST = BST_Insert(BST, Tree_Node);

	Tree_Node = Tree_Node_Allocate(Tree_Node);
	BST_UserInput(numberptr);
	Tree_Node = Tree_Node_Initialize(Tree_Node, numberptr);
	BST = BST_Insert(BST, Tree_Node);

	InorderDisplay(BST);

	PreorderDisplay(BST);

	QuerySearchValue(searchptr);
	resultSearched = Searching(BST, searchptr);
	SearchDisplay(resultSearched);

	FindMin(BST);
	FindMax(BST);
/*
	numberNodesptr = numberTreeNodes(numberNodesptr);
	MinHeight(numberNodesptr);
	MaxHeight(numberNodesptr);
*/
	removeptr = removeNode(removeptr);
	BST = BST_Remove(BST, removeptr);
	PreorderDisplay(BST);

	removeptr = removeNode(removeptr);
	BST = BST_Remove(BST, removeptr);
	PreorderDisplay(BST);


	BST_Deallocate(BST);
	

	return 0;
}
// ------------------------------------------------------------
struct BST* BST_Allocate(struct BST *BST)
{
    BST = malloc(sizeof(struct BST));
    assert(BST != 0);
    BST->root = NULL;
 
    return BST;
}
// -----------------------------------------------------------
void BST_Deallocate(struct BST *BST)
{
	// Memory Leak if i only delete root and not
    // all tree nodes request from heap memory
	/*
		Use postorder traversal method to free Tree Node
		and finally root
	*/

    if (BST != NULL && BST->root != NULL)
    {
		RecursivePostOrder_Deallocate(BST->root);
        free(BST);
        BST->root = NULL;
		BST = BST;
    }
    else
    {
        exit(0);
    }
}
// --------------------------------------------------------
void RecursivePostOrder_Deallocate(struct Tree_Node *Tree_Node)
{
	if (Tree_Node != NULL)
	{
		RecursivePostOrder_Deallocate(Tree_Node->leftNode);
		RecursivePostOrder_Deallocate(Tree_Node->rightNode);
		free(Tree_Node);
	}
}
// ---------------------------------------------------------
struct BST* BST_Insert(struct BST *BST, struct Tree_Node *Tree_Node)
{
	struct Tree_Node *traversal;
	int *numberptr, number;

	numberptr = &number;

	traversal = BST->root;

	*numberptr = Tree_Node->value;

	if (BST->root == NULL)
	{
		BST->root = Tree_Node;
	}
	else
	{
		if (BST->root->leftNode == NULL 
			|| BST->root->rightNode == NULL)
		{
			if (Tree_Node->value < BST->root->value)
			{
				BST->root->leftNode = Tree_Node;
			}
			else
			{
				BST->root->rightNode = Tree_Node;
			}
		}
		else
		{
			traversal = Searching(BST, numberptr);
			if (*numberptr < traversal->value)
			{
				traversal->leftNode = Tree_Node;
			}
			else
			{
				traversal->rightNode = Tree_Node;
			}
		}
	}
	/*
		Top Down construction - Create root first
		Bottom Up construction - Create child first
	*/
	return BST;
}
// -------------------------------------------------------
struct BST* BST_Remove(struct BST *BST,int *removeptr)
{
	struct Tree_Node *parent;
	struct Tree_Node *traversal;    
	struct Tree_Node *RemoveNode;  

	parent = BST->root;
	traversal = BST->root;

	/*
		if no child, just delete
		if one child, point by grandparent
		
		if two children, 
		swap with it with 
		inorder-successor(Left child of right sub Tree)
		// Smallest in right sub tree
		or
		inorder-predecessor(Right child of Left sub Tree)
		// Largest in left sub tree
	*/
	
	// Iteractve Remove Tree Node
	while(traversal != NULL)
	{
		if (*removeptr < traversal->value)
		{
			traversal = traversal->leftNode;

			if (traversal != NULL)
			{
				RemoveNode = traversal;
			}

			if (traversal != NULL)
			{
				if (traversal->value == *removeptr)
				{
					// got 2 children
					if (RemoveNode->leftNode != NULL
						&& RemoveNode->rightNode != NULL)
					{
					}
					// Got 1 child
					else if (RemoveNode->leftNode != NULL
						|| RemoveNode->rightNode != NULL)
					{
						// Swap it with its Left child 
						if (RemoveNode->leftNode != NULL)
						{
							traversal = traversal->leftNode;
							
							if (traversal->value < parent->value)
							{
								parent->leftNode = traversal;
							}
							else
							{
								parent->rightNode = traversal;
							}
							Tree_Node_Deallocate(RemoveNode);
						}

						// Swap it with its Right child 
						if (RemoveNode->rightNode != NULL)
						{
							traversal = traversal->rightNode;

							if (traversal->value < parent->value)
							{
								parent->leftNode = traversal;
							}
							else
							{
								parent->rightNode = traversal;
							}
							Tree_Node_Deallocate(RemoveNode);
						}
					}
					// No child
					else
					{
						Tree_Node_Deallocate(RemoveNode);
						parent->leftNode = NULL;
					}
				}
			}
			if (parent != NULL)
			{
				parent = parent->leftNode;
			}	
		}
		else
		{
			traversal = traversal->rightNode;
			
			if (traversal != NULL)
			{
				RemoveNode = traversal;
			}

			if (traversal != NULL)
			{
				if (traversal->value == *removeptr)
				{
					// got 2 children
					if (RemoveNode->leftNode != NULL
						&& RemoveNode->rightNode != NULL)
					{
					}
					// Got 1 child
					else if (RemoveNode->leftNode != NULL
						|| RemoveNode->rightNode != NULL)
					{
						// Swap it with its Left child 
						if (RemoveNode->leftNode != NULL)
						{
							traversal = traversal->leftNode;
							
							if (traversal->value < parent->value)
							{
								parent->leftNode = traversal;
							}
							else
							{
								parent->rightNode = traversal;
							}
							Tree_Node_Deallocate(RemoveNode);
						}

						// Swap it with its Right child 
						if (RemoveNode->rightNode != NULL)
						{
							traversal = traversal->rightNode;

							if (traversal->value < parent->value)
							{
								parent->leftNode = traversal;
							}
							else
							{
								parent->rightNode = traversal;
							}
							Tree_Node_Deallocate(RemoveNode);
						}
					}
					// No child
					else
					{
						Tree_Node_Deallocate(RemoveNode);
						parent->rightNode = NULL;
					}
				}
			}
			if (parent != NULL)
			{
				parent = parent->rightNode;
			}
		}
	}
	return BST;
}
// -------------------------------------------------------
void FindMin(struct BST *BST)
{
	struct Tree_Node *Tree_Node;

	if (BST != NULL)
	{
		Tree_Node = RecursiveMinSearch(BST->root->leftNode);
	}
	else
	{
		exit(0);
	}
	printf("\n\n\t\tMinimum value of this tree : %d", Tree_Node->value);
}
// -------------------------------------------------------
void FindMax(struct BST *BST)
{
	struct Tree_Node *Tree_Node;

	if (BST->root != NULL)
	{
		Tree_Node = RecursiveMaxSearch(BST->root->rightNode);
	}
	else
	{
		exit(0);
	}
	printf("\n\n\t\tMaximum value of this tree : %d", Tree_Node->value);
}
// -------------------------------------------------------
void MinHeight(int *numberNodesptr)
{
	if (*numberNodesptr != 0)
	{
		// n = 2 ^ h;
	}
	else
	{
		exit(0);
	}
}
// --------------------------------------------------------
void MaxHeight(int *numberNodesptr)
{
	if (*numberNodesptr != 0)
	{
		printf("\n\n\t\t\tMax Height of Tree : %d", *numberNodesptr); 
	}
	else
	{
		exit(0);
	}
}
// -------------------------------------------------------
void PreorderDisplay(struct BST *BST)
{
	// Root->Left->Right
	printf("\n\n\t\t    Preorder Traversal Display\n");

	if (BST->root != NULL)
	{
		RecursivePreorderDisplay(BST->root);
	}
	else
	{
		exit(0);
	}
}
// -------------------------------------------------------
void RecursivePreorderDisplay(struct Tree_Node *Tree_Node)
{
	// Root->Left->Right
	if (Tree_Node != NULL)
	{
		printf("\n\t\t\tValue of node : %d", Tree_Node->value);
		if (Tree_Node->leftNode != NULL)
		{
			RecursivePreorderDisplay(Tree_Node->leftNode);
		}

		if (Tree_Node->rightNode != NULL)
		{
			RecursivePreorderDisplay(Tree_Node->rightNode);
		}
	}
	else
	{
		exit(0);
	}
}

// -------------------------------------------------------
void InorderDisplay(struct BST *BST)
{
	// Left->Root->Right

	printf("\n\n\t\t    Inorder Traversal Display\n");

	if (BST->root != NULL)
	{
		RecursiveInorderDisplay(BST->root);	
	}
	else
	{
		exit(0);
	}
}
// -----------------------------------------------------
void RecursiveInorderDisplay(struct Tree_Node *Tree_Node)
{
	if (Tree_Node != NULL)
	{
		if (Tree_Node->leftNode != NULL)
		{
			RecursiveInorderDisplay(Tree_Node->leftNode);
		}

		printf("\n\t\t\tValue of node : %d", Tree_Node->value);
		
		if (Tree_Node->rightNode != NULL)
		{
			RecursiveInorderDisplay(Tree_Node->rightNode);
		}
	}
	else
	{
		exit(0);
	}
	/*
		1. First call left-node 
		2. After finished calling, return to point where its 
		   calling from which is root 
		   Display root value
        3. Call right node

        After finished calling itself, return to 
		previous stack where its calling from
		
    */
}

// -----------------------------------------------------
void PostorderDisplay(struct BST *BST)
{
	// Left->Right->Root

	printf("\n\n\t\t    Postorder Traversal Display\n");
	if (BST->root != NULL)
	{
		RecursivePostorderDisplay(BST->root);
	}
	else
	{
		exit(0);
	}
}
// -------------------------------------------------------
void RecursivePostorderDisplay(struct Tree_Node *Tree_Node)
{
	if (Tree_Node != NULL)
	{
		if (Tree_Node->leftNode != NULL)
		{
			RecursiveInorderDisplay(Tree_Node->leftNode);
		}

		if (Tree_Node->rightNode != NULL)
		{
			RecursiveInorderDisplay(Tree_Node->rightNode);
		}

		printf("\n\t\t\tValue of node : %d", Tree_Node->value);
	}
	else
	{
		exit(0);
	}
}
// ------------------------------------------------------
void SearchDisplay(struct Tree_Node *Tree_Node)
{
	if (Tree_Node != NULL)
	{
		printf("\n\n\t\t\tResult of searched : %d\n", Tree_Node->value);
	}
	else
	{
		exit(0);
	}
}
// ------------------------------------------------------
struct Tree_Node* Searching(struct BST *BST, int *numberptr)
{
    if (BST != NULL)
    {
		return RecursiveSearch(BST->root, numberptr);
    }
    else
    {
        exit(0);
    }
}
// -----------------------------------------------------
struct Tree_Node* RecursiveSearch(struct Tree_Node *Tree_Node
								  , int *numberptr, ...)
{
	struct Tree_Node* result;

	result = Tree_Node;

	if (Tree_Node != NULL)
	{
		if (Tree_Node->value == *numberptr)
		{
			return Tree_Node;
		}
		else
		{
			if (Tree_Node->leftNode != NULL 
				|| Tree_Node->rightNode != NULL)
			{
				if (*numberptr < Tree_Node->value)
				{
					if (Tree_Node->leftNode != NULL)
					{
						return RecursiveSearch(Tree_Node->leftNode, numberptr);
					}
				}
				else
				{
					if (Tree_Node->rightNode != NULL)
					{
						return RecursiveSearch(Tree_Node->rightNode, numberptr);
					}
				}
			}
		}
	}
	return result;
}
// -----------------------------------------------------
struct Tree_Node* RecursiveMinSearch(struct Tree_Node *Tree_Node)
{
	if (Tree_Node != NULL)
	{
		if (Tree_Node->leftNode != NULL)
		{
			Tree_Node =  RecursiveMinSearch(Tree_Node->leftNode);
		}
	}
	return Tree_Node;
}
// ------------------------------------------------------
struct Tree_Node* RecursiveMaxSearch(struct Tree_Node *Tree_Node)
{
	if (Tree_Node != NULL)
	{
		if (Tree_Node->rightNode != NULL)
		{
			Tree_Node = RecursiveMaxSearch(Tree_Node->rightNode);
		}
	}
	else
	{
		exit(0);
	}
	return Tree_Node;
}
// ------------------------------------------------------
void BST_UserInput(int *numberptr)
{
    int value;

    printf("\n\n\t\t\tEnter a value : ");
    scanf("%d", &value);
 
    *numberptr = value;
}
// ------------------------------------------------------
int* QuerySearchValue(int *numberptr)
{
	int value;

	printf("\n\n\t\t\tEnter a value to search or delete: ");
	scanf("%d", &value);

	*numberptr = value;

	return numberptr;
}
// -----------------------------------------------------
struct Tree_Node* Tree_Node_Allocate(struct Tree_Node *Tree_Node)
{
    Tree_Node = malloc(sizeof(struct Tree_Node));
    assert(Tree_Node != 0);

    Tree_Node->leftNode = NULL;
    Tree_Node->rightNode = NULL;
 
    return Tree_Node; 
}
// ------------------------------------------------------
void Tree_Node_Deallocate(struct Tree_Node *Tree_Node)
{
    if (Tree_Node != NULL)
    {
        free(Tree_Node);
        Tree_Node->leftNode = NULL;
        Tree_Node->rightNode = NULL;
    }
    else
    {
        exit(0);
    }
}
// -------------------------------------------------------
struct Tree_Node* Tree_Node_Initialize(struct Tree_Node *Tree_Node,
                                     int *numberptr)
{
    if (Tree_Node != NULL)
    {
        Tree_Node->value = *numberptr;
		Tree_Node->leftNode = NULL;
		Tree_Node->rightNode = NULL;
    }
    else
    {
        exit(0);
    }
 
    return Tree_Node;
}
// -------------------------------------------------------
int* numberTreeNodes(int *numberNodesptr)
{
	printf("\n\n\t\t\tEnter Number of Nodes : ");
	scanf("%d", &numberNodesptr);

	return numberNodesptr;
}
// -------------------------------------------------------
int* removeNode(int *removeptr)
{
	printf("\n\n\t\t\tEnter a value to remove : ");
	scanf("%d", removeptr);
	/*
		If pointer or array, no need address operator
	*/

	return removeptr;
}
// --------------------------------------------------------

[cpp]
#ifndef _BST_
#define _BST_
 
struct Tree_Node 
{
    int value;
    struct Tree_Node *leftNode;
    struct Tree_Node *rightNode;
};
 
struct BST
{
    struct Tree_Node *root;
};
 
#endif
/*
	Binary Search Tree can be used for efficient searching, 
	arithmetic expression parsing, and 
	data compression

	Fullness - Previous Level * 2 = Current Level is 
			   consider fullness
	Balance - isBalanced() - Find Maximum height
	          of left node and right node
			  if == balanced else unbalaced
			  All node must same height then 
			  considered balanced
	Leftness - 

    Recursion good for keeping track of paths(Fixed Path or a route)
    
*/

[/cpp]

I fyou good in pointer to pointer, then you only need to create one struct else you can follow this approach where teach by seprich.

Thanks.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Deleting a node from binary search tree	earachefl	C++ Forum	3	28-Jun-2006 08:26
can anyone help me with my tree :)	bioeng_mtm	C++ Forum	5	22-Apr-2006 13:50
Binary Search Tree in C++	rpg3	C++ Forum	5	02-Apr-2006 10:53
printing binary search tree	nkhambal	C Programming Language	2	26-Mar-2005 04:01
Search Engine Positioning 101 and 201 "How To" Tips...	000	Search Engine Optimization Forum	0	29-May-2003 11:34

Binary Search Tree

Re: Binary Search Tree

Re: Binary Search Tree

Re: Binary Search Tree

Re: Binary Search Tree

Re: Binary Search Tree

Re: Binary Search Tree

Re: Binary Search Tree

Re: Binary Search Tree

Re: Binary Search Tree