1
\$\begingroup\$

This code implements a binary tree for integers. How can I improve it?

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
///////////////////////////////
struct node{
    int data;
    struct node *left;
    struct node *right;
};
///////////////////////////////
struct node *newnode(int value)
{
    struct node *temp=(struct node *)malloc(sizeof(struct node));
    temp->data=value;
    temp->left=NULL;
    temp->right=NULL;
    return (temp);
}

void inorder_rec(struct node *temp)
{
    if(temp->left!=NULL)
    inorder_rec(temp->left);

    printf("%d",temp->data);

    if(temp->right!=NULL)
    inorder_rec(temp->right);
}

void preorder_rec(struct node *temp)
{
    printf("%d",temp->data);
    if(temp->left!=NULL)
    preorder_rec(temp->left);
    if(temp->right!=NULL)
    preorder_rec(temp->right);
}

void postorder_rec(struct node *temp)
{
    if(temp->left!=NULL)
    postorder_rec(temp->left);
    if(temp->right!=NULL)
    postorder_rec(temp->right);
    printf("%d",temp->data);
}
////////////////////////////////
int main()
{
    int option;
    option=1;
    struct node *root=newnode(1);
    root->left=newnode(2);
    root->right=newnode(3);
    root->left->left=newnode(4);
    root->left->right=newnode(5);
    root->right->left=newnode(6);
    root->right->right=newnode(7);
    printf("Press:\n1 for inorder\n2 for preorder\n3 for postorder\n0         toQUIT!");
    while(option)
    {
        printf("\nenter your option=");
        scanf("%d",&option);
        switch(option)
        {
            case 1:
                inorder_rec(root);
                break;
            case 2:
                preorder_rec(root);
                break;
            case 3:
                postorder_rec(root);
                break;
        /*  case 4:
                inorder_non_rec(root);
                break;
            case 5:
                preorder_non_rec(root);
                break;
            case 6:
                postorder_non_rec(root);
                break;*/

        }

    }
}
\$\endgroup\$
  • \$\begingroup\$ FYI, I replaced "binary search tree" -> "binary tree", because that's what this really is, and the difference is significant (see wikipedia to learn about binary search trees) \$\endgroup\$ – janos Mar 5 '16 at 14:57
4
\$\begingroup\$

C and C++ are different languages.

They have a common syntax in places. But how you use them is completely different. What you have written is C NOT C++.

C++ has its own set of header files for C functionality.

#include<stdio.h>
#include<stdlib.h>

Drop the ".h" and add a "c" prefix for the C++ version of these files.

#include<cstdio>
#include<cstdlib>

This puts all the functions in the namespace std.

Don't use using namespace std;

using namespace std;

Yes we know all tutorials and books do this. But they have a motive they are trying to save space on printed material. In any program larger than 10 lines this is going to cause a problem.

The reason the standard libraries are in the std namespace is so that it is not a huge burden to include the prefix in the name.

More details can be found here: Why is “using namespace std;” considered bad practice? and the best answer.

Use OO and classes

Sure OO is not perfect for everything. But a tree and its node is the perfect place to use OO concepts.

The may it is written is very C like and not C++ like. The constructor is not part of the class. There is no destructor to clean up memory there is no definition of ownership semantics so it is unclear who should be cleaning up memory and thus it is going to leak like a sieve.

struct node{
    int data;
    struct node *left;    // Don't need struct in C++
    struct node *right;   // unlike C structs don't have their own namespace.
};
///////////////////////////////
struct node *newnode(int value)
{
    // Abslutely never use C memory management functions in C++
    // The Heap and Free Store need not map to the same memory.
    // Also this does not invoke the constructure to initialize
    // the object.
    struct node *temp=(struct node *)malloc(sizeof(struct node));


    // Also you C code is broken.
    // malloc() can return `NULL` and you don't check for that.
    temp->data=value;
    temp->left=NULL;
    temp->right=NULL;
    return (temp);
}

This should look like this:

class Tree
{
     // Private class to store the nodes in the tree.
     struct Node
     {
         int   data;
         Node* left;
         Node* right;

         Node(int d) : data(d), left(nullptr), right(nullptr) {}
         Node(int d, Node* l, Node* r) : data(d), left(l), right(r) {}

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

     Node*  root;
     Tree()
         : root(nullptr)
     {}
     ~Tree()
     {
         delete root;
     }
     // Remove copy semantics (because I am lazy)
     // If you want add your own
     Tree(Tree const&)            = delete;
     Tree& operator=(Tree const&) = delete;

     void addData(int data) {
        // Ill leave you to implement this
     }
};

These should be a member of the Tree object (Note the Node)

void inorder_rec(struct node *temp)
void preorder_rec(struct node *temp)
void postorder_rec(struct node *temp)

Why are you using printf when you import iostream?

    printf("%d",temp->data);
    printf("%d",temp->data);

Your main just leaks memory. For every call to new there should be a call to delete. But in reality there should be zero calls to new. That should be done internal to the owning class and most objects should be automatic objects (construct on declaration and destruct when they go out of scope).

| improve this answer | |
\$\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.