Hey guys. I apologize for my sloppy code. But it got a bit longer than i expected so i stopped bothering about giving meaningful names to Variables later on in the program. Below I have a AVL tree(atleast that's what I intended to write). But my approach to it was a little different and I am not sure if its even correct. If the tree is drawn on paper, it turns out to be perfectly balanced. if you read the code, you will see how i achieved this. But i think i need some major help with balancing the tree if the data to input is not known. the program crashes if I input even number of data. for example right now i am inserting 15 numbers. if i were to insert 18 it will crash because of the way i get my root node and other nodes. Any help would be greatly appreciated. Thanks. My data file has the following numbers which are to be inserted into the tree.(no duplicates are allowed. I have already taken care of that part.)
12 20 18 10 15 19 16 17 13 11 25 10 40 55 30 5 25
code:
<<Mod edit: Posts merged, redundant code removed>>
Sorry I didnt include code tags in original post. Here it is with the tags. Thanks.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
class BinaryTree
{
private:
struct TreeNode
{
int data;
TreeNode *LeftChild;
TreeNode *RightChild;
};TreeNode *root;
public:
BinaryTree()
{
root = NULL;
}
bool Empty()const {return root == NULL;}
void insert(int);
void inOrder(TreeNode *DataToPrint_InOrder);
int Print_inOrder();
void preOrder(TreeNode *DataToPrint_preOrder);
int Print_preOrder();
int EleminatingDuplicateValues(int [],int,int []);
int DuplicateArrayRecorder(int [], int [],int);
int Checking(int [],int [],int,int [],int);
void DeleteNode(int);
void Balance(int,int[],int[],int[],int[],int[],int[],int);
void insertCallFunction(int,int[]);
};
void BinaryTree::insert(int FileData)
{
TreeNode *temp = new TreeNode;
TreeNode *parent;
temp -> data = FileData;
temp -> LeftChild = NULL;
temp -> RightChild = NULL;
parent = NULL;
if(Empty())
root = temp;
else
{
TreeNode *current;
current = root;
while(current)
{
parent = current;
if(temp->data > current->data)
{
current = current -> RightChild;
}
else
{
current = current -> LeftChild;
}
}
if(temp->data < parent->data)
parent -> LeftChild = temp;
else
parent ->RightChild = temp;
}
}
int BinaryTree:rint_inOrder()
{
inOrder(root);
}
void BinaryTree::inOrder(TreeNode *DataToPrint_InOrder)
{
if(DataToPrint_InOrder != NULL)
{
if(DataToPrint_InOrder -> LeftChild)
inOrder(DataToPrint_InOrder->LeftChild);
cout<< DataToPrint_InOrder->data <<endl;
if(DataToPrint_InOrder -> RightChild)
inOrder(DataToPrint_InOrder->RightChild);
}
else return;
}
int BinaryTree:rint_preOrder()
{
preOrder(root);
}
void BinaryTree::preOrder(TreeNode *DataToPrint_preOrder)
{
if(DataToPrint_preOrder !=NULL)
{
cout<<DataToPrint_preOrder->data<<endl;
if(DataToPrint_preOrder ->LeftChild)
preOrder(DataToPrint_preOrder ->LeftChild);
if(DataToPrint_preOrder ->RightChild)
preOrder(DataToPrint_preOrder ->RightChild);
}
else return;
}
int BinaryTree:uplicateArrayRecorder(int OriginalArray[], int RecorderArray[],int size)
{
int x;
int y=0;
int incrementor = 0;
for(x = 1; x<size;x++)
{
if(OriginalArray[y] == OriginalArray[x] ) //condition checks 1st and 2nd element of a sorted array...
{
RecorderArray[incrementor] = OriginalArray[y]; //when a match is found, the value is stored in the recorder array
incrementor++;//and the index is incremented
}
y++;
}
cout<<"Number of Duplicate Records: "<<incrementor<<endl;
return incrementor;
}
int BinaryTree::Checking(int a[],int b[], int size,int ProperOrderArray[],int finalSize)
{
int ConstantIndex=0;
int ConstantIndex2=0;
int ConstantIndex3=0;
finalSize = 0;
int i=0;
int FinalSizeIncrementor = 0;
int count = 0;
int SecondIndexArray[50]={0};
for(int x=0; x<size; x++)
{
if(a[x] == b[ConstantIndex])//each value of the original array is being checked with the recorded duplicates.
{
SecondIndexArray[ConstantIndex] = x;//the maching values index number is stored in a array
a[x] = 0;//and the value it self is set to 0
ConstantIndex++;
}
}
for(int f=0;f<size;f++)//doing the same prodecure the 2nd time will gurantee that all the numbers are now set to 0 which had duplicates
{
if(a[f] == b[ConstantIndex2])
{
a[f] = 0;
ConstantIndex2++;
}
}
for(int v=0;v<size;v++)//here the recorded items with duplicates are reinserted into their original index
{
if(v == SecondIndexArray[ConstantIndex3])
{
a[v] = b[ConstantIndex3];
ConstantIndex3++;
}
}
for(int g=0; g<size; g++)//new array with no duplicates
{
if(a[g] != 0)
{
ProperOrderArray[i] = a[g];
i++;
finalSize++;
}
}
return finalSize;
}
void BinaryTree:eleteNode(int a)
{
bool located = false;
if(Empty())
{
cout<<"The tree is empty"<<endl;
return;
}
TreeNode *current;
TreeNode *parent;
current = root;
while(current != NULL)
{
if(current ->data == a)
{
located = true;
break;
}
else
{
parent = current;
if(a>current->data)
current = current->RightChild;
else
current = current -> LeftChild;
}
}
if(!located)
{
cout<<"could not locate integer: "<<a<<endl;
return;
}
if((current->LeftChild == NULL && current->RightChild !=NULL) || (current->LeftChild !=NULL && current ->RightChild == NULL))
{
if(current->LeftChild == NULL && current->RightChild !=NULL)
{
if(parent ->LeftChild == current)
{
parent->LeftChild = current->RightChild;
cout<<"deleting Leaf: "<<a<<endl;
delete current;
}
else
{
parent ->RightChild = current->RightChild;
cout<<"deleting leaf: "<<a<<endl;
delete current;
}
}
else
{
if(parent->LeftChild == current)
{
parent->LeftChild = current->LeftChild;
cout<<"deleting : "<<a<<endl;
delete current;
}
else
{
parent->RightChild = current->LeftChild;
cout<<"deleting : "<<a<<endl;
delete current;
}
}
return;
}
if(current ->LeftChild == NULL && current ->RightChild == NULL)
{
if(parent -> LeftChild == current)
parent-> LeftChild = NULL;
else
parent-> RightChild = NULL;
cout<<"deleting Leaf: "<<a<<endl;
delete current;
return;
}
if(current -> LeftChild != NULL && current->RightChild !=NULL)
{
TreeNode *checker;
checker = current -> RightChild;
if((checker->LeftChild == NULL) && (checker->RightChild == NULL))
{
//cout<<"current before setting equal to checker: "<<current<<endl;
//cout<<"checker: "<<checker<<endl;
current->data = checker->data;
//cout<<"current after setting equal to checker: "<<current<<endl;
cout<<"deleting Node->: "<<a<<endl;
delete checker;
current -> RightChild = NULL;
}
else
{
if((current->RightChild)->LeftChild !=NULL)
{
TreeNode *current1;
TreeNode *current2;
current2 = current->RightChild;
current1 = (current->RightChild)->LeftChild;
while(current1->LeftChild !=NULL)
{
current2 = current1;
current1 = current1->LeftChild;
}
//cout<<"CurrentData: "<<current->data<<endl;
//cout<<"CurrentData 1: "<<current1->data<<endl;
current->data = current1->data;
cout<<"deleting Node->: "<<a<<endl;
//current1->data = NULL;
delete current1;
//cout<<"CurrentData1: "<<current1->data<<endl;
(current->RightChild)->LeftChild = NULL;
}
else
{
TreeNode *temp;
temp = current->RightChild;
current->data = temp->data;
current -> RightChild = temp->RightChild;
delete temp;
}
}
return;
}
}
//this method is not required anymore
int BinaryTree::EleminatingDuplicateValues(int a[],int size,int final[])
{
int i, j;
j = 0;
for (i = 1; i < size; i++)
{
if (a[i] != a[j])
{
j++;
a[j] = a[i];
}
}
size = (j + 1);
for(i = 0; i < size; i++)
{
final[i] = a[i];
}
return(j + 1);
}
void BinaryTree::Balance(int loopsize,int NodeRecorder[],int firstArray[],int secondArray[],int thirdArray[],int FourthArray[],int SortedOrderArray[],int modVal)
{
int OriginalLoopSize = 15;
int BackWardCounterChecker = 0;
if(modVal != 1)
{
if(modVal != 1)
{
loopsize = loopsize-1;
}
}
int NodeRecorderIndex = 0;
/*finding index number for middle most node of the entire list*/
int BackwardCounter = 0;
int arrayLength = loopsize-1;
while(arrayLength != BackwardCounter )
{
arrayLength = arrayLength -1;
BackwardCounter = BackwardCounter +1;
}
//cout<<"Root Index: "<<BackwardCounter<<endl;
NodeRecorder[NodeRecorderIndex] = BackwardCounter;
NodeRecorderIndex++;
/*-----------------------------------------------------------*/
/*finding index number for middle most node of the left small list*/
int arrayLength2 = BackwardCounter -1;
int BackwardCounter2 = 0;
while(arrayLength2 != BackwardCounter2)
{
arrayLength2 = arrayLength2 -1;
BackwardCounter2 = BackwardCounter2 + 1;
}
//cout<<"Node Index: "<<BackwardCounter2<<endl;
NodeRecorder[NodeRecorderIndex] = BackwardCounter2;
NodeRecorderIndex++;
/*-------------------------------------------------------------*/
/*finding index number for middle node of the left small list which is on the left of the middle most node*/
int arrayLength3 = BackwardCounter2 -1;
int BackwardCounter3 = 0;
while(arrayLength3 != BackwardCounter3)
{
arrayLength3 = arrayLength3 -1;
BackwardCounter3 = BackwardCounter3 + 1;
}
//cout<<"Node Index: "<<BackwardCounter3<<endl;
NodeRecorder[NodeRecorderIndex] = BackwardCounter3;
NodeRecorderIndex++;
/*-------------------------------------------------------------*/
/*finding index number for middle node of the left small list which is on the right of the middle most node*/
int arrayLength4 = BackwardCounter -1;
int BackwardCounter4 = BackwardCounter2 + 1;
while(arrayLength4 != BackwardCounter4)
{
arrayLength4 = arrayLength4 -1;
BackwardCounter4 = BackwardCounter4 + 1;
}
//cout<<"Node Index: "<<BackwardCounter4<<endl;
NodeRecorder[NodeRecorderIndex] = BackwardCounter4;
NodeRecorderIndex++;
/*-------------------------------------------------------------*/
/*finding index number for middle most node of the Right small list*/
int arrayLength5 = loopsize - 1;
int BackwardCounter5 = BackwardCounter + 1;
while(arrayLength5 != BackwardCounter5)
{
arrayLength5 = arrayLength5 -1;
BackwardCounter5 = BackwardCounter5 + 1;
}
//cout<<"Node Index: "<<BackwardCounter5<<endl;
NodeRecorder[NodeRecorderIndex] = BackwardCounter5;
NodeRecorderIndex++;
/*-------------------------------------------------------------*/
/*finding index number for middle node of the right small list which is on the left of the middle most node*/
int arrayLength6 = BackwardCounter5 -1;
int BackwardCounter6 = BackwardCounter + 1;
while(arrayLength6 != BackwardCounter6)
{
arrayLength6 = arrayLength6 -1;
BackwardCounter6 = BackwardCounter6 + 1;
}
//cout<<"Node Index: "<<BackwardCounter6<<endl;
NodeRecorder[NodeRecorderIndex] = BackwardCounter6;
NodeRecorderIndex++;
/*-------------------------------------------------------------*/
/*finding index number for middle node of the right small list which is on the right of the middle most node*/
int arrayLength7 = loopsize -1;
int BackwardCounter7 = arrayLength5 + 1;
while(arrayLength7 != BackwardCounter7)
{
arrayLength7 = arrayLength7 -1;
BackwardCounter7 = BackwardCounter7 + 1;
}
//cout<<"Node Index: "<<BackwardCounter7<<endl;
NodeRecorder[NodeRecorderIndex] = BackwardCounter7;
NodeRecorderIndex++;
/*-------------------------------------------------------------*/
int constantIndex = 0;
for(int xc = 0; xc < loopsize ; xc++)
{
if(xc == NodeRecorder[constantIndex])
{
firstArray[constantIndex] = SortedOrderArray[xc];
constantIndex++;
xc = 0;
}
}
for(int xv=0;xv<loopsize;xv++)
{
secondArray[xv] = firstArray[xv];
}
sort(firstArray,firstArray+constantIndex);
int constIndex = 0;
for(int xb=0;xb<loopsize;xb++)
{
if(SortedOrderArray[xb] == firstArray[constIndex])
{
SortedOrderArray[xb] = 0;
constIndex++;
}
}
int constIndex2 = 0;
for(int test = 0; test<loopsize;test++)
{
if(SortedOrderArray[test] != 0)
{
thirdArray[constIndex2] = SortedOrderArray[test];
constIndex2++;
}
}
int constIndex3 = 0;
for(int Finaltest = 0; Finaltest<loopsize;Finaltest++)
{
if(secondArray[Finaltest] == 0)
{
secondArray[Finaltest] = thirdArray[constIndex3] ;
constIndex3++;
}
}
for(int y=0;y<loopsize;y++)
{
insert(secondArray[y]);
}
}
void BinaryTree::insertCallFunction(int loopsize,int secondArray[])
{
for(int y=0;y<loopsize;y++)
{
insert(secondArray[y]);
}
}
int main()
{
BinaryTree var;
int FileData;
int StorageArraySize=0;
int FinalArraySize=0;
int StorageArray[30]={0};
int FinalArray[30]={0};
int ArrayIndexes[30];
int i=0;
int finalData;
int deletedItems[30] = {0};
int temp[30];
int orderArray[30]={0};
int loopsize=0;
ifstream MyDataChecker("p6data.txt");
while(MyDataChecker >> FileData)
{
StorageArray[i] = FileData;
i++;
}
MyDataChecker.close();
temp[i];
for(int k=0; k < i; k++)
{
temp[k] = StorageArray[k];
}
StorageArraySize = i;
StorageArray[StorageArraySize];
sort(temp,temp+i);
deletedItems[i];
int m=0;
var.DuplicateArrayRecorder(temp,deletedItems,StorageArraySize);
int negator = 0;
for(int check =0; check < i; check++)
{
if(deletedItems[check] != 0)
{
cout<<"Duplicate Items: "<<deletedItems[check]<<endl;
negator++;
}
}
orderArray[i];
var.Checking(StorageArray,deletedItems,StorageArraySize,orderArray,loopsize);
cout<<"---Input Data---"<<endl;
for(int InputData=0; InputData < StorageArraySize-negator;InputData++)
{
cout<<orderArray[InputData]<<endl;
}
int SortedOrderArray[50]={0};
int NodeRecorder[20] = {0};
int NodeRecorderIndex = 0;
int z=0;
for(int r=0; r<i;r++ )
{
if(orderArray[r] != 0)
{
SortedOrderArray[z]=orderArray[r];
z++;
loopsize++;
}
}
sort(SortedOrderArray,SortedOrderArray+loopsize);
int firstArray[20]={0};
int secondArray[20]={0};
int thirdArray[20]={0};
int FourthArray[20]={0};
int modVal = loopsize%2;
var.Balance(loopsize,NodeRecorder,firstArray,secondArray,thirdArray,FourthArray,SortedOrderArray,modVal);
cout<<"--IN-ORDER TRAVERSAL--"<<endl;
cout<<endl;
var.Print_inOrder();
cout<<"--PRE-ORDER TRAVERSAL--"<<endl;
var.Print_preOrder();
cout<<endl;
var.DeleteNode(18);
var.DeleteNode(16);
var.DeleteNode(25);
var.DeleteNode(35);
cout<<"--REPRINTING IN-ORDER--"<<endl;
var.Print_inOrder();
cout<<endl;
var.insert(25);
cout<<"--REPRINTING IN-ORDER WITH 25 INSERTED--"<<endl;
var.Print_inOrder();
return 0;
}
