Binary Search Tree

soapbar (6)
Read the first line of code as a key
Ignore it

Read the following as a binary search tree

main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
    Node *tree;
    Node *root;
    char str[100];
    int i = 0;
    int key;
    FILE* fp;
    fp = fopen("/Users/mushu/Desktop/CS130/Assignment3_PS/Assignment3_PS/years.txt", "r");
    if ((fp = fopen("/Users/mushu/Desktop/CS130/Assignment3_PS/Assignment3_PS/years.txt","r")) == NULL)
    {
        printf("Could not open textFile.txt\n");
        exit(1);
    }
    string str2;
    
    /*
    while(fgets(str, 100, fp) != NULL)
    {
        ++i;
        root = tree->add(root, str);
        tree->print(root,2);
        //printf("%3d: %s +---", i, str);
      */


Node 
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
 
class Node
{
public:
    //Node(Entry<T> entry);
    Node *left;
    Node*right;
    void print(Node *node, int indent);
    Node* add (Node *node, char*key);
    string find(int key);
    void preorder(Node *node);
    bool findNode(Node *root, char* key);

    Node* newNode(char *item);
    
    int data;
    char*key;
};


void Node::preorder(Node *node)
{
    if (node == NULL)
    {
        return;
    }
    preorder(node);
    cout << node->left << " ";
    cout << node->right << " ";
}

// Prints will the structure of the tree. One node will be printed per line.
// Preorder tree tarversal.
// Adds the key to the correct position in the BST.

void Node::print(Node*node, int indent)
{
    cout << std::string(2*indent, ' ');
    if (node != NULL)
    {
        cout << "+--- ";
        //cout << node->data << ":" << node->key << endl;
        cout << node->key << endl;
        indent += 1;
        print(node->right, indent);
        print(node->left, indent);
    }
}


Node* Node::newNode(char *item)
{
    Node*temp = new Node;
    temp->key = item;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}


Node* Node::add(Node *node, char* key)
{
    //Node*node;
    //node->left = NULL;
    //node->right = NULL;
    if (node == NULL)
    {
        return newNode(key);
    }
    if(strcmp(key, node->key) < 0)
        node->left = add(node->left, key);
    if(strcmp(key, node->key) > 0)
        node->right = add(node->right, key);
    
    return node;
}

// inserts the node into the key.

// Finds a node with the key and returns its value.

string Node::find(int key)
{
    //return string(key);
    return " ";
}

// mycodeschool Search function;

bool Node::findNode(Node *root, char* key)
{
    /*
    if (root == NULL)
        return "Empty String";
    else if (root->key == key)
    {
        return root->key;
    }
    else if(data <= root->data) return findNode(root->left, data);
    else
        return findNode(root->right, data);
     */
    return true;
}



Errors:
Does not separate the integers from the string.
Does not sort the tree as follow

text file

4
2020,Great Toilet Paper Shortage   
1839,Sutter's Fort founded
1846,Bear Flag Revolt
1947,Sacramento State founded 
1977,Star Wars was born
2017,Star Wars franchise almost destroyed
1964,Buffalo wings invented
1783,United States Constitution enacted
1850,California joins the United States
1848,Gold Rush begins 
1776,American Revolution
1980,Pacman was released
1953,Cheese Whiz was invented (Nacho Era began)
END




+--- 2020: Great Toilet Paper Shortage   
            +--- 1846,Bear Flag Revolt
            +--- 1947,Sacramento State founded 

+--- 1839: Sutter's Fort founded
            +--- 1776,American Revolution


my output

    +--- 4

                +--- 2020,Great Toilet Paper Shortage   

                +--- 1839,Sutter's Fort founded

                +--- 1846,Bear Flag Revolt

                +--- 1947,Sacramento State founded 

                +--- 1977,Star Wars was born

                +--- 2017,Star Wars franchise almost destroyed

                +--- 1964,Buffalo wings invented

                +--- 1783,United States Constitution enacted

                +--- 1850,California joins the United States

                +--- 1848,Gold Rush begins 

                +--- 1776,American Revolution

                +--- 1980,Pacman was released

                +--- 1953,Cheese Whiz was invented (Nacho Era began)

                +--- END
Last edited on
seeplus (6456)
As this is C++, why are you using c file functions and not C++ file stream? Also why not use std::string instead of a c char-array?
seeplus (6456)
As a first refactor, consider:

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
 
#include <iostream>
#include <fstream>
#include <string>

struct Data {
	int key {};
	std::string data;
};

