Hi all,
I'm trying to design a program that implements a binary tree structure, with special nodes that contain an integer data value, and a string indicating their position relative to the tree's root. I'm almost positive I've got this thing figured out, but I can't test it because VS2010 keeps insisting it can't understand my code. I keep getting C3861 errors. I'll post my code here. Bear in mind this will be using 5 different files.
1. Node.h
Code:
#include <iostream>
#include <string>
using namespace std;
#ifndef _Node_h_included_
#define _Node_h_included_
class Node
{
public:
Node(int val=-1, string pa=""){value = val; path = pa;}
void set(int val=-1, string pa=""){value = val; path = pa;}
int getVal() {return value;}
string getPath() {return path;}
void print() {cout<<value<<","<<path<<endl;}
private:
int value;
string path;
};
#endif
2. tNode.h
Code:
#include <iostream>
#include "Node.h"
#include <string>
using namespace std;
#ifndef _tNode_h_included_
#define _tNode_h_included_
struct tNode
{
Node node;
tNode *left;
tNode *right;
};
#endif
3. SumTreeClass.h
Code:
#include <iostream>
#include <string>
#include "Node.h"
#include "tNode.h"
#include <vector>
using namespace std;
#ifndef _SumTreeClass_h
#define _SumTreeClass_h
class SumTreeClass
{
public:
tNode BuildTree(vector <Node> nodes, tNode *head);
void PrintOut(tNode *head);
vector<Node> SortNodes(vector <Node> nodes);
bool DataBalanced(tNode *head);
bool TreeBalanced(tNode *head);
bool Complete(tNode *head);
bool Full(tNode *head);
private:
int sum(tNode *head);
int height(tNode *head);
};
#endif
4. SumTreeClass.cpp
Code:
#include "Node.h"
#include "SumTreeClass.h"
#include "tNode.h"
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
#ifndef _SumTreeClass_cpp_included_
#define _SumTreeClass_cpp_included_
vector<Node> SumTreeClass::SortNodes(vector<Node> nodes)
{
vector<Node> Sorted;
vector<string> targetStrings;
for(int i = 0;i < nodes.size();i++)
targetStrings.push_back(nodes[i].getPath());
sort(targetStrings.begin(), targetStrings.end());
for(int i = 0; i < targetStrings.size(); i++)
for(int k = 0; targetStrings[i] != nodes[k].getPath();k++)
{
if(nodes[k].getPath() == targetStrings[i])
{
Sorted.push_back(nodes[k]);
nodes.erase(nodes.begin() + k);
}
}
return Sorted;
}
tNode SumTreeClass::BuildTree(vector<Node> nodes, tNode *head)
{
if(nodes.empty() == true)
return *head;
else
{
tNode temp;
temp.node = nodes[0];
temp.left = NULL;
temp.right = NULL;
string tempPath = temp.node.getPath();
if(tempPath.empty() == true)
{
head = &temp;
nodes.erase(nodes.begin());
BuildTree(nodes, head);
}
else if(tempPath[0] == 'L')
{
if(head->left != NULL)
BuildTree(nodes, head -> left);
else if (head->left == NULL && tempPath.size() != 1)
{
temp.node.set(-1, "");
head-> left = &temp;
BuildTree(nodes, head -> left);
}
else if (head->left == NULL && tempPath.size() == 1)
{
head -> left = &temp;
nodes.erase(nodes.begin());
tempPath.erase(tempPath.begin());
BuildTree(nodes, head);
}
}
else if(tempPath[0] == 'R')
{
if(head->right != NULL)
BuildTree(nodes, head -> right);
else if (head->right == NULL && tempPath.size() != 1)
{
temp.node.set(-1, "");
head -> right = &temp;
tempPath.erase(tempPath.begin());
BuildTree(nodes, head -> right);
}
else if (head->right == NULL && tempPath.size() == 1)
{
head -> right = &temp;
nodes.erase(nodes.begin());
tempPath.erase(tempPath.begin());
BuildTree(nodes, head);
}
}
}
}
bool SumTreeClass::DataBalanced (tNode *head)
{
int l, r;
l = sum(head -> left);
r = sum(head -> right);
if (l - r <= 1 && l - r >= -1)
return true;
else
return false;
}
bool SumTreeClass::TreeBalanced (tNode *head)
{
int l, r;
l = height(head -> left);
r = height(head -> right);
if (l - r <= 1 && l - r >= -1)
return true;
else
return false;
}
bool SumTreeClass::Complete(tNode *head)
{
if(head == NULL)
return false;
else if (head -> left == NULL && head ->right != NULL)
return false;
else if (head -> left == NULL && head -> right == NULL)
return true;
else if (TreeBalanced(head) == false)
return false;
else
return (Complete(head->left) && Complete(head->right));
}
bool SumTreeClass::Full(tNode *head)
{
if(head == NULL)
return false;
else if((head -> left != NULL && head ->right == NULL) || (head -> left == NULL && head ->right != NULL))
return false;
else if ((head -> left == NULL && head ->right == NULL))
return true;
else
return(Full(head->left) && Full(head->right));
}
void SumTreeClass::PrintOut(tNode *head)
{
static int h = height(head);
if(head == NULL)
cout << "Empty Tree!" << endl;
else
{
for(int i = 0; i < (h - height(head)); i++)
cout << " ";
cout << head -> node.getVal() << endl;
PrintOut(head -> right);
PrintOut(head -> left);
}
if(TreeBalanced(head) == true)
cout << "Balanced ";
else
cout << "Unbalanced ";
if(DataBalanced(head) == true)
cout << "Data Balanced ";
else
cout << "Data Unbalanced ";
if(Complete(head) == true)
cout << "Complete ";
else
cout << "Incomplete ";
if(Full(head) == true)
cout << "Full " << endl;
else
cout << "Not Full " << endl;
}
int SumTreeClass::height(tNode *head)
{
if (head == NULL)
return 0;
else if (head->right == NULL && head->left == NULL)
return 0;
else
return 1 + max(height(head->left), height(head->right));
}
int SumTreeClass::sum(tNode *head)
{
if (head == NULL)
return 0;
else if (head -> left == NULL && head ->right == NULL)
return head -> node.getVal();
else
return sum (head -> left) + sum (head ->right);
}
#endif
5. SumTree.cpp
Code:
#include "SumTreeClass.h"
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include "Node.h"
#include "tNode.h"
using namespace std;
vector<Node> getInput();
int main()
{
vector<Node> treeNodes;
tNode head;
do
{
treeNodes.clear();
treeNodes = getInput();
treeNodes = SortNodes(treeNodes);
head = BuildTree(treeNodes, &head);
PrintOut(*head);
} while(treeNodes.size() > 0);
system("pause");
return 0;
}
vector<Node> getInput()
{
char line[256];
string lineString;
string nodeString;
bool endOfTree = false;
int openPos, closePos, commaPos; // positions of the delimiters
int value;
string path;
Node node;
vector<Node> nodes;
while (!endOfTree)
{
cin.getline(line,256);
lineString = line;
while (!endOfTree && lineString.size() > 0)
{
openPos = lineString.find('(');
closePos = lineString.find(')');
commaPos = lineString.find(',');
if (openPos == string::npos || commaPos == string::npos)
endOfTree = true;
else
{
nodeString = lineString.substr(openPos+1, closePos - openPos -1);
lineString = lineString.substr(closePos+1, lineString.size() - closePos);
commaPos = nodeString.find(',');
//cout<<"Node string is "<<nodeString<<endl;
value =atoi(nodeString.substr(0,commaPos).c_str());
path = nodeString.substr(commaPos+1,nodeString.size()-commaPos+1);
node.set(value, path);
nodes.push_back(node);
//cout<<"value= "<<value<<"\t path= "<<path<<endl;
}
}
}
return nodes;
}
I'm getting the errors in SumTree.cpp. The errors are saying that SortNodes, BuildTree and PrintOut, identifier not found. Am I using them wrong? Or is there some kind of weird linker error? The compiler shows no other errors. Please help!