c++ binary tree

**Solarwin** · 12-29-2013

hi, there.
I am not sure how to build the tree with values:

Code:

struct Node *root = 1  root->left        = 2
  root->right       = 3
  root->left->left  = 4;
  root->left->right = 5;

Everything should be right except the main(). How to demonstrate this program correctly?

Code:

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include <stack>          // std::stack

using namespace std;

struct Node
{
    char value;
    Node* left;
    Node* right;
};

void Visit(Node* node)
{
    cout << node->value;
}

void InorderTraversal(Node* root)
{
    stack<Node*> s;

    Node* current = root;

    while (current != NULL)
    {
        s.push(current);
        current = current->left;
    }

    while (!s.empty())
    {
        current = s.top();
        s.pop();

        Visit(current);

        current = current->right;
        while (current != NULL)
        {
            s.push(current);
            current = current->left;
        }
    }
}

int main()
{
/* Constructed binary tree is
            1
          /   \
        2      3
      /  \
    4     5
  */
  struct Node *root = 1
  root->left        = 2
  root->right       = 3
  root->left->left  = 4;
  root->left->right = 5;

  InorderTraversal(root);
    return 0;
}

**iMalc** · 12-30-2013

We can tell that everything except main was not written by you, and main is very wrong.
This exercise is too advanced for you. You must first learn about "pointers", "structures" and ideally "dynamic memory allocation".

**jocdrew21** · 12-30-2013

Yes I agree with iMalc and normally I would give someone a huge hint when I know it.

Somethings to think about in main.

What you need you must create. What are you sending to

Code:

voidInorderTraversal(Node* root)

?

I don't think you need to be using <stack> just yet, learn what is really going on. I am still learning myself, and this is a great site to help a long the way. Also what you create you must destroy and give back to the free store "heap".

**jocdrew21** · 12-30-2013

Solarwin like I said I am learning to and now I have a question. Did I clean up correctly? I have recently realized I have a program about forgetting to clean up after myself. Thought this was a good opportunity to check.

Code:

void cleanUp(NodePtr head)
{
    NodePtr Current = head;
    NodePtr Temp = Current;
    
    while (Current != NULL) {
        
        Current=Current->left;
        Temp=Temp->right;
        
        delete Current;
        delete Temp;
    }
}

**laserlight** · 12-30-2013

Looks wrong to me. For example, you would not delete the root node since you immediately set the Current node to its left child on the first iteration of the loop. Then, the fact that you delete Current means that the next access to Current->left dereferences a pointer to an object that no longer exists.

By the way, there's probably no need for NodePtr: just write Node* instead.

**jocdrew21** · 12-30-2013

Code:

typedef struct Node
{
    char value;
    Node* left;
    Node* right;
}*NodePtr;

I just prefer this type of style above. Do you think it is confusing?

Code:

void cleanUp(NodePtr head)
{
    NodePtr Current = head;
    NodePtr Temp = head;
    NodePtr trail = head;
    NodePtr trailBuddy=head;
    
    while (Current != NULL) {
        
        Current=Current->right;
        Temp=Temp->left;
        trail=trail->right;
        trailBuddy=trailBuddy->left;
        
        delete Current;
        delete Temp;
    }
}

Ok so don't beat me up over the name to much but what I was thinking the temp and current nodes will be deleted and the trail and trail buddy would go to the next before they were deleted.

**laserlight** · 12-30-2013

Originally Posted by jocdrew21

I just prefer this type of style above. Do you think it is confusing?

Why do you prefer it? We might typedef a pointer to serve as an iterator, but then that's because the name iterator might serve as an interface by convention, and the pointer might later be replaced by a class, e.g., if actually the iterator is not necessarily random access. In this case, your type name alias contains an abbreviation for "pointer", so it seems that you gain nothing from this typedef.

Originally Posted by jocdrew21

what I was thinking the temp and current nodes will be deleted and the trail and trail buddy would go to the next before they were deleted.

The fact that you set Current = Current->left and then delete Current still means that on the next iteration, Current->left dereferences a pointer to an object that has been destroyed.

Even if you avoided this, your algorithm has a fundamental problem: suppose your binary tree is a complete tree with a height of say, 3. After the immediate children of the root have been destroyed, the left child of the left child of the root will be destroyed, but not the right child. The right child of the right child of the root will be destroyed, but not the left child. So on and so forth.

I think that you may need an explicit stack in order to use iteration to destroy such a tree (unless you happen to be storing the complete tree in an array, as per the usual heap implementation, but that's not the case here). Alternatively, you could use recursion.

**jocdrew21** · 12-30-2013

Never even thought of recursion... I am not even on this data structure yet but it looks pretty efficient. 0(1)?

Code:

void cleanUp(Node* head)
{
    if (head!=NULL) {
        cleanUp(head->left);
        cleanUp(head->right);
        delete head;
    }
}

**hk_mp5kpdw** · 12-30-2013

Originally Posted by jocdrew21

Never even thought of recursion... I am not even on this data structure yet but it looks pretty efficient. 0(1)?

O(N).

And recursion would make the inorder traversal a snap as well, just a few lines of code quite similar in looks to the cleanUp function with some minor adjustments.

OP: Are you trying to store/print characters or integers? If you declare that a node holds characters but store integers then when it comes time to print the data out, you aren't going to see 1, 2, 3... etc.. but the ascii characters that those values represent... unless you cast before printing but why do that when you should just change what is being stored from char to integer.

Thread: c++ binary tree

Thread Tools

Search Thread

Display

c++ binary tree

Similar Threads

Converting From Binary Tree to Threaded Binary Trees

can anyone teach me how to convert a general tree to binary tree and vice versa?

binary interface to binary search tree giving me SUCH A HEADACHE!!

display tree data in binary tree format

b-tree (not binary tree) implementation help

Tags for this Thread