Binary tree/knowledge base design

Question

Currently I have a binary tree template setup where my main is using it with strings to make a question/answer game. I'm using a knowledge base that works as an interface to the binary tree that main uses. My code seems to work fine inserting/rearranging nodes as necessary but I think my design is pretty bad.

Is it usually best to just put the Node and BinaryTree classes in the same file since neither is independently useful?

I'm not sure how to not use class friending (assuming this is bad design) unless I just do away with the knowledge base. Without knowledge base being able to see private node members, it wouldn't be able to move it's "current" node pointer around the tree through questions/guesses unless it passed its current pointer by reference to a binary tree function that moved it each time.

Also with this setup, the binary tree doesn't really do anything except provide a root node. I'm also unsure how to move some traversal, etc. functionality from kbase to btree without just making a bunch of kbase functions that call their btree counterparts.

Is there a way to use std::swap in each file also without polluting with the utility header? This design looks to be bad OO-wise.

Node.h:

#ifndef NODE_H
#define NODE_H
#include <utility>

template<typename T>
class Node {
    friend class KnowledgeBase<T>;
public:
    Node() {lChild = rChild = nullptr;}
    Node(T& newData) {lChild = rChild = nullptr; data = newData;}
    ~Node();
    Node(const Node&);
    bool isLeaf() {return (lChild == nullptr) && (rChild == nullptr);}
    void setData(T newData) {data = newData;}
    void setRchild(Node* newRchild) {rChild = newRchild;}
    void setLchild(Node* newLchild) {lChild = newLchild;}

    Node<T>& operator=(const Node);
private:
    T data;
    Node *lChild;
    Node *rChild;
};

template<typename T>
Node<T>::~Node() {
    delete lChild;
    delete rChild;
    lChild = nullptr;
    rChild = nullptr;
}

template<typename T>
Node<T>::Node(const Node& other) {
    data = other.data;
    lChild = new Node<T>;
    rChild = new Node<T>;
    *lChild = *(other.lChild);
    *rChild = *(other.rChild);
}

template<typename T>
Node<T>& Node<T>::operator=(const Node other) {
    std::swap(data, other.data);
    std::swap(lChild, other.lChild);
    std::swap(rChild, other.rChild);
    return *this;
}

#endif  /* NODE_H */

BinaryTree.h:

#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <utility>

template<typename T> class Node;
template<typename T> class KnowledgeBase;

template<typename T>
class BinaryTree {
    friend class KnowledgeBase<T>;
public:
    BinaryTree() {root = nullptr;}
    ~BinaryTree() {delete root; root = nullptr;}
    BinaryTree(const BinaryTree&);

    BinaryTree<T>& operator=(const BinaryTree other);
private:
    Node<T> *root;
};

template<typename T>
BinaryTree<T>::BinaryTree(const BinaryTree& other) {
    root = new Node<T>;
    *root = *(other.root);
}

template<typename T>
BinaryTree<T>& BinaryTree<T>::operator=(const BinaryTree other) {
    std::swap(root, other.root);
    return *this;
}

#endif  /* BINARYTREE_H */

KnowledgeBase.h:

#ifndef KNOWLEDGEBASE_H
#define KNOWLEDGEBASE_H
#include <utility>

template<typename T> class BinaryTree;
template<typename T> class Node;

template<typename T>
class KnowledgeBase {
public:
    KnowledgeBase();
    ~KnowledgeBase() {delete current; current = nullptr;}
    KnowledgeBase(const KnowledgeBase&);

    void addQandA(T&, T&, char);
    void giveUp() {unableToGuess = true; guessedWrong = true;}
    bool outOfQ() {return unableToGuess == true;}
    bool isGuess() {return current->isLeaf();}
    T getQ() const {return current->data;}
    void resetTraverse() {current = bTree.root;}
    void traverse(char);

    KnowledgeBase<T>& operator=(const KnowledgeBase);
private:
    BinaryTree<T> bTree;
    Node<T> *current;
    bool unableToGuess, guessedWrong;
};

template<typename T>
KnowledgeBase<T>::KnowledgeBase() {
    current = bTree.root;
    unableToGuess = true;
    guessedWrong = false;
}

template<typename T>
KnowledgeBase<T>::KnowledgeBase(const KnowledgeBase& other) {
    bTree = other.bTree;
    unableToGuess = other.unableToGuess;
    guessedWrong = other.guessedWrong;
    current = new Node<T>;
    *current = *(other.current);
}

template<typename T>
void KnowledgeBase<T>::addQandA(T& question, T& answer, char side) {
    Node<T> *newQnode = new Node<T>(question);
    Node<T> *newAnode = new Node<T>(answer);
    newQnode->setRchild(newAnode);
    if (!guessedWrong) {
        if (!(bTree.root == nullptr)) {
            if ((side == 'y') || (side == 'Y'))
                current->rChild = newQnode;
            else
                current->lChild = newQnode;
        } else {
            bTree.root = newQnode;
        }
    } else { //wrong guess, need to move current node to "no" guess after "yes" from newAnswer
        Node<T> *nodeToMove = new Node<T>;
        nodeToMove->setData(current->data);
        nodeToMove->setRchild(current->rChild);
        nodeToMove->setLchild(current->lChild);
        current->setData(question);
        current->setRchild(newAnode);
        current->setLchild(nodeToMove);
    }
    guessedWrong = false;
    unableToGuess = false;
    current = bTree.root;
}

