A Question About inserting node in a regular Binary Tree
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: A Question About inserting node in a regular Binary Tree

  1. #1
    Join Date
    Dec 2010
    Posts
    32

    Unhappy A Question About inserting node in a regular Binary Tree

    Hi All,

    I was trying to edit a code so that it could insert nodes into a binary tree. Every time the user inserts, there will prompt a line asking to insert to the left child or the right child. Could anyone show me what's wrong with my code(you can see to the insert func)? It doesn't yield the correct result.

    Thanks in advance.


    #include<iostream>
    //#include<stdio>
    // #include<stdlib>
    using std::cin;
    using std::cout;
    using std::endl;
    struct node
    {
    int data;
    node *left;
    node *right;
    };

    node *tree=NULL;
    node *insert(node *tree,int ele);

    void preorder(node *tree);
    void inorder(node *tree);
    void postorder(node *tree);
    int count=1;

    int main()
    {
    //clrscr();
    int ch,ele;
    do
    {
    //clrscr();
    cout<<"\n\t\a\a1----INSERT A NODE IN A BINARY TREE.\a\a";
    cout<<"\n\t\a\a2----PRE-ORDER TRAVERSAL.\a\a";
    cout<<"\n\t\a\a3----IN-ORDER TRAVERSAL.\a\a";
    cout<<"\n\t\a\a4----POST-ORDER TRAVERSAL.\a\a";
    cout<<"\n\t\a\a5----EXIT.\a\a";
    cout<<"\n\t\a\aENTER CHOICE::\a\a";
    cin>>ch;
    switch(ch)
    {
    case 1:
    cout<<"\n\t\a\aENTER THE ELEMENT::\a\a";
    cin>>ele;
    tree=insert(tree,ele);
    break;

    case 2:
    cout<<"\n\t\a\a****PRE-ORDER TRAVERSAL OF A TREE****\a\a";
    preorder(tree);
    break;

    case 3:
    cout<<"\n\t\a\a****IN-ORDER TRAVERSAL OF A TREE****\a\a";
    inorder(tree);
    break;

    case 4:
    cout<<"\n\t\a\a****POST-ORDER TRAVERSAL OF A TREE****\a\a";
    postorder(tree);
    break;

    case 5:
    break;
    }
    }while(ch!=5);
    return 0;
    }

    node *insert(node *tree,int ele)
    {
    char ch;
    if(tree==NULL)
    {
    tree=new node;
    tree->left=NULL;
    tree->right=NULL;
    tree->data=ele;
    count++;

    }
    else{
    cout<<"Insert to Left or Right?"<<endl;
    cin>>ch;
    if(ch=='L'||'l')
    tree->left=insert(tree->left,ele);
    if(ch=='R'||'r')
    tree->right=insert(tree->right,ele);
    }
    return(tree);
    }

    void preorder(node *tree)
    {
    if(tree!=NULL)
    {
    cout<<tree->data;
    preorder(tree->left);
    preorder(tree->right);
    //cin.get();
    }
    }

    void inorder(node *tree)
    {
    if(tree!=NULL)
    {
    inorder(tree->left);
    cout<<tree->data;
    inorder(tree->right);
    //cin.get();
    }
    }

    void postorder(node *tree)
    {
    if(tree!=NULL)
    {
    postorder(tree->left);
    postorder(tree->right);
    cout<<tree->data;
    //cin.get();
    }
    }

  2. #2
    Join Date
    Dec 2010
    Posts
    19

    Re: A Question About inserting node in a regular Binary Tree

    In the Insert function change the conditional expression to

    if (ch == 'L' || ch == 'l')
    and
    if (ch == 'R' || ch == 'r')

  3. #3
    Join Date
    Oct 2009
    Posts
    577

    Smile Re: A Question About inserting node in a regular Binary Tree

    You better put your code between [ c o d e ] [ / c o d e] tags (no spaces) so that you don't loose indentation.

    Code:
    #include<iostream>
    //#include<stdio>
    // #include<stdlib>
    using std::cin;
    using std::cout;
    using std::endl;
    struct node
    {
        int data;
        node *left;
        node *right;
    };
    
    node *tree=NULL;
    node *insert(node *tree,int ele);
    
    void preorder(node *tree);
    void inorder(node *tree);
    void postorder(node *tree);
    int count=1;
    
    int main()
    {
        //clrscr();
        int ch,ele;
        do
        {
            //clrscr();
            cout<<"\n\t\a\a1----INSERT A NODE IN A BINARY TREE.\a\a";
            cout<<"\n\t\a\a2----PRE-ORDER TRAVERSAL.\a\a";
            cout<<"\n\t\a\a3----IN-ORDER TRAVERSAL.\a\a";
            cout<<"\n\t\a\a4----POST-ORDER TRAVERSAL.\a\a";
            cout<<"\n\t\a\a5----EXIT.\a\a";
            cout<<"\n\t\a\aENTER CHOICE::\a\a";
            cin>>ch;
            switch(ch)
            {
            case 1:
                cout<<"\n\t\a\aENTER THE ELEMENT::\a\a";
                cin>>ele;
                tree=insert(tree,ele);
                break;
                
            case 2:
                cout<<"\n\t\a\a****PRE-ORDER TRAVERSAL OF A TREE****\a\a";
                preorder(tree);
                break;
                
            case 3:
                cout<<"\n\t\a\a****IN-ORDER TRAVERSAL OF A TREE****\a\a";
                inorder(tree);
                break;
                
            case 4:
                cout<<"\n\t\a\a****POST-ORDER TRAVERSAL OF A TREE****\a\a";
                postorder(tree);
                break;
                
            case 5:
                break;
            }
        }while(ch!=5);
        return 0;
    }
    
    node *insert(node *tree,int ele)
    {
        char ch;
        if(tree==NULL)
        {
            tree=new node;
            tree->left=NULL;
            tree->right=NULL;
            tree->data=ele;
            count++;
            
        }
        else{
            cout<<"Insert to Left or Right?"<<endl;
            cin>>ch;
            if(ch=='L'|| ch=='l')
                tree->left=insert(tree->left,ele);
            if(ch=='R'|| ch=='r')
                tree->right=insert(tree->right,ele);
        }
        return(tree);
    }
    
    void preorder(node *tree)
    {
        if(tree!=NULL)
        {
            cout<<tree->data;
            preorder(tree->left);
            preorder(tree->right);
            //cin.get();
        }
    }
    
    void inorder(node *tree)
    {
        if(tree!=NULL)
        {
            inorder(tree->left);
            cout<<tree->data;
            inorder(tree->right);
            //cin.get();
        }
    }
    
    void postorder(node *tree)
    {
        if(tree!=NULL)
        {
            postorder(tree->left);
            postorder(tree->right);
            cout<<tree->data;
            //cin.get();
        }
    }
    I wouldn't ask the user in the insert function whether to go left or right. Instead, I would check the input value whether it is greater or less than the value of the current node and then go down accordingly.

    You also should avoid statements like

    Code:
    tree=insert(tree,ele);
    cause that could destroy the (only) root pointer you have in your main function. You are lucky that your insert function doesn't change the tree argument so that the statement doesn't any harm and even helps you to initialize the tree pointer at first call.

    The correct way with your current tree implementation would be

    Code:
    Node * pNode = insert(tree, ele);
    if (tree == NULL)
         tree = pNode;
    Though that may look a little clumsy, it avoids to make assumptions on a function 'insert' where the 'normal' return would be the new Node inserted and not the Node passed as argument.

    A probably better approach is to change the argument type of the tree argument to Node*&. That way the tree was 'returned' correctly when it was initialized and used for input only for the normal case where the tree already exists.

    The code in the main would change to:

    Code:
       insert(tree, ele);
    All the problems with passing Nodes to the public interface of your tree you could avoid by adding a Tree class which holds the root pointer as a private member:

    Code:
    class Tree
    {
         Node * root;
         node * insert(node *& tree,int ele);
         void preorder(node * tree);
         void inorder(node * tree);
         void postorder(node * tree);
    public:
         Tree() : root(NULL) {}
         void insert(int ele);
         void preorder();
         void inorder();
         void postorder();
    };
    In main you only create an empty Tree and call the public functions while those were calling the private functions using the private root pointer.

  4. #4
    Join Date
    Dec 2010
    Posts
    32

    Re: A Question About inserting node in a regular Binary Tree

    Thanks a lot itsmeandnobodyelse, you are of great help!

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center