0
\$\begingroup\$

This is code for Inorder, Preorder, Postorder Traversal of a Tree. Suggest some ways to improve it (since I have made root public and want to make it Private).

#include<iostream.h>
#include<conio.h>

struct Node
{
  int data;
  Node *left;
  Node *right;
};


class Tree
{
  private:
    Node *p;
  public:
    Node *root;
    Tree()
    {
      root=NULL;
    }
    void Insertion();
    void Traversal();
  protected:
    void SearchPos(Node *);
    void Inorder_Traversal(Node *);
    void Preorder_Traversal(Node *);
    void Postorder_Traversal(Node *);
};

void Tree::Insertion()
{
  p=new Node;
  p->left=p->right=NULL;
  if(root==NULL)
  {
    cout<<"Enter Root Value to be inserted:";
    cin>>p->data;
    root=p;
  }
  else
  {
    cout<<"\nEnter Value to be inserted:";
    cin>>p->data;
    SearchPos(root);
  }
}

void Tree::SearchPos(Node *tmp)
{
  if(p->data<tmp->data && tmp->left==NULL)
  {
    tmp->left=p;
    return;
  }
  else if(p->data>tmp->data && tmp->right==NULL)
  {
    tmp->right=p;
    return;
  }
  else if(p->data<tmp->data && tmp->left!=NULL)
  {
    SearchPos(tmp->left);
  }
  else if(p->data>tmp->data && tmp->right!=NULL)
  {
    SearchPos(tmp->right);
  }
}

void Tree::Traversal()
{
  cout<<"\nInorder Traversal:";
  Inorder_Traversal(root);
  cout<<"\nPreorder Traversal:";
  Preorder_Traversal(root);
  cout<<"\nPostorder Traversal:";
  Postorder_Traversal(root);
}

void Tree::Inorder_Traversal(Node *tmp)
{
  if(tmp->left==NULL && tmp->right==NULL)
  {
    cout<<tmp->data<<" ";
    return;
  }
  else if(tmp->left!=NULL)
  {
    Inorder_Traversal(tmp->left);
  }
  cout<<tmp->data<<" ";
  if(tmp->right!=NULL)
  {
    Inorder_Traversal(tmp->right);
  }
}

void Tree::Preorder_Traversal(Node *tmp)
{
  if(tmp->left==NULL && tmp->right==NULL)
  {
    cout<<tmp->data<<" ";
    return;
  }
  else if(tmp->left!=NULL)
  {
    cout<<tmp->data<<" ";
    Preorder_Traversal(tmp->left);
  }
  if(tmp->right!=NULL)
  {
    Preorder_Traversal(tmp->right);
  }
}

void Tree::Postorder_Traversal(Node *tmp)
{
  if(tmp->left==NULL && tmp->right==NULL)
  {
    cout<<tmp->data<<" ";
    return;
  }
  else if(tmp->left!=NULL)
  {
    Postorder_Traversal(tmp->left);
  }
  if(tmp->right!=NULL)
  {
    Postorder_Traversal(tmp->right);
    cout<<tmp->data<<" ";
  }
}

void main()
{
  clrscr();
  char choice;
  Tree t;
  do
  {
    t.Insertion();
    cout<<"\nMore to Insert???Enter(y/n):";
    cin>>choice;
  }while(choice=='y'||choice=='Y');
  t.Traversal();
  getch();
}
\$\endgroup\$
  • \$\begingroup\$ Please don't use conio.h. It's not supported in most modern compilers. \$\endgroup\$ – coderodde Jan 15 '18 at 16:34
  • \$\begingroup\$ It seems like code doesn't work in some cases. I'm not sure in which, but it would be great to fix them before posting. Also, please use VC++ or minGW64 on windows, or g++ or clang on linux. If you're on mac, clang will come packed with XCode. The compiler you're using is quite outdated, and extremely few people have access to it (I fixed those part in the link above). Voting to close. \$\endgroup\$ – Incomputable Jan 17 '18 at 9:56
1
\$\begingroup\$

Recursion

  1. Test if the current node is valid (return if it is not).
  2. Processes node or Recurse

All your functions can be written much more succinctly and easier to read if you follow those rules.

void Tree::preorderTraversal(Node *tmp)
{
    // Always check to see if the node is valid first.
    if (tmp == nullptr) {
        return;
    }

    //processes your data (this could come after recursion or between the calls depending on the type of the traversal needed).
    std::cout << tmp->data << " ";

    // Recursion.
    preorderTraversal(tmp->left);   // Don't care if these are null
    preorderTraversal(tmp->right);  // This will be checked at the beginning of the next call.
}

Code Review

Make this part of Tree class (ie declare this as a private member of Tree). There is no reason for anbody outside the tree to know or use this class.

struct Node
{
  int data;
  Node *left;
  Node *right;
};

Why is root public?

  public:
    Node *root;

This breaks encapsulation and allows a non member to mutate the state of the class without the class knowing or understanding about the mutation.

    Tree()
    {
      root=NULL;
    }

Your Tree class does not obey the rule of Three or Five. This needs to be fixed immediately. Currently it does not break much because you have missed the destructor but it will lead to unexpected results when you copy and mutate the tree.

Also because you don't have a destructor you are leaking memory. You basically need to add the following methods to your Tree class.

     ~Tree();
     Tree(Tree const& rhs);
     Tree& operator=(Tree const& rhs);

You should avoid protected. Though it has its uses these are mostly advanced reasons to use protected. Stick to private and public.

  protected:

Note: As all these expose Node these should be private members. Your interface to the public should not expose internal types and Node is an internal type that affects the implementation.

    void SearchPos(Node *);
    void Inorder_Traversal(Node *);
    void Preorder_Traversal(Node *);
    void Postorder_Traversal(Node *);
};

You can initialize objects created with new.

  p=new Node;
  p->left=p->right=NULL;

  // Like this:
  p = new Node{0, nullptr, nullpre};

In 2011 ( 6 years ago) we introduced nullptr to replace the nasty C macro NULL. Please use nullptr.

  if(root==NULL)

Also a bit of horizontal space makes your code less clustered and nicer to read.

 if (root == nullptr) {
 }

Better Insertion

public:
    void Tree::insert(int data)
    {
        root = insertData(root, data);
    }
private:
    Node* Tree::insertData(Node* current, int data)
    {
        if current == nullptr) {
            return new Node{data, nullptr, nullptr};
        }
        if (date <= current->data) {
            current->left  = insertData(current->left,  data);
        }
        else {
            current->right = insertData(current->right, data);
        }
        return current;
    }
\$\endgroup\$

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