template<typename T>
void KnowledgeBase<T>::traverse(char direction) {
    if ((direction == 'y') || (direction == 'Y')) {
        if (current->rChild == nullptr)
            unableToGuess = true;
        else
            current = current->rChild;
    } else {
        if (current->lChild == nullptr)
            unableToGuess = true;
        else
            current = current->lChild;
    }
}

template<typename T>
KnowledgeBase<T>& KnowledgeBase<T>::operator =(const KnowledgeBase other) {
    std::swap(bTree, other.bTree);
    std::swap(unableToGuess, other.unableToGuess);
    std::swap(guessedWrong, other.guessedWrong);
    std::swap(current, other.current);
    return *this;
}

#endif  /* KNOWLEDGEBASE_H */

main.cpp:

#include "BinaryTree.h"
#include "KnowledgeBase.h"
#include "Node.h"
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
vector<char> vowels = {'a', 'e', 'i', 'o', 'u'};

int main(int argc, char** argv) {

    void playRound(KnowledgeBase<string>&);

    KnowledgeBase<string> Kbase;
    playRound(Kbase);
    return 0;
}

void playRound(KnowledgeBase<string>& Kbase) {
    void checkVowel(string, string);

    cout << endl << endl << "Ok. Think of an animal. Ready? ('y' to continue): ";
    char keepPlaying, traversalSide, guessResponse;
    cin >> keepPlaying;
    while ((keepPlaying == 'y') || (keepPlaying == 'Y')) {
        if (!Kbase.outOfQ()) { //still have questions/guesses left
            if (!Kbase.isGuess()) { //question found
                cout << Kbase.getQ() << " ";
                cin >> traversalSide;
                Kbase.traverse(traversalSide);
            } else { //guess found
                checkVowel(Kbase.getQ(), "Is it");
                cin >> guessResponse;
                if ((guessResponse == 'y') || (guessResponse == 'Y')) {
                    cout << "I win!" << endl;
                    cout << "Would you like to play again? ('y' or 'n')? ";
                    cin >> keepPlaying;
                    Kbase.resetTraverse();
                } else { //program guesses wrong, need to rearrange nodes
                    traversalSide = 'n';
                    Kbase.giveUp();
                }
            }
        } else { //out of questions/guesses
            cout << endl << "I give up. What is it? ";
            string newAnswer;
            cin >> newAnswer;
            checkVowel(newAnswer, "What question would tell me it's");
            string newQuestion;
            cin.ignore(80, '\n');
            getline(cin, newQuestion);
            Kbase.addQandA(newQuestion, newAnswer, traversalSide);
            cout << "Would you like to play again? ('y' or 'n'): ";
            cin >> keepPlaying;
            cout << endl;
        }
    }
}

void checkVowel(string toCheck, string output) {
    if (find(vowels.begin(), vowels.end(), toCheck.at(0)) != vowels.end())
        cout << output << " an " << toCheck << "? ";
    else
        cout << output << " a " << toCheck << "? ";
}

Answer 1

First of all, I'd rewrite the constructors to use member initialization lists instead of assignment in the body of the ctor (where possible). For example, Node's ctor could become:

Node(T& data) : data(data), lChild(nullptr), rChild(nullptr) { }

Your destructor for Node currently does some pointless work:

template<typename T>
Node<T>::~Node() {
    delete lChild;
    delete rChild;
    lChild = nullptr;
    rChild = nullptr;
}

After the dtor runs, the object no longer exists, so setting its members to nullptr accomplishes nothing useful. This can be reduced to just:

template<typename T>
Node<T>::~Node() {
    delete lChild;
    delete rChild;
}

I'd got a little further than just putting Node and BinaryTree in the same file. I'd make Node a nested class inside the BinaryTree class. I'd also add a get to the Node class, so KnowledgeBase can use it instead of accessing Node's private data directly.

template<typename T>
struct BinaryTree {
    struct Node {
        friend class KnowledgeBase<T>;

        Node() : lChild(nullptr), rChild(nullptr) { }
        Node(T& data) : data(data), lChild(nullptr), rChild(nullptr) { }
        Node(const Node&);

        bool isLeaf() { return (lChild == nullptr) && (rChild == nullptr); }
        void setData(T newData) { data = newData; }
        void setRchild(Node* newRchild) { rChild = newRchild; }
        void setLchild(Node* newLchild) { lChild = newLchild; }
        T get() const { return data; }

        Node& operator=(const Node);

        ~Node() {
            delete lChild;
            delete rChild;
        }

    private:
        T data;
        Node *lChild;
        Node *rChild;
    };

    BinaryTree() {root = nullptr;}
    ~BinaryTree() {delete root; root = nullptr;}
    BinaryTree(const BinaryTree&);

    BinaryTree& operator=(const BinaryTree other);
    friend class KnowledgeBase<T>;
private:
    Node *root;
};

I think at least for now I'll pass on reviewing KnowledgeBase -- I'm reasonably certain it's buggy. Specifically, at least part of the time, KnowledgeBase::current can contain a pointer to a node in KnowledgeBase::bTree. However, its destructor attempts to delete current;. This will result in a double-delete, since bTree is a member of KnowledgeBase, and will be destroyed automatically when the KnowledgeBase object is destroyed.

Answer 2

I am concerned that there might be a problem with your Node copy constructor.

template<typename T>
Node<T>::Node(const Node& other) {
    data = other.data;
    lChild = new Node<T>;
    rChild = new Node<T>;
    *lChild = *(other.lChild);
    *rChild = *(other.rChild);
}

As it is written, you will traverse the entire tree and copy construct all of the children of other as desired, but when you finally hit a leaf node and either other.lChild or other.rChild are nullptr, you'll be dereferencing a nullptr and the program will crash.