BST Node and Count Function Don't Work
Dec 2, 2013 at 1:07am UTC
Hello there. I have to do a BST project for school and I am almost there. Here is the code:
BINARY_SEARCH_TREE.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
#include "stdafx.h"
#include "genBST.h"
#include <iostream>
using namespace std;
int main()
{
BST<int > b;
int ch;
int tmp, tmp2;
b.insert(5);
b.insert(6);
b.insert(7);
b.insert(8);
b.insert(9);
b.insert(10);
b.NodeCount();
b.LeafCount();
//b.MirrorTree();
}
What I need help with is the output. When I run the program, it compiles correctly but does not give any output. I'm not sure what else to do. I've tried changing up the code in
nodeCount(), leafCount(), NodeCount(), and LeafCount(). I've tried adding a
count variable to both
nodeCount() and leafCount() but that didn't work. If I fiddle with the functions, I get a whole mess of errors. Currently, the code is stable but just won't output what I want it to. If you can figure out what I'm doing wrong, that would be most helpful.
I WILL INCLUDE THE HEADER ON ANOTHER POST BECAUSE IT IS TOO BIG TO FIT HERE.
Dec 2, 2013 at 1:08am UTC
genBST.h
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
//************************ genBST.h **************************
// generic binary search tree
#include <queue>
#include <stack>
#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE
template <class T>
class Stack : public stack<T> {
public :
T pop() {
T tmp = top();
stack<T>::pop();
return tmp;
}
};
template <class T>
class Queue : public queue<T> {
public :
T dequeue() {
T tmp = front();
queue<T>::pop();
return tmp;
}
void enqueue(const T& el) {
push(el);
}
};
template <class T> class BST;
template <class T>
class BSTNode {
public :
BSTNode() {
left = right = 0;
}
BSTNode(const T& e, BSTNode<T> *l = 0, BSTNode<T> *r = 0) {
el = e; left = l; right = r;
}
T el;
BSTNode<T> *left, *right;
};
template <class T>
class BST {
public :
BST() {
root = 0;
}
~BST() {
clear();
}
void clear() {
clear(root);
root = 0;
}
bool isEmpty() const {
return root == 0;
}
void preorder() {
preorder(root);
}
void inorder() {
inorder(root);
}
void postorder() {
postorder(root);
}
void insert(const T&);
void recursiveInsert(const T& el) {
recursiveInsert(root,el);
}
T* search(const T& el) const {
return search(root,el);
}
T* recursiveSearch(const T& el) const {
return recursiveSearch(root,el);
}
void deleteByCopying(BSTNode<T>*&);
void findAndDeleteByCopying(const T&);
void deleteByMerging(BSTNode<T>*&);
void findAndDeleteByMerging(const T&);
void iterativePreorder();
void iterativeInorder();
void iterativePostorder();
void breadthFirst();
void MorrisPreorder();
void MorrisInorder();
void MorrisPostorder();
void balance(T*,int ,int );
int NodeCount();
int LeafCount();
//void MirrorTree();
protected :
BSTNode<T>* root;
void clear(BSTNode<T>*);
void recursiveInsert(BSTNode<T>*&, const T&);
T* search(BSTNode<T>*, const T&) const ;
T* recursiveSearch(BSTNode<T>*, const T&) const ;
void preorder(BSTNode<T>*);
void inorder(BSTNode<T>*);
void postorder(BSTNode<T>*);
void nodeCount(BSTNode<T> *);
void leafCount(BSTNode<T> *);
//void mirrorTree(BSTNode<T> *p);
virtual void visit(BSTNode<T>* p) {
cout << p->el << ' ' ;
}
};
Dec 2, 2013 at 1:14am UTC
I HAVE SHORTENED IT TO INCLUDE ONLY THE MOST IMPORTANT FUNCTIONS.
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
template <class T>
void BST<T>::nodeCount(BSTNode<T>* ptr)
{
int count = 0;
if (ptr == NULL)
break ;
else
{
nodeCount(ptr->left);
nodeCount(ptr->right);
count++;
}
//return (1 + nodeCount(ptr->left) + nodeCount(ptr->right));
cout << count;
}
template <class T>
void BST<T>::leafCount(BSTNode<T>* ptr)
{
if (ptr == NULL)
return 0;
else
if (ptr->left == NULL && ptr->right == NULL)
return 1;
else
return (1 + leafCount(ptr->left) + leafCount(ptr->right));
}
template <class T>
int BST<T>::NodeCount()
{
return nodeCount(root);
}
template <class T>
int BST<T>::LeafCount()
{
return leafCount(root);
}
/*template<class T>
void BST<T>::MirrorTree(BSTNode<T>* root)
{
if (root == NULL)
return;
else
{
BSTNode<T>* temp;
MirrorTree(root.left);
MirrorTree(root.right);
temp = root.left;
root.left = root.right;
root.right = temp;
}
}
*/
#endif
Last edited on Dec 2, 2013 at 1:15am UTC
Dec 2, 2013 at 9:04am UTC
Just print the returned values form functions
1 2
cout << "Node Count: " << b.NodeCount() << endl;
cout << "Leaf Count: " << b.LeafCount() << endl;
Topic archived. No new replies allowed.