Code:
#include iostream
#include cstdlib
#include cmath
using namespace std;
/*
* Class SGTNode
*/
class SGTNode
{
public:
SGTNode *right, *left, *parent;
int value;
SGTNode()
{
value = 0;
right = NULL;
left = NULL;
parent = NULL;
}
SGTNode(int val)
{
value = val;
right = NULL;
left = NULL;
parent = NULL;
}
};
/*
* Class ScapeGoatTree
*/
class ScapeGoatTree
{
private:
SGTNode *root;
int n, q;
public:
ScapeGoatTree()
{
root = NULL;
n = 0;
}
/* Function to check if tree is empty */
bool isEmpty()
{
return root == NULL;
}
/* Function to clear tree */
void makeEmpty()
{
root = NULL;
n = 0;
}
/* Function to count number of nodes recursively */
int size(SGTNode *r)
{
if (r == NULL)
return 0;
else
{
int l = 1;
l += size(r->left);
l += size(r->right);
return l;
}
}
/* Functions to search for an element */
bool search(int val)
{
return search(root, val);
}
/* Function to search for an element recursively */
bool search(SGTNode *r, int val)
{
bool found = false;
while ((r != NULL) && !found)
{
int rval = r->value;
if (val < rval)
r = r->left;
else if (val > rval)
r = r->right;
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
/* Function to return current size of tree */
int size()
{
return n;
}
/* Function for inorder traversal */
void inorder()
{
inorder(root);
}
void inorder(SGTNode *r)
{
if (r != NULL)
{
inorder(r->left);
cout<
inorder(r->right);
}
else
return;
}
/* Function for preorder traversal */
void preorder()
{
preorder(root);
}
void preorder(SGTNode *r)
{
if (r != NULL)
{
cout<
preorder(r->left);
preorder(r->right);
}
else
return;
}
/* Function for postorder traversal */
void postorder()
{
postorder(root);
}
void postorder(SGTNode *r)
{
if (r != NULL)
{
postorder(r->left);
postorder(r->right);
cout<
}
else
return;
}
static int const log32(int q)
{
double const log23 = 2.4663034623764317;
return (int)ceil(log23 * log(q));
}
/* Function to insert an element */
bool add(int x)
{
/* first do basic insertion keeping track of depth */
SGTNode *u = new SGTNode(x);
int d = addWithDepth(u);
if (d > log32(q))
{
/* depth exceeded, find scapegoat */
SGTNode *w = u->parent;
while (3 * size(w) <= 2 * size(w->parent))
w = w->parent;
rebuild(w->parent);
}
return d >= 0;
}
/* Function to rebuild tree from node u */
void rebuild(SGTNode *u)
{
int ns = size(u);
SGTNode *p = u->parent;
SGTNode **a = new SGTNode* [ns];
packIntoArray(u, a, 0);
if (p == NULL)
{
root = buildBalanced(a, 0, ns);
root->parent = NULL;
}
else if (p->right == u)
{
p->right = buildBalanced(a, 0, ns);
p->right->parent = p;
}
else
{
p->left = buildBalanced(a, 0, ns);
p->left->parent = p;
}
}
/* Function to packIntoArray */
int packIntoArray(SGTNode *u, SGTNode *a[], int i)
{
if (u == NULL)
{
return i;
}
i = packIntoArray(u->left, a, i);
a[i++] = u;
return packIntoArray(u->right, a, i);
}
/* Function to build balanced nodes */
SGTNode *buildBalanced(SGTNode **a, int i, int ns)
{
if (ns == 0)
return NULL;
int m = ns / 2;
a[i + m]->left = buildBalanced(a, i, m);
if (a[i + m]->left != NULL)
a[i + m]->left->parent = a[i + m];
a[i + m]->right = buildBalanced(a, i + m + 1, ns - m - 1);\
if (a[i + m]->right != NULL)
a[i + m]->right->parent = a[i + m];
return a[i + m];
}
/* Function add with depth */
int addWithDepth(SGTNode *u)
{
SGTNode *w = root;
if (w == NULL)
{
root = u;
n++;
q++;
return 0;
}
bool done = false;
int d = 0;
do
{
if (u->value < w->value)
{
if (w->left == NULL)
{
w->left = u;
u->parent = w;
done = true;
}
else
{
w = w->left;
}
}
else if (u->value > w->value)
{
if (w->right == NULL)
{
w->right = u;
u->parent = w;
done = true;
}
else
{
w = w->right;
}
}
else
return -1;
d++;
}
while (!done);
n++;
q++;
return d;
}
};
int main()
{
ScapeGoatTree sgt;
cout<<"ScapeGoat Tree Test"<
char ch;
int val;
/* Perform tree operations */
do
{
cout<<"\nScapeGoat Tree Operations\n";
cout<<"1. Insert "<
cout<<"2. Count nodes"<
cout<<"3. Search"<
cout<<"4. Check empty"<
cout<<"5. Make empty"<
int choice;
cout<<"Enter your Choice: ";
cin>>choice;
switch (choice)
{
case 1 :
cout<<"Enter integer element to insert: ";
cin>>val;
sgt.add(val);
break;
case 2 :
cout<<"Nodes = " <
break;
case 3 :
cout<<"Enter integer element to search: ";
cin>>val;
if (sgt.search(val))
cout<
else
cout<
break;
case 4 :
cout<<"Empty status = ";
if (sgt.isEmpty())
cout<<"Tree is empty"<
else
cout<<"Tree is non - empty"<
break;
case 5 :
cout<<"\nTree cleared\n";
sgt.makeEmpty();
break;
default :
cout<<"Wrong Entry \n ";
break;
}
/* Display tree*/
cout<<"\nPost order : ";
sgt.postorder();
cout<<"\nPre order : ";
sgt.preorder();
cout<<"\nIn order : ";
sgt.inorder();
cout<<"\nDo you want to continue (Type y or n) \n";
cin>>ch;
}
while (ch == 'Y'|| ch == 'y');
return 0;
}
Output:
ScapeGoat Tree Test
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 34
Post order : 34
Pre order : 34
In order : 34
Do you want to continue (Type y or n)
y
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 67
Post order : 67 34
Pre order : 34 67
In order : 34 67
Do you want to continue (Type y or n)
y
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 11
Post order : 11 67 34
Pre order : 34 11 67
In order : 11 34 67
Do you want to continue (Type y or n)
y
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 24
Post order : 24 11 67 34
Pre order : 34 11 24 67
In order : 11 24 34 67
Do you want to continue (Type y or n)
y
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 6
Post order : 6 24 11 67 34
Pre order : 34 11 6 24 67
In order : 6 11 24 34 67
Do you want to continue (Type y or n)
y
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 97
Post order : 6 24 11 97 67 34
Pre order : 34 11 6 24 67 97
In order : 6 11 24 34 67 97
Do you want to continue (Type y or n)
y
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 12
Post order : 6 12 24 11 97 67 34
Pre order : 34 11 6 24 12 67 97
In order : 6 11 12 24 34 67 97
Do you want to continue (Type y or n)
y
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 1
Enter integer element to insert: 57
Post order : 6 12 24 11 57 97 67 34
Pre order : 34 11 6 24 12 67 57 97
In order : 6 11 12 24 34 57 67 97
Do you want to continue (Type y or n)
y
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 2
Nodes = 8
Post order : 6 12 24 11 57 97 67 34
Pre order : 34 11 6 24 12 67 57 97
In order : 6 11 12 24 34 57 67 97
Do you want to continue (Type y or n)
y
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 3
Enter integer element to search: 57
57 found in the tree
Post order : 6 12 24 11 57 97 67 34
Pre order : 34 11 6 24 12 67 57 97
In order : 6 11 12 24 34 57 67 97
Do you want to continue (Type y or n)
y
ScapeGoat Tree Operations
1. Insert
2. Count nodes
3. Search
4. Check empty
5. Make empty
Enter your Choice: 5
Tree cleared
Post order :
Pre order :
In order :
Do you want to continue (Type y or n)
n
------------------
(program exited with code: 1)
Press return to continue
More C++ Programs:
