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
|
/* UROP Project.
Parse.cpp
Edition 14.
*/
#include <iostream>
#include <fstream>
#include <stdlib.h> //we need this for atoi and rand() functions
#include <string>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <cassert> //header used to define assert function
#include <time.h>
using std::cout;
using std::endl;
typedef enum {START, END, LEFT, RIGHT} State;
typedef enum {LEAF, INNER} NodeType;
typedef enum {GREEN, BLUE, NOCOLOR} Color_Type; //GREEN==0 and BLUE==1
//Definition of the Tree and function declerations that belong to this class
class BinaryTree
{
private:
BinaryTree * left;
BinaryTree * right;
BinaryTree * parent;
public:
unsigned nodeNumber;
Color_Type Color;
BinaryTree * root; //declaration of a pointer to the head of the linked root
BinaryTree(BinaryTree * parent = NULL) : left(NULL), right(NULL), parent(parent) {};
bool isRoot() const { return root==NULL; }
BinaryTree * getRoot() { return root;}
void printGraphicalTree(std::ostream& );
void graphicalTree(std::ostream&, BinaryTree * , int );
BinaryTree * insert(State& state, unsigned nodeNumber) {
assert(state == LEFT || state == RIGHT);
BinaryTree * newNode = new BinaryTree(this);
newNode->root = root;
newNode->nodeNumber = nodeNumber;
newNode->Color = NOCOLOR;
if (state == LEFT)
{
left = newNode;
return newNode;
}
if (state == RIGHT)
{
right = newNode;
return newNode;
}
}
int color_specific_node(BinaryTree * root,int random_leafnode, Color_Type Color) //go through the tree and examine if there is a leafnode. if there is give it a color
{
if (root == NULL){
return(0);
}
else {
if ((root->left == NULL) || (root->right == NULL)) return (LEAF);
else return (0);
}
}
bool insert_color(Color_Type Color, NodeType nt, BinaryTree * root) {
int total_nodes= BinaryTree::count_total_nodes(root);
int total_leaf_nodes= BinaryTree::count_total_leafnodes(root);
bool success = false;
do {
if (nt == LEAF)
{
int random_leafnode = rand() % (total_leaf_nodes + 1);
success = color_specific_node(root, random_leafnode, Color);
}
else
{
int random_innernode = total_leaf_nodes + rand() % (total_leaf_nodes-total_nodes); //does not include the root
success = color_specific_node(root, random_innernode, Color);
}
} while(success == false);
return success;
}
//used for error detection and for colouring
static unsigned count_total_nodes(BinaryTree * node)
{
if (node == NULL) return 0;
else return count_total_nodes(node->left) + count_total_nodes(node->right) + 1;
}
static unsigned int count_total_leafnodes(BinaryTree* node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return count_total_leafnodes(node->left) + count_total_leafnodes(node->right);
}
BinaryTree* up()
{
return parent;
}
};
bool parse_file(std::fstream& file, BinaryTree**);
void print_string_from_file(std::string&, std::ostream&);
unsigned count();
int main(int argc, char** argv)
{ srand ( time(NULL) );
std::string fileName = "tree.txt";
std::fstream treeFile (fileName.c_str()); //get input sequence from file
std::cout << "Original String : ";
print_string_from_file (fileName, std::cout); //print on screen the actually sequence as it appears in file
// treeFile.open(args.REQ_ARGS[0]); //not in use
if (!treeFile.is_open())
{
std::cerr << "File not found" << std::endl;
return -1;
}
BinaryTree * root = new BinaryTree(NULL);
root->root = root;
root->nodeNumber = 0;
root->Color = NOCOLOR;
bool is_valid = parse_file(treeFile, &root);
assert(is_valid);
root->printGraphicalTree(std::cout); //shouldn't we call this as BinaryTree::printGraphicalTree? From where does root-> come from?
return 0;
}
|
