Visual C++ - Binary Search Tree
The basic structure, insertion, printing inorder and postorder of a binary search tree is exaplined with complete C++ source code.
Source Code
#include "stdafx.h"
#include "windows.h"
#include <iostream>
typedef struct _BSTNode
{
struct _BSTNode *left;
struct _BSTNode *right;
int data;
} BSTNode;
static BSTNode *root = NULL;
BSTNode* NewNode(int data)
{
BSTNode *pNewNode = new BSTNode();
pNewNode->left = pNewNode->right = NULL;
pNewNode->data = data;
return pNewNode;
}
BSTNode* Insert(BSTNode* node, int data)
{
if(node == NULL)
return NewNode(data);
if(data <= node->data)
{
if(node->left == NULL)
node->left = NewNode(data);
else
node->left = Insert(node->left, data);
}
else
{
if(node->right == NULL)
node->right = NewNode(data);
else
node->right = Insert(node->right, data);
}
return node;
}
BSTNode* Insert2(BSTNode* node, int data)
{
if(node == NULL)
return NewNode(data);
if(data <= node->data)
{
if(node->left == NULL)
{
node->left = NewNode(data);
}
else
if(node->right == NULL)
{
// Rearrange
int temp = node->data;
node->data = node->left->data;
node->right = node->left; // reuse valid left pointer
node->right->data = temp;
node->left = NewNode(data);
}
else
{
node->left = Insert2(node->left, data);
}
}
else
{
if(node->left == NULL) // left must be filled in first
{
// swap the values
int temp = node->data;
node->data = data;
data = temp;
// insert now
node->left = NewNode(data);
}
else
{
if(node->right == NULL)
node->right = NewNode(data);
else
node->right = Insert2(node->right, data);
}
}
return node;
}
void PrintTree(BSTNode *node)
{
if(node == NULL)
return;
PrintTree(node->left);
std::cout << node->data << " ";
PrintTree(node->right);
}
void PrintPostOrder(BSTNode *node)
{
if(node == NULL)
return;
PrintPostOrder(node->left);
PrintPostOrder(node->right);
std::cout << node->data;
}
int MaxDepth(BSTNode *node)
{
if(node == NULL)
return 0;
int ldepth = MaxDepth(node->left);
int rdepth = MaxDepth(node->right);
int max = (ldepth > rdepth) ? ldepth : rdepth;
return (max + 1);
}
int _tmain(int argc, _TCHAR* argv[])
{
///////////////////////////////////
root = Insert(NULL, 30);
int arr1[] = { 40, 50, 60, 70, 80, 90, 25,
35, 45, 55, 65, 75, 85, 95 };
for(int i = 0; i < sizeof(arr1) / sizeof(arr1[0]); i++)
root = Insert2(root, arr1[i]);
PrintTree(root);
std::cout << "\n";
std::cout << "Depth: " << MaxDepth(root);
std::cout << "\n\n";
return 0;
}
Output
If you use the Insert2 Function,
25 30 35 40 45 50 55 60 65 70 75 80 85 90 95
Depth: 5
Press any key to continue . . .
If you use the Insert Function,
25 30 35 40 45 50 55 60 65 70 75 80 85 90 95
Depth: 8
Press any key to continue . . .
|
|