Need assistance with binary tree
Apr 20, 2011 at 11:30pm UTC
Hi I need help with my binary search tree. This is what I have so far. I have created 2 classes. One that will store an integer value and two pointers to the left and right called TNode and the other I'm having trouble with. The other class is suppose to be a binary search tree. Its purpose is to add elements to the tree and output the results in inorder traversal. Here's what I have so far:
main.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 25 26 27 28 29 30 31 32
#include "TNode.h"
#include "bsTree.h"
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
TNode<int > intNode1(5);
TNode<int > intNode2(3);
TNode<int > intNode3(7);
intNode1.setLeft(&intNode2);
intNode1.setRight(&intNode3);
intNode1.setData(6);
cout<<"Printing the value of nodes" <<endl;
cout<<"===========================" <<endl;
cout<<intNode1.getData()<<endl;
cout<<intNode2.getData()<<endl;
cout<<intNode3.getData()<<endl;
cout<<"Left child of node 1 : " <<intNode1.getLeft()->getData()<<endl;
cout<<"Right child of node 1 : " <<intNode1.getRight()->getData()<<endl;
// bsTree<int> tree1;
// tree1.insert(5);
// tree1.insert(4);
// tree1.insert(6);
// tree1.inOrderTraversal();
}
TNode.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
#ifndef TNode_H
#define TNode_H
#include <iostream>
#include <string>
using namespace std;
template <typename T>
class TNode {
public :
TNode(T val);
//~TNode();
T getData() const ;
void setData(T val);
void addChild(TNode<T>* p);
void setLeft(TNode<T> * n);
void setRight(TNode<T> * n);
TNode<T>* getLeft( );
TNode<T>* getRight( );
private :
T data;
TNode<T>* left;
TNode<T>* right;
};
#include "TNode.cpp"
#endif;
TNode.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 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
#include "TNode.h"
template <typename T>
TNode<T>::TNode(T val) : data(val), left(NULL), right(NULL) {
}
/*
template <typename T>
TNode<T>::~TNode() {
delete left;
delete right;
}
*/
template <typename T>
T TNode<T>::getData() const {
return data;
}
template <typename T>
void TNode<T>::setData(T val){
data = val;
}
template <typename T>
void TNode<T>::addChild(TNode<T>* p) {
T other = p->getData();
if (other > data)
if (right)
right->addChild(p);
else
right = p;
else
if (left)
left->addChild(p);
else
left = p;
}
template <typename T>
void TNode<T>::setLeft(TNode<T> * n) {
if (left)
left->setLeft(n);
else
left = n;
}
template <typename T>
void TNode<T>::setRight(TNode<T> * n) {
if (right)
right->setRight(n);
else
right = n;
}
template <typename T>
TNode<T>* TNode<T>::getLeft() {
return left;
}
template <typename T>
TNode<T>* TNode<T>::getRight() {
return right;
}
Now here is were I get stuck. What if I want to create a class called BinarySearchTree with a function that will allow me to to add an element to the tree while following the tree rules and an function that will allow me to traverse the list. This is briefly what I have. I know it probably doesn't make any sense but I'm working on it. Any help?
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
#ifndef BSTREE_H
#define BSTREE_H
#include <iostream>
#include <string>
#include "TNode.h "
using namespace std;
template <typename T>
class bsTree {
public :
bool isEmpty();
int treeSize();
T insert(T val);
T inOrderTraversal();
private :
TNode<T> * root;
int size;
};
#include "bsTree.cpp"
#endif;
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
#include "bsTree.h"
template <typename T>
bool bsTree<T>::isEmpty() {
return (treeSize() == 0);
}
template <typename T>
int bsTree<T>::treeSize() {
return size;
}
template <typename T>
T bsTree<T>::insert(T val) {
if (root == NULL)
return 0;
//TNode<T> *newNode = new TNode<T>(val);
//newNode.addChild(var);
TNode<T>->addChild(var);
size++;
}
template <typename T>
T bsTree<T>::inOrderTraversal(TNode<T> T* currentNode) {
if (!isEmpty)
return 0;
if (currentNode) {
inOrderTraveral(currentNode->LeftChild);
cout << currentNode->data;
inOrderTraveral(currentNode->RightChild);
}
}
Topic archived. No new replies allowed.