std::istream& operator>>(std::istream& ifs, Data& d) {
	char t {};

	ifs >> d.key >> t;
	return std::getline(ifs, d.data);
}

class Node {
public:
	Node* left {};
	Node* right {};
	Data data;

	Node(const Data& d) : data(d) {}

	void destroy_tree(Node* leaf) {
		if (leaf) {
			destroy_tree(leaf->left);
			destroy_tree(leaf->right);
			delete leaf;
		}
	}

	void print(Node* node, int& indent);
	Node* add(Node* node, const Data& data);
	void preorder(Node* node);
	void inorder(Node* node);
	Node* findNode(Node* root, int key);
	static Node* newNode(const Data& data);
};

void Node::preorder(Node* node) {
	if (node) {
		preorder(node);
		std::cout << node->left << " ";
		std::cout << node->right << " ";
	}
}

void Node::inorder(Node* node) {
	if (node) {
		inorder(node->left);
		std::cout << node->data.key << ": " << node->data.data << '\n';
		inorder(node->right);
	}
}

void Node::print(Node* node, int& indent) {
	std::cout << std::string(2 * indent, ' ');

	if (node) {
		std::cout << "+--- ";
		std::cout << node->data.key << ": " << node->data.data << '\n';
		++indent;
		print(node->right, indent);
		print(node->left, indent);
	}
}

Node* Node::newNode(const Data& d) {
	return new Node (d);
}

Node* Node::add(Node* node, const Data& d) {
	if (!node)
		return newNode(d);

	if (d.key < node->data.key)
		node->left = add(node->left, d);
	else if (d.key > node->data.key)
		node->right = add(node->right, d);

	return node;
}

Node* Node::findNode(Node* root, int key) {
	if (root) {
		if (root->data.key == key)
			return root;

		if (key <= root->data.key)
			return findNode(root->left, key);

		return findNode(root->right, key);
	}

	return nullptr;
}

int main() {
	Node* tree {};

	if (std::ifstream ifs { "years.txt" }) {
		ifs.ignore(1000, '\n');
		for (Data d; ifs >> d; )
			tree = tree->add(tree, d);

		//int indent {};

		//tree->print(tree, indent);
		tree->inorder(tree);
	} else
		return (std::cout << "Cannot open file\n", 1);

	tree->destroy_tree(tree);
}



1776: American Revolution
1783: United States Constitution enacted
1839: Sutter's Fort founded
1846: Bear Flag Revolt
1848: Gold Rush begins
1850: California joins the United States
1947: Sacramento State founded
1953: Cheese Whiz was invented (Nacho Era began)
1964: Buffalo wings invented
1977: Star Wars was born
1980: Pacman was released
2017: Star Wars franchise almost destroyed
2020: Great Toilet Paper Shortage


However this isn't really using Node class in a C++ way. You'd have a class Tree that maintained it's own root pointer etc and the main program wouldn't know anything about it.
seeplus (6456)
As a basic more C++ way (insert, in-order traverse and find), then perhaps consider:

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
 
#include <iostream>
#include <fstream>
#include <string>

struct Data {
	int key {};
	std::string data;
};

std::istream& operator>>(std::istream& ifs, Data& d) {
	char t {};

	ifs >> d.key >> t;
	return std::getline(ifs, d.data);
}

class Tree {
	struct Node {
		Node* left {};
		Node* right {};
		Data data;

		Node(const Data& d) : data(d) {}
	};

	Node* root {};

	void inord(const Node*) const;
	Node* insNode(Node*, const Data&);
	Node* findNode(const Node*, int) const;

public:
	Tree() = default;
	~Tree() {
		destroy_tree(root);
	}

	Tree(const Tree&) = delete;
	Tree& operator=(const Tree&) = delete;

	void destroy_tree(Node*);
	void insert(const Data& data) {
		root = insNode(root, data);
	}

	void inorder() const {
		inord(root);
	}

	Data* find(int key) const;
};

void Tree::inord(const Node* node) const {
	if (node) {
		inord(node->left);
		std::cout << node->data.key << ": " << node->data.data << '\n';
		inord(node->right);
	}
}

Tree::Node* Tree::insNode(Node* node, const Data& d) {
	if (!node)
		node = new Node(d);
	else if (d.key < node->data.key)
		node->left = insNode(node->left, d);
	else if (d.key > node->data.key)
		node->right = insNode(node->right, d);

	return node;
}

