1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
|
#include<iostream>
#include<iomanip>
#include "BST1.h"
using namespace std;
binST::binST()
{
root=nullptr;
}
binST::~binST()
{
binST_TreeClear(root);
}
void binST::binST_TreeClear(Node* n)
{
Node *nn;
if(n!=nullptr)
{
nn=n->left;
binST_TreeClear(nn);
nn=n->right;
binST_TreeClear(nn);
delete n;
n=nullptr;
}
}
int binST::binST_Size()
{
return binST_Count(root);
}
int binST::binST_Count(Node *n)
{
if(n==nullptr)
return 0;
else
return binST_Count(n->left) + binST_Count(n->right) + 1;
}
void binST::binST_Insert(int item)
{
// Call Recursive Function
binST_Insert(root, item);
}
void binST::binST_Insert(Node *temp, int item)
{
// If node is null, create a new node with input data
if(temp == nullptr)
{
temp = new Node(item);
}
else
{
// Check to see if data being inserted is < current node->data
if(item < (temp->data))
// recursive call with left child node input node
binST_Insert((temp->left), item);
else
{
// Check to see if data being inserted is > current node->data
if(item > (temp->data))
// recursive call with left child node input node
binST_Insert((temp->right), item);
else
// Ignore Duplicate Values
cout<<item<<"is a duplicate"<<endl;
}
}
}
void binST::binST_Erase(int item)
{
binST_Erase(root, item);
}
void binST::binST_Erase(Node *n, int item)
{
// CASE 1: Root is NULL
if(n==nullptr)
return;
// CASE 2: Root has 1 element
if(n->data == item)
{
delete n;
n=nullptr;
}
/*
// CASE 3: less than Root
if(item<n->data)
binST_Erase((n->left), item);
else if((root->left) =nullptr)
return;
// CASE 4: greater than Root
if(item>root->data)
binST_Erase((n->right), item);
else if((n->right) = nullptr)
return;
*/
}
/*
bool binST::binST_Find(Node *n, int d)
{
if(n==nullptr)
return false;
if(n->data==d)
return true;
else if(n->data>d)
binST_Find(n->left,d);
else
binST_Find(n->right,d);
}
*/
// TRAVERSAL FUNCTIONS
void binST::binST_InOrder()
{
// Call Recursive Function
binST_InOrder(root);
}
// Overloaded InOrder Function to be used recursively
void binST::binST_InOrder(Node *n)
{
if(n!=nullptr)
{
binST_InOrder(n->left); // Recursive Traversal of left subtree
cout<<n->data<<endl; // Process Node
binST_InOrder(n->right); // Recursive Traversal of right subtree
}
}
void binST::binST_PostOrder()
{
binST_PostOrder(root);
}
// Overloaded PostOrder Function to be used recursively
void binST::binST_PostOrder(Node *n)
{
if(n!=nullptr)
{
binST_PostOrder(n->left); // Recursive Traversal of left subtree
binST_PostOrder(n->right); // Recursive Traversal of right subtree
cout<<n->data<<endl; // Process Node
}
}
void binST::binST_PreOrder()
{
binST_PreOrder(root);
}
// Overloaded PreOrder Function to be used recursively
void binST::binST_PreOrder(Node *n)
{
if(n!=nullptr)
{
cout<<n->data<<endl; // Process Node
binST_PreOrder(n->left); // Recursive Traversal of left subtree
binST_PreOrder(n->right); // Recursive Traversal of right subtree
}
}
|