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.

• Instinct: Thanks for suggestions, I implemented all of these changes and now have 0 friending for no private data access from other classes. But does using gets in this way "break" encapsulation? Now my node class has a get and set for each private member, along with the a get/set for the binary tree's root for changing it and resetting the traversal pointer current in kbase. This seems just as open as friending? Is the only way to get around this to remove a knowledge base class and allow main to communicate directly with the binary tree class?
• Jerry Coffin: @Instinct: Public get/set pairs generally point to poor design, or else something that should probably just be a struct with public members. In this case, putting node inside of BinaryTree (mostly) protects it from "public" consumption in any case, so it can make sense to just make it a struct with all its contents public (but only perhaps accessible only to the BinaryTree class).
• Instinct: Updated moving node inside tree as a struct, along with moving functionality over to tree leaving kbase just as an interface between main and tree to improve encapsulation. Does this look correct? No get/set pairs now although kbase mostly just passes things back and forth between tree and main, but that way nothing can be directly manipulated from main.

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.

• Instinct: True didn't think of this, using cout's to check though the node's copy ctor is never even being used, only the default and non-defaults. What a good fix though be just calling isLeaf() on other first?
• YoungJohn: no, calling isLeaf will only check if both children are nullptr. You'll need to check each child individually before you new it up. If you find that one of the children from other is a nullptr just set your child to nullptr, no allocation from new, no dereferencing.