0
\$\begingroup\$

I am writing code for breadth-first search of a tree with C++'s STL. Please help as I am new to the STL.

#include<iostream>
#include<malloc.h> //on llvm we don't need this
#include<list>
using namespace std;
typedef struct Node{
    int val;
    struct Node* left;
    struct Node* right;
}node;
void push(node** root,int val)
{
    if(!(*root))
    {
        node* temp=(node*)malloc(sizeof(node));
        temp->val=val;
        temp->right=temp->left=NULL;
        *root=temp;
    }
    else if(val<(*root)->val)
        push(&((*root)->left),val);
    else
        push(&((*root)->right),val);
}

void printout(node* head)
{
    node* temp;
    temp=head;
    list<node*>qu;

    //using bfs here
    while(temp!=NULL)
    {
        cout<<temp->val<<endl;
        if(temp->left!=NULL)
            qu.push_back(temp->left);
        if(temp->right!=NULL)
            qu.push_back(temp->right);

        free(temp);
            if (qu.empty())
            {   break;
            }

        temp=qu.front();
        qu.pop_front();
    }
}

int main()
{
    node* root=NULL;
    push(&root,3);
    push(&root,4);
    push(&root,1);
    push(&root,10);
    push(&root,2);
    printout(root);
}

The output is:

3
1
4
2
10
\$\endgroup\$
3
\$\begingroup\$

Don't use malloc(). If you do then you will need to track memory that is allocated with new and that allocated with malloc and use the appropriate de-allocation functions. Also using new calls the constructor and makes sure the object is correctly initialized.

#include<malloc.h> //on llvm we don't need this

Don't do this:

using namespace std;

See Why is “using namespace std;” considered bad practice?

In C++ you don't need to typedef structs. struct names are in the same namespace as everything else. Also Add a constructor to make sure things are correctly initialized.

typedef struct Node{
    int val;
    struct Node* left;
    struct Node* right;
}node;

// Prefer
struct Node
{
     int    val;
     Node*  left;
     Node*  right;
     Node(int v):val(v), left(NULL), right(NULL) {}
};

When pushing a value onto a tree or list. Return the new value rather than pass out values.

void push(node** root,int val)

// Your current usage is:
push(&head, 5);

// Easier usage
head = push(head, 5);

Don't use C casts

        node* temp=(node*)malloc(sizeof(node));

If you must cast then use one of the C++ cast's. But any casts are a sign of bad design. Also using new means this is not required.

// Easier implementation of push:
Node* push(Node* current, value)
{
    if (current == NULL)
    {   return new Node(value);
    }

    if (value <= current->value)
        current->left  = push(current->left,  value);
    else
        current->right = push(current->right, value); 

    return current;
}

In your breadth first printing of the tree don't treat the head as special. You should just push the head node onto the list. The loop while the list is not empty. Thus you remove the item at the top of the loop not the bottom.

// Code deliberately left out to make you work.

Don't free the nodes as past of the print function. Add a destructor to your node. So that it calls delete on left and right.

~Node()
{    delete left;
     delete right;
}

Then all you need to do is delete the head and all the nodes will be destroyed correctly.

Your design should hide the memory management. You should put the head node inside its own structure. So that it hides all the memory management and you the user of your class does not need to worry about any of that

class Tree
{ 
    Node*   head;
    Tree(Tree const& copy);
    Tree& operator=(Tree const& rhs);
    public:
        Tree(): head(NULL) {}  // Set up empty tree.
       ~Tree() {delete head;}  // Memory management done.

        void push(int val)
        {
            head = ::push(head, val);
        }
        void printBF()
        {
            ::printout(head);
        }
};

Note the functions you wrote should also made as members of Node.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.