Re: Threaded Binary Tree

[Paavo Helde]

On 28.11.2016 17:43, xero...@gmail.com wrote:
> For some reason the below program in not inserting correctly and I have tried now for days to figure out why. Seems I am missing something very simple.
> This is the insert function:

[...]

> This is the complete code:

[...]

This was not a complete code, there was no main(). Also, you did not say
what means "not inserting correctly". How did you call your code, what
result did you expect and what did you get instead?

At the moment I see only lots of misspelled 'curr' variables and also
that begin() goes into infinite loop because of data cycles created in
the tree constructor:

root_->right_ = root_->left_ = root_;

hth
Paavo

[Ike Naar]

On 2016-11-28, xero...@gmail.com <xero...@gmail.com> wrote:
> For some reason the below program in not inserting correctly and I
> have tried now for days to figure out why. Seems I am missing
> something very simple.
> This is the insert function:

> //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->leftThread = 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_);

> }
> }
> This is the complete code:

> [snip]
> template <class T>
> 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_;

> root_->leftThread = true;
> }

In the constructor for ThreadedTree, some members of the root node
are not initialized, such as root_->data and root->righttThread,
but the values of those members are used in insert().

[xerofoify]

Ok that makes sense was wondering how to do data as it's a template. Also whenever I call begin it never calls it for some reason but calls end fine.

[xerofoify]

Ok it works expect how to I setup data as it's templated. Otherwise it seems to work correctly.

[Popping mad]

On Mon, 28 Nov 2016 17:18:19 +0000, Ike Naar wrote:

>> root_->right_ = root_->left_ = root_; root_->leftThread = true;
>> }
>
> In the constructor for ThreadedTree, some members of the root node are not
> initialized, such as root_->data and root->righttThread, but the values of
> those members are used in insert().

try nullptr on them, perhaps.