BinaryTree will not assign newly created node

Question

The problem lies in the insert method with two parameters. The function, insert(char letter, string code), calls insert(TreeNode *node, char letter, char code). However it does not assign the left or right child as the node. The insert method with three parameters should create a new node. Then this node should be assigned as either a left or a right child.

#include "tree.h"
#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::endl;

BinaryTree::BinaryTree() {
    root = nullptr;
}

BinaryTree::~BinaryTree() {
    empty_tree(root);
}

void BinaryTree::empty_tree(TreeNode *node) {
    if (root) {
        if (node->left) {
            return empty_tree(node->left);
        }
        if (node->right) {
            return empty_tree(node->right);
        }
        delete node;
    }
}

void BinaryTree::insert(char letter, string code) {
    TreeNode *node = root;
    TreeNode *temp = nullptr;
    if (node) {
        for (string::size_type i = 0; i < code.length(); i++) {
            //temp = node;
            if (code[i] == '.') {
                if (node->left) {
                    node = node->left;
                }
                else {
                    insert(temp, letter, code[i]);
                    node->left = temp;

                }
            }
            else {
                if (node->right) {
                    node = node->right;
                }
                else {
                    return insert(temp, letter, code[i]);
                    node->right = temp;
                }
            }
        }
    }
    /*else {
        return insert();
    }*/
}

void BinaryTree::insert() {
    if (!root) {
        root= new TreeNode();
        root->letter = '*';
        root->left = nullptr;
        root->right = nullptr;
        root->code = "*";
    }
}

void BinaryTree::insert(TreeNode *node, char letter, char code) {
    if (!node) {
        node = new TreeNode();
        node->letter = letter;
        node->left = nullptr;
        node->right = nullptr;
        node->code += code;
    }
}

void BinaryTree::print_tree() {
    return print_tree(root);
}

void BinaryTree::print_tree(TreeNode *tree) {
    if (tree) {
        if (tree->left) {
            print_tree(tree->left);
        }
        if (tree->right) {
            print_tree(tree->right);
        }
        cout << "Node is " << tree->letter << " and in Morse Code is " << tree->code << endl << endl;
    }
}

Below is the file containing main. The morse-code.txt file just has the alphabet letters in order from a to z. Each line has one letter, followed by a space, followed by the morse code.

#include "tree.h"
#include <iostream>
#include <fstream>
#include <string>

using std::cout;
using std::endl;

int main() {
    std::string code;
    std::ifstream infile;
    char letter;
    BinaryTree tree;;

    infile.open("morse-code.txt");
    if (!infile) {
        std::cout << "File unable to open" << std::endl;
    }
    else {
        cout << "morse-code.txt\n\n";
        tree.insert();
        while (std::getline(infile, code)) {
            tree.insert(code[0], code.substr(2, code.length()-2));
            cout << code << endl;
        }
        cout << "\n******Tree Representation******\n\n";
        tree.print_tree();
    }
    system("pause");
}

text file

a .-
b -...
c -.-.
d -..
e .
f ..-.
g --.
h ....
i ..
j .---
k -.-
l -.--
m --
n -.
o ---
p .--.
q --.-
r .-.
s ...
t -
u ..-
v ...-
w .--
x -..-
y -.--
z --..

tree.h

#ifndef _TREE_H
#define _TREE_H

//#include <iostream>
//#include <fstream>
#include <string>

using std::string;

class BinaryTree {
private:
    struct TreeNode {
        char letter;
        string code;
        TreeNode *left;
        TreeNode *right;
    }; TreeNode *root;

public:
    BinaryTree();
    ~BinaryTree();
    void insert();
    void insert(TreeNode *new_node, char letter, char code);
    void insert(char letter, string code);
    void empty_tree(TreeNode *node);
    void print_tree(TreeNode *node);
    void print_tree();
};
#endif

Answer 1

