I am new to binary trees. I have been given the task to write functions to count the number of nodes, to count the number of leaves in nodes, to count the number of right children, to find the height of the tree, and to delete all the leaves of the binary tree. I believe I have coded correctly, however when I compile I am getting the warning C4101: 'p' : unreferenced local variable.
Here is what I have so far:
#include <queue>
#include <stack>
#include <list>
#include <iostream>
using namespace std;
template <class T>
class Queue{
public:
Queue(){
}
void clear(){
lst.clear();
}
bool isEmpty() const{
return lst.empty();
}
T& front(){
return lst.front();
}
T dequeue(){
T el= lst.front();
lst.pop_front();
return el;
}
void enqueue(const T& el) {
lst.push_back(el);
}
private:
list<T> lst;
};
template <class T>
class BSTNode{
public:
BSTNode(){
left=right=0;
}
BSTNode(const T& el, BSTNode *l=0, BSTNode *r=0){
key=el; left=l;right =r;
}
T key;
BSTNode *left, *right;
};
template<class T>
class BST2 {
public:
BST2() {
root = 0;
}
T* search(const T& el) const{
return search( root, el);
}
void insert(const T&);
BSTNode<T>* breadthFirstSearch(const T& el) const;
void inorder() {
inorder(root);
}
int numberOfNodes() {
return numberOfNodes(root);
}
int numberOfLeaves() {
return numberOfLeaves(root);
}
int numberOfRightChildren() {
return numberOfRightChildren(root);
}
int heightOfTree() {
return heightOfTree(root);
}
void deleteAllLeaves() {
deleteAllLeaves(root);
}
protected:
BSTNode<T>* root;
T* search(BSTNode<T> *p, const T& el) const;
void visit(BSTNode<T> *p) {
cout<<p->key<<" ";
}
void inorder(BSTNode<T>*);
int numberOfNodes(BSTNode<T> *p);
int numberOfLeaves(BSTNode<T> *p);
int numberOfRightChildren (BSTNode<T> *p);
int heightOfTree (BSTNode<T> *p);
void deleteAllLeaves (BSTNode<T> *p);
};
template<class T>
T* BST2<T>::search( BSTNode<T> *p, const T& el) const{
while (p!=0)
if (el == p->key)
return &p->key;
else if (el < p->key)
p=p->left;
else p=p->right;
return 0;
}
template<class T>
void BST2<T>::insert(const T& el) {
BSTNode<T> *p = root, *prev = 0;
while (p != 0) { // find a place for inserting new node;
prev = p;
if (p->key < el)
p = p->right;
else p = p->left;
}
if (root == 0) // tree is empty;
root = new BSTNode<T>(el);
else if (prev->key < el)
prev->right = new BSTNode<T>(el);
else prev->left = new BSTNode<T>(el);
}
template<class T>
BSTNode<T>* BST2<T>::breadthFirstSearch(const T& el) const {
Queue<BSTNode<T>*> queue;
BSTNode<T> *p = root;
if (p != 0) {
queue.enqueue(p);
while (!queue.isEmpty()) {
p = queue.dequeue();
if (p->key == el)
return p;
if (p->left != 0)
queue.enqueue(p->left);
if (p->right != 0)
queue.enqueue(p->right);
}
}
return 0;
}
template<class T>
void BST2<T>::inorder(BSTNode<T> *p) {
if (p != 0) {
inorder(p->left);
visit(p);
inorder(p->right);
}
}
template<class T>
int BST2<T>::numberOfNodes(BSTNode<T> *p) {
if (p!=0)
return numberOfNodes(p->left)+1+numberOfNodes(p->right);
else
return 0;
}
template<class T>
int BST2<T>::numberOfLeaves(BSTNode<T> *p) {
if (p==0)
return 0;
if (p->left==0 && p->right ==0)
return 1;
else
return numberOfLeaves(p->right)+numberOfLeaves(p->left);
}
template<class T>
int BST2<T>::numberOfRightChildren(BSTNode<T> *p)
{
if (p==0)
return 0;
if (p->right !=0)
return numberOfRightChildren (p->right) + 1 + numberOfRightChildren (p->left);
else
return numberOfRightChildren (p->left);
}
template<class T>
int BST2<T>::heightOfTree(BSTNode<T> *p)
{
int leftTr=0,RightTr=0;
if(p==0)
return 0;
if(p->left !=0)
{leftTr=heightOfTree(p->left);}
if(p->right !=0)
{RightTr=heightOfTree(p->right);}
return(max(leftTr,RightTr)+1);
}
template<class T>
void BST2<T>::deleteAllLeaves(BSTNode<T> *p)
{
if(p !=0)
{
deleteAllLeaves(p->left);
deleteAllLeaves(p->right);
delete p;
}
}
int main() {
int number, n;
BST2<int> tree;
BSTNode<int> *p;
cout<<"Enter the number of nodes: ";
cin >>number;
for (int i=0; i<number; i++) {
cout << "Enter the node ";
cin >> n;
tree.insert(n);
}
cout << endl;
tree.inorder();
cout<<endl;
cout<<"The number of nodes is "<<tree.numberOfNodes()<<endl;
cout << " The number of leaves is " << tree.numberOfLeaves() << endl;
cout << " The number of Right Children is " << tree.numberOfRightChildren() << endl;
cout << "The Height of the Tree is " << tree.heightOfTree() << endl;
tree.deleteAllLeaves();
return 0;
}