Greetings all,
Sorry for the stupid question but I for whatever reason can't get this to work and
was wondering if it's me being stupid or something else. Below is a threaded binary
thread and its not passing this tester:
#include "threadedtree.h"
int main(void){
ThreadedTree<int> T;
T.insert(20);
T.insert(30);
T.printTree();
}
and should print
20 30
however what's weird is the insert passes the function internally but when I get
here it prints:
This is the threaded binary tree:
#include <iostream>
using namespace std;
//Threaded Binary Tree Class that is templated to hold Node pointers with data type T
template <class T>
class ThreadedTree{
//Internal Node Class for each Node in the tree
struct Node{
//Constructor for Node Class
//Takes the data to be held as a paramater and Node pointers for left and right elements
//defaults are nullptr for left and right elements and data is set to default value for data type T
Node(const T& data = T{}, Node* left = nullptr, Node* right = nullptr){
data_ = data;
right_ = right;
left_ = left;
}
T data_;
Node*left_;
Node* right_;
bool leftThread;
bool rightThread;
//Finds the leftmost from the struct Node pointer passed in, returns nullptr if the Node is nullptr
struct Node* leftMost(struct Node *n){
if (n == nullptr){
return nullptr;
}
while (n->left_ != nullptr){
n = n->left_;
}
return n;
}
//Finds the rightmost from the struct Node pointer passed in, returns nullptr if the Node is nullptr
struct Node* rightMost(struct Node *n){
if (n == nullptr){
return nullptr;
}
while (n->right_ != nullptr){
n = n->right_;
}
return n;
}
};
Node* root_;
Node* leftmost_;
Node* rightmost_;
void cleanup(Node* subtreeroot){
if(subtreeroot==root_){
return;
}
if (subtreeroot){
cleanup(subtreeroot->left_);
cleanup(subtreeroot->right_);
delete subtreeroot;
}
}
public:
class const_iterator{
protected:
friend class ThreadedTree;
//Constructor that sets curr_ internal Node for iterator to Node passed in agrument Node* c
const_iterator(Node* c){ curr_ = c; }
Node* curr_;
//Checks current node is not nullptr
bool checkData(){
return curr_ == nullptr;
}
public:
//Constructor that sets curr_ internal iterator Node to nullptr
const_iterator(){
curr_ = nullptr;
}
//Takes a interger and makes iterator point to next right element before returning previous element
const_iterator operator++(int){
if(curr_==nullptr){
}
const_iterator old = *this;
if (curr_->rightThread){
curr_ = curr_->right_;
}
else {
curr_ = curr_->left_;
curr_ = curr_->rightMost(curr_);
}
return const_iterator(old);
}
//Takes a interger and makes iterator point to next left element before returning previous element
const_iterator operator--(int){
const_iterator old =*this;
if(curr_==nullptr){
return nullptr;
}
if (curr_->leftThread){
curr_ = curr_->left_;
}
else{
curr_ = curr_->right_;
curr_ = curr_->leftMost(curr_);
}
return const_iterator(old);
}
//Takes no arguments and makes iterator point to next right element
const_iterator operator++(){
if (curr_==nullptr){
return nullptr;
}
if(curr_->rightThread){
curr_= curr_->right_;
}
else{
curr_ = curr_->left_;
curr_ = curr_->rightMost(curr_);
}
return iterator(curr_);
}
//Takes no arguments and makes iterator point to next left element
const_iterator operator--(){
if(curr_==nullptr){
return nullptr;
}
if(curr_->leftThread){
curr_ = curr_->right_;
}
else{
curr_ = curr_->right_;
curr_ = curr_->leftMost(curr_);
}
return iterator(curr_);
}
//Takes no arguments and returns internal Node of iterator
const T& operator*(){
return curr_->data_;
}
//Takes const_iterator reference and sees if internal element equals passed reference's element
bool operator==(const const_iterator& rhs) const{
return curr_ == rhs.curr_;
}
//Takes const_iterator reference and sees if internal element does not equals passed reference's element
bool operator!=(const const_iterator& rhs) const{
return curr_ != rhs.curr_;
}
friend class ThreadedTree;
};
class iterator :public const_iterator{
protected:
//Constructor that sets curr_ internal iterator Node to Node passsed
iterator(Node* c) :const_iterator(c){}
public:
// Constructor that sets curr_ internal iterator Node to nullptr
iterator() :const_iterator(){}
const T& operator*(){
return this->curr_->data_;
}
iterator operator++(int){
iterator old = *this;
if(this->checkData()) {
return nullptr;
}
if (this->curr_->rightThread){
this->curr_ = this->curr_->right_;
}
else{
Node* pass = this->curr_->left_;
this->curr_ = this->curr_->left_;
this->curr_ = this->curr_->rightMost(pass);
}
return iterator(old);
}
//Takes a interger and makes iterator point to left element before returning previous element
iterator operator--(int){
const_iterator old = *this;
if(this->checkData()){
return nullptr;
}
if (this->curr->leftThread){
this->curr = this->curr->right_;
}
else{
Node* pass = this->curr_->left_;
this->curr_ = this->curr_->right_;
this->curr_ = this->curr_->leftMost(pass);
}
return iterator(old);
}
//Takes a interger and makes iterator point to next right element before returning previous element
iterator operator++(){
if(this->checkData()){
return nullptr;
}
if (*this->curr->rightThread){
this->curr = this->curr->right_;
}
else{
this->curr_ = this->curr_->left_;
this->curr_ = this->curr_->rightMost(this->curr_->right_);
}
return iterator(this->curr_);
}
//Takes no arguments and makes iterator point to next right element
iterator operator--(){
if(this->checkData()){
return nullptr;
}
if(this->curr->leftThread){
this->curr = this->curr->right_;
}
else{
this->curr_ = this->curr_->right_;
this->curr_ = this->curr_->leftMost(this->curr_->left_);
}
return iterator(this->curr_);
}
friend class ThreadedTree;
};
//Constructor that creates new Tree, takes no arguments and sets tree to new state
ThreadedTree(){
root_ = new Node();
root_->right_ = root_->left_ = root_;
rightmost_ = leftmost_ = nullptr;
root_->leftThread = true;
}
void printTree()
{
Node *tmp = root_, *p;
for (;;)
{
p = tmp;
tmp = tmp->right_;
if (!p->rightThread)
{
while (!tmp->leftThread)
{
tmp = tmp->left_;
}
}
if (tmp == root_)
break;
cout<<tmp->data_<<" ";
}
cout<<endl;
}
//Takes const reference of type T and inserts it into tree, returns iterator to inserted Node
iterator insert(const T& data){
Node* p = root_;
for (;;){
if (p->data_ > data){
if (p->rightThread)
break;
p = p->right_;
}
else if (p->data_ < data){
if (p->leftThread)
break;
p = p->left_;
}
}
Node* tmp = new Node();
tmp->data_ = data;
tmp->rightThread = tmp->rightThread = true;
if (p->data_ < data){
tmp->right_ = p->right_;
tmp->left_ = p;
p->right_ = tmp;
p->rightThread = false;
return iterator(p->right_);
}
else{
tmp->right_ = p;
tmp->left_ = p->left_;
p->left_ = tmp;
p->leftThread = false;
return iterator(p->left_);
}
}
//Takes const reference of type T and finds it in table,if not found returns nullptr
iterator find(const T& data) const{
Node *tmp = root_->left_;
for (;;){
if (tmp->data_ > data){
if (tmp->rightThread)
return nullptr;
tmp = tmp->right_;
}
else if (tmp->data_ < data){
if (tmp->leftThread)
return nullptr;
tmp = tmp->left_;
}
else{
return iterator(tmp);
}
}
}
//Takes no arguments and returns leftmost Node in Tree as iterator
iterator begin(){
Node* curr = root_;
if (curr != nullptr) {
while(curr->left_!=nullptr){
curr = curr->left_;
}
}
return iterator(curr);
}
//Takes no arguments and returns rightmost Node in Tree as iterator
iterator end(){
return nullptr;
}
//Takes no arguments and returns leftmost Node in Tree as const_iterator
const_iterator begin() const{
Node* curr = root_;
if (curr != nullptr) {
while(curr->left_!=nullptr){
curr = curr->left_;
}
}
return const_iterator(curr);
}
//Takes no arguments and returns rightmost Node in Tree as iterator
const_iterator end() const{
return nullptr;
}
//Destructor that destroys tree
~ThreadedTree(){
cleanup(root_);
}
};
I assume I am doing something stupid but wanted to known if I am as it worked like 2 day ago with the same code under g++ for insert and now it
doesn't.
Huge Thanks for any Advice,
Nick
