Hi, I got homework about tree data structure
professor wrote his own tree stuff which are: binnode.h and bintree.h
the actual file is tree.cpp
binnode.h
#ifndef BINNODE_H
#define BINNODE_H
#include <math.h>
#include <iostream>
/*******************************************************\
template node class for binary tree
\********************************************************/
template <typename dataType> class binNode
{
private:
dataType nodeData;
binNode<dataType> *left, *right;
void deleteNode(binNode<dataType> **root) {
if (left == NULL && right == NULL) {
// leaf node
*root = NULL;
} else if (left == NULL) {
// right branch but no left branch
*root = right;
} else if (right == NULL) {
// left branch but no right branch
*root = left;
} else {
// has left and right branch
binNode<dataType> *temp = right;
// find left most node of right branch
while (temp->left != NULL) temp = temp->left;
// attach left branch to left side of right branch
temp->left = left;
// make root point to right branch
*root = right;
}
left = NULL;
right = NULL;
delete (this);
}
public:
// constructor
binNode() : left(NULL), right(NULL) {
}
binNode(const dataType& dataItem) :
nodeData(dataItem), left(NULL), right(NULL) {
}
// destructor
~binNode() {
if (left != NULL) delete left;
if (right != NULL) delete right;
}
void insert(const dataType& dataItem) {
if (nodeData == dataItem) {
throw std::invalid_argument("dataItem already in tree");
}
if (dataItem < nodeData) {
if (left == NULL) {
left = new binNode(dataItem);
} else {
left->insert(dataItem);
}
} else {
if (right == NULL) {
right = new binNode(dataItem);
} else {
right->insert(dataItem);
}
}
}
void erase(binNode<dataType> **root, const dataType &delData) {
if (delData == nodeData) {
deleteNode(root);
} else {
if (delData < nodeData) {
if (left == NULL) {
throw std::invalid_argument("delItem not in tree");
} else {
left->erase(&left, delData);
}
} else {
if (right == NULL) {
throw std::invalid_argument("delItem not in tree");
} else {
right->erase(&right, delData);
}
}
}
}
dataType* find(const dataType &findData) {
if (findData == nodeData) {
return &nodeData;
} else if (findData < nodeData) {
if (left == NULL) return NULL;
else return left->find(findData);
} else {
if (right == NULL) return NULL;
else return right->find(findData);
}
}
bool rebalance(binNode<dataType>* &root) {
int rdepth=0, ldepth=0;
bool rotate = false;
if (left != NULL) {
if (left->rebalance(left)) rotate = true;
ldepth = left->maxTreeDepth();
}
if (right != NULL) {
if (right->rebalance(right)) rotate = true;
rdepth = right->maxTreeDepth();
}
if (rdepth > ldepth+1) {
// rotate anitclockwise
root = right;
right = right->left;
root->left = this;
rotate = true;
}
else if (ldepth > rdepth+1) {
// rotate clockwise
root = left;
left = left->right;
root->right = this;
rotate = true;
}
return rotate;
}
// tree statistic functions
int maxTreeDepth() const {
int rdepth = 0, ldepth = 0;
if (left != NULL) ldepth = left->maxTreeDepth();
if (right != NULL) rdepth = right->maxTreeDepth();
if (ldepth > rdepth) return 1 + ldepth;
else return 1 + rdepth;
}
int numNodes() const {
int size = 1;
if (left != NULL) size += left->numNodes();
if (right != NULL) size += right->numNodes();
return size;
}
void print() const {
if (left != NULL) left->print();
std::cout << nodeData.toString() << "\n";
if (right != NULL) right->print();
}
int numLeafNodes() const {
if (left == NULL && right == NULL) return 1;
int numLeaf = 0;
if (left != NULL) numLeaf += left->numLeafNodes();
if (right != NULL) numLeaf += right->numLeafNodes();
return numLeaf;
}
// overloaded dereference operator
const dataType& operator * () const {
return nodeData;
}
};
#endifbintree.h
#ifndef BINTREE_H_
#define BINTREE_H_
#include <stdexcept>
#include <math.h>
#include "binnode.h"
/********************************************************\
template class for a binary tree
\********************************************************/
template <typename dataType> class bintree
{
private:
binNode<dataType> *root;
int numItems;
public:
/*******************************************************\
constructors & destructors
\*******************************************************/
// constructor
bintree() : root(NULL), numItems(0) {}
// destructor
~bintree() {
if (root != NULL) delete root;
}
/*******************************************************\
misc functions
\*******************************************************/
bool empty() const {
return (numItems == NULL);
}
int size() const {
return numItems;
}
int numNodes() const {
if (root == NULL) {
return 0;
} else {
return root->numNodes();
}
}
int maxTreeDepth() const {
if (root == NULL) {
return 0;
} else {
return root->maxTreeDepth();
}
}
int numLeafNodes() const {
if (root == NULL) {
return 0;
} else {
return root->numLeafNodes();
}
}
double balance() const {
// Returns a measure of how balanced a tree is.
// A value of 1 is a prefectly balanced tree.
// The closer to 0 the value is the more unbalanced
// the tree.
// A value < 0.5 indicates a tree that is seriously unbalanced
// case of no nodes in tree
if (numItems == 0) return 1.0;
// calculate balance
double log2numItems = log10(numItems + 1) / log10(2);
return log2numItems / maxTreeDepth() * (numLeafNodes() * 2) / (numItems + 1);
}
void rebalance() {
// Rebalance tree using the AVL algorithm
// While this does not guarantee a perfectly balanced tree
// it does make it mostly balanced by guranteeing that the diference
// in depth between every right and left subtree is at most 1
if (root != NULL) {
while (root->rebalance(root));
}
}
/*******************************************************\
insertion and erasure functions
\*******************************************************/
void insert(const dataType& newData) {
if (root == NULL) {
root = new binNode<dataType>(newData);
} else {
root->insert(newData);
}
numItems++;
}
void erase(const dataType& delData) {
if (root == NULL) {
throw std::invalid_argument("data does not exist in tree to erase");
}
root->erase(&root, delData);
numItems--;
}
dataType* find(const dataType &findData) const {
// this function looks for findData in ther tree.
// If it find the data it will return the address of the data in the tree
// otherwise it will return NULL
if (root == NULL) return NULL;
else return root->find(findData);
}
/*******************************************************\
print function for assignment.
assumes dataType has print() function
\*******************************************************/
void print() const {
if (root != NULL) root->print();
}
};
#endifhere is the tree.cpp
#include <iostream>
#include "bintree.h"
using namespace std;
/* Small program to explore using binary trees.
The program fills a tree with number in the order 1 to 16;
It then prints some statistics about the tree
It then rebalances the tree calling the rebalance function
of bintree and then reprints the stats.
Can you figure out what this tree looks like when first constructed?
Can you figure out what balance value it could have if properly
balanced?
*/
void fillTree(const bintree<int> &treeRoot);
void printTreeStats(const bintree<int> &treeRoot);
int main()
{
bintree<int> treeRoot;
printTreeStats(treeRoot);
fillTree(treeRoot);
treeRoot.rebalance();
printTreeStats(treeRoot);
return 0;
}
void fillTree(const bintree<int> &treeRoot)
{
int *ptr;
for (int i=1; i<16; i++) {
ptr = new int(i);
treeRoot.insert(*ptr); //ERROR HAPPENS HERE
}
}
void printTreeStats(const bintree<int> &treeRoot)
{
cout << "Num nodes = " << treeRoot.size() << "\n";
cout << "Max tree depth = " << treeRoot.maxTreeDepth() << "\n";
cout << "Num leaf nodes = " << treeRoot.numLeafNodes() << "\n";
cout << "Tree balance = " << treeRoot.balance() << "\n";
printf("\n");
}the error says:
tree.cpp: in function 'void fillTree(const bintree<int>&)':
tree.cpp:39: error: passing 'const bintree<int>' as 'this' argument of
void bintree<dataType>::insert(const dataType&) [with dataType = int]' discards qualifiers
I have been trying to debug it... but couldn't find it >.<
I'm new to tree data structure..
Any help will be appreciated