Tree::Node* Tree::findNode(const Node* node, int key) const {
	if (node) {
		if (root->data.key == key)
			return root;

		if (key <= root->data.key)
			return findNode(root->left, key);

		return findNode(root->right, key);
	}

	return nullptr;
}

void Tree::destroy_tree(Node* leaf) {
	if (leaf) {
		destroy_tree(leaf->left);
		destroy_tree(leaf->right);
		delete leaf;
	}
}

Data* Tree::find(int key) const {
	if (auto n { findNode(root, key) }; n)
		return &(n->data);

	return nullptr;
}

int main() {
	Tree tree;

	if (std::ifstream ifs { "years.txt" }) {
		ifs.ignore(1000, '\n');
		for (Data d; ifs >> d; )
			tree.insert(d);

		tree.inorder();
	} else
		return (std::cout << "Cannot open file\n", 1);
}

dhayden (5795)
What's the key and what's the data here? The input file appears to have events and the year they occurred. You're sorting them based on the name of the event. Sorting on the date would make a lot more sense. The sample doesn't appear to be sorted by either.

You might want to post the full assignment so we can help with the details.

Here's another take on the code. I added an inorder() method to print the data in order for easier verification. Class Event contains the data from the file. Like seeplus, I separated the Tree from the Node.

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
 
#include <iostream>
#include <string>

using std::string;
using std::cin;
using std::cout;
using std::istream;
using std::ostream;

class Event {
public:
    int year;			// this is the key
    string name;		// name of the event

    // constructor
    Event(int y=0, const string &n = "") :
	year(y), name(n)
    {}

    // Less than operator lets you compare two events with
    // event1 < event2. The tree uses this to establish the order
    bool operator<(const Event &rhs) const {
	return year < rhs.year;
    }
};

// Print the event to the output stream
ostream & operator << (ostream &os, const Event &e) {
    return os << e.year << ' ' << e.name;
}

// Read the event from the input stream
istream &operator >> (istream &is, Event &e) {
    is >> e.year;
    getline(is, e.name);
    return is;
}

// A Node is an event and left & right pointers.
// It would be better to make this a class inside the Tree class,
// but this is the beginners forum.
class Node
{
public:
    Node (const Event &e) :
	event(e), left(NULL), right(NULL)
    {}
    Event event;
    Node *left, *right;
};

// A tree has all the member functions and a pointer to the root node.
class Tree
{
public:
    Tree() :
	root(NULL)
    {}
    
    void add (const Event &);
    const Event *find(const Event &e) {
	Node *pos = findPosition(root, e);
	return (pos ? &pos->event : NULL);
    }
    void preorder(ostream &os) {
	preorder(os, root, 0);
    }
    void preorder(ostream &, Node *, int indent);

    void inorder(ostream &os) {
	inorder(os, root, 0);
    }

    void inorder(ostream &, Node *, int indent);
    // This does most of the work for find and add. It returns a reference
    // to the pointer (root, or a nodes right or left pointer) where the
    // event is located, or should be located if you insert it.
    Node * &findPosition(Node *&, const Event &);
private:
    Node *root;
};


// pre-order print the node os at the indent level
void Tree::preorder(ostream &os, Node *node, int indent)
{
    if (node) {
	os << std::string(2*indent, ' ') << "+--- " << node->event << '\n';
	preorder(os, node->left, indent+1);
	preorder(os, node->right, indent+1);
    }
}


// in-order print the node os at the indent level
void Tree::inorder(ostream &os, Node *node, int indent)
{
    if (node) {
	inorder(os, node->left, indent+1);
	os << std::string(2*indent, ' ') << "+--- " << node->event << '\n';
	inorder(os, node->right, indent+1);
    }
}


Node * &
Tree::findPosition(Node *&node, const Event &e)
{
    if (node == NULL) return node;
    if (e < node->event) {
	return findPosition(node->left, e);
    } else if (node->event < e) {
	return findPosition(node->right, e);
    } else {
	return node;
    }
}

void
Tree::add (const Event &e)
{
    Node * &pos = findPosition(root, e);
    if (pos) {
	pos->left = new Node(e);	// duplicate entry. Add to left
    } else {
	pos = new Node(e);
    }
}




int main()
{
    Tree tree;
    string str;			// use a string instead array of chars
    Event e;
    
    // Skip the first line
    getline(cin, str);
    while (cin >> e) {
	tree.add(e);
    }
    cout << "IN ORDER:\n";
    tree.inorder(cout);
    cout << "\n\nPRE ORDER:\n";
    tree.preorder(cout);
}

Topic archived. No new replies allowed.