So the problem was in my tree_driver.cpp file. Most of the problems contained in that file were in the insert function with two parameters. Below is the working code.

tree_driver.cpp

#include "tree.h"
#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::endl;

BinaryTree::BinaryTree() {
    root = nullptr;
}

BinaryTree::~BinaryTree() {
    empty_tree(root);
}

void BinaryTree::empty_tree(TreeNode *node) {
    if (!node) {
        if (node->left) {
            empty_tree(node->left);
        }
        if (node->right) {
            empty_tree(node->right);
        }
        delete node;
    }
}

//The following member function contains the most alterations
void BinaryTree::insert(char letter, string code) {
    if (!root) {
        insert(root, letter, code, true);
    }
    else {
        TreeNode *node = root;
        for (string::size_type i = 0; i < code.length(); i++) {
            if (code[i] == '.') {
                if (!node->left) {
                    if (i == code.length() - 1) {
                        insert(node->left, letter, code.substr(0, i + 1), true);
                    }
                    else {
                        insert(node->left, letter, code.substr(0, i + 1), false);
                    }
                }
                node = node->left;
                if (node->left) {
                    if (i == code.length() - 1) {
                        node->letter = letter;
                    }
                }
                if (!node->left) {
                    if (i == code.length() - 1) {
                        node->letter = letter;
                    }
                }
            }
            else if (code[i] == '-') {
                if (!node->right) {
                    if (i == code.length() - 1) {
                        insert(node->right, letter, code.substr(0, i + 1), true);
                    }
                    else {
                        insert(node->right, letter, code.substr(0, i + 1), false);
                    }
                }
                node = node->right;
                if (node->right) {
                    if (i == code.length() - 1) {
                        node->letter = letter;
                    }
                }
                if (!node->right) {
                    if (i == code.length() - 1) {
                        node->letter = letter;
                    }
                }
            }
        }
    }
}

void BinaryTree::insert(TreeNode *&node, char letter, string code, bool last) {
    if (last) {
            node = new TreeNode();
            node->letter = letter;
            node->right = nullptr;
            node->left = nullptr;
            node->code = code;
    }
    if (!last) {
            node = new TreeNode();
            node->letter = '\0';
            node->right = nullptr;
            node->left = nullptr;
            node->code = code;
    }
}

void BinaryTree::print_tree() {
    print_tree(root);
}

void BinaryTree::print_tree(TreeNode *tree) {
    if (tree) {
        if (tree->left) {
            print_tree(tree->left);
        }
        cout << "Node is " << tree->letter << " and in Morse Code is " << tree->code << endl << endl;
        if (tree->right) {
            print_tree(tree->right);
        }
    }
}

tree_tester.

#include "tree.h"
#include <iostream>
#include <fstream>
#include <string>

using std::cout;
using std::endl;

int main() {
    std::string code_main;
    std::ifstream infile;
    BinaryTree tree;;

    infile.open("morse-code.txt");
    if (!infile) {
        std::cout << "File unable to open" << std::endl;
    }
    else {
        cout << "morse-code.txt\n\n";
        tree.insert('0', "*");
        while (std::getline(infile, code_main)) {
            tree.insert(code_main[0], code_main.substr(2, code_main.length()-2));
            cout << code_main << endl;
        }
        infile.close();
        cout << "\n******Tree Representation******\n\n";
        tree.print_tree();
    }
    system("pause");
    return 0;
}

tree.h

#ifndef _TREE_H
#define _TREE_H

#include <string>

using std::string;

class BinaryTree {
private:
    struct TreeNode {
        string letter;
        string code;
        TreeNode *left;
        TreeNode *right;
    }; TreeNode *root;

public:
    BinaryTree();
    ~BinaryTree();
    /*void insert();*/
    void insert(TreeNode *&new_node, char letter, string code, bool last);
    void insert(char letter, string code);
    void empty_tree(TreeNode *node);
    void print_tree();
    void print_tree(TreeNode *node);
};
#endif

Answer 2

I think that insert isn't the only problems you have with your code. Your empty_tree is incorrect (will not free all of the memory, since you return prematurely. The specific part of the code you have wrong is the following line of your code: "return insert(temp, letter, code[i]);" The rest of your code looks fine.

It should look something like this instead:

void BinaryTree::empty_tree(TreeNode *node) {
    if (!node) return;
    delete node;
    empty_tree(node->left );
    empty_tree(node->right);
    /* See Jerry's solution below. */
}

void BinaryTree::insert(char letter, string code) {
    TreeNode *node = root;
    if (!root) /* do something*/;
    for (string::size_type i = 0; i < code.length(); i++) {
        if (code[i] == '.') {
            if (node->left)
                insert(&node->left, letter, code[i]);
            node = node->left;
        }
        else {
            if (!node->right)
                insert(&node->right, letter, code[i]);
            node = node->right
        }
    }
}

void BinaryTree::insert(TreeNode **node, char letter, string code) {
    *node = new TreeNode();
    (*node)->letter = letter;
    (*node)->left = nullptr;
    (*node)->right = nullptr;
    (*node)->code = code;
}

In tree.h:

typedef struct _TreeNode {
    char letter;
    string code;
    struct _TreeNode *left;
    struct _TreeNode *right;
} TreeNode; TreeNode *root;

I *compiled the following code:

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

typedef struct _TreeNode {
    char letter;
    string code;
    struct _TreeNode *left;
    struct _TreeNode *right;
} TreeNode;

class BinaryTree {
private:
    TreeNode *root;
public:
    BinaryTree();
    ~BinaryTree();
    void insert();
    void insert(TreeNode **new_node, char letter, string code);
    void insert(char letter, string code);
    void empty_tree(TreeNode *node);
    void print_tree(TreeNode *node);
    void print_tree();
};

BinaryTree::BinaryTree() {
    root = nullptr;
}

BinaryTree::~BinaryTree() {
    empty_tree(root);
}

void BinaryTree::empty_tree(TreeNode *node) {
    if (!node) return;
    delete node;
    empty_tree(node->left );
    empty_tree(node->right);
}

void BinaryTree::insert(char letter, string code) {
    TreeNode *node = root;
    if (!root) insert();
    for (string::size_type i = 0; i < code.length(); i++) {
        if (code[i] == '.') {
            if (!node->left)
                insert(&node->left, letter, code.substr(0,i));
            node = node->left;
        } else {
            if (!node->right)
                insert(&node->right, letter, code.substr(0,i));
            node = node->right;
        }
    }
}

void BinaryTree::insert() {
    root = new TreeNode();
    root->letter = '*';
    root->left = nullptr;
    root->right = nullptr;
    root->code = "*";
}

void BinaryTree::insert(TreeNode **node, char letter, string code) {
    *node = new TreeNode();
    (*node)->letter = letter;
    (*node)->left = nullptr;
    (*node)->right = nullptr;
    (*node)->code = code;
}

void BinaryTree::print_tree() {
    return print_tree(root);
}

void BinaryTree::print_tree(TreeNode *tree) {
    if (tree) {
        if (tree->left ) print_tree(tree->left );
        cout << "Node is " << tree->letter << " and in Morse Code is "
             << tree->code << endl << endl;
        if (tree->right) print_tree(tree->right);
    }
}

int main() {
    string code;
    ifstream infile;
    char letter;
    BinaryTree tree;

    infile.open("morse-code.txt");
    if (!infile) {
        cout << "File unable to open" << endl;
    }
    else {
        cout << "morse-code.txt\n\n";
        tree.insert();
        while (std::getline(infile, code)) {
            tree.insert(code[0], code.substr(2, code.length()-2));
            cout << code << endl;
        }
        cout << "\n******Tree Representation******\n\n";
        tree.print_tree();
    }
    system("pause");
}