0

I'm trying to write class for binary tree in c++ but I think in inserting function I have some problem it doesnt work correctly I'm begginer in c++ and I can't find the problem. I should write this code without using "struct" it should Compeletly write with classes I'm so sorry beacuse my code doesn't have any comment and also sorry for bad English Thank you very much

#include<iostream>

using namespace std;

///////////////////////////////////////////////////////////////////////////
class Tree
{
public:

    Tree* left;
    Tree* right;
    string info;

    Tree()
    {
        this->left=NULL;
        this->right=NULL;
        this->info="";
    }
    Tree(string info)
    {
        this->left=NULL;
        this->right=NULL;
        this->info=info;
    }    
    Tree(string info,Tree* left,Tree* right)
    {
        this->left=left;
        this->right=right;
        this->info=info;
    }
};
/////////////////////////////////////////////////////////////////////
class LinkedList
{
    public:
    
        Tree* root;

        LinkedList()
        {
            root=NULL;
        }

        void mainInsert(Tree* newroot , string info)
        {
            if(newroot==NULL)
            {
                Tree* newNode = new Tree(info);
                newroot=newNode;
                return;
            }
            if(info.compare(newroot->info)==-1)
            {
                mainInsert(newroot->left,info);
            }
            else
            {
                mainInsert(newroot->right,info);
            }

        }

        void mainPrintTree(Tree* newroot)
        {
            if(newroot==NULL)
            {
                return;
            }
            cout<<newroot->info<<endl;
            mainPrintTree(newroot->left);
            mainPrintTree(newroot->right);
        }

        void insert(string info)
        {
            mainInsert(this->root , info);
        }

        void printTree()
        {
            mainPrintTree(this->root);
        }

};

///////////////////////////////////////////////////////////////////////////

int main()
{

    LinkedList myTree;

    myTree.insert("2");
    myTree.insert("1");
    myTree.insert("3");
    myTree.insert("7");
    myTree.insert("0");

    myTree.printTree();
  
    return 0;
}
mehdi
  • 1
  • 1
  • 3
    The only difference between `struct` and `class` is the default access specifier is `public` for the former and `private` for the latter, otherwise they are completely identical. In any case it's not clear what your question is other than your code seems to not be working? – Cory Kramer Oct 27 '21 at 12:12
  • 3
    Why are your nodes called "Tree" and your trees called "LinkedList"? That sounds like you're only going to confuse yourself. – molbdnilo Oct 27 '21 at 12:13
  • Welcome to Stack Overflow. Please read [the help pages](http://stackoverflow.com/help), take the SO [tour], read [ask], as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). Lastly please learn how to create a [mre]. – Some programmer dude Oct 27 '21 at 12:14
  • 1
    Assigning to a function's (non-reference) argument has no effect outside that function. There is nothing special about pointers. – molbdnilo Oct 27 '21 at 12:14
  • You're on the right track. Take a pencil and a piece of paper and possibly use your debugger have a close look at `mainInsert`. If you don't kn ow how to use your debugger it's a great opportunity to learn it now. Knowing even the basis of your debugger will save you countless hours in the future. BTW: recursion is not neccessary for `mainInsert`, an iterative approach is probably simpler. – Jabberwocky Oct 27 '21 at 12:17

2 Answers2

1

Your mainInsert is wrong: after mainInsert(newroot->left,info);, newroot->left is not modified because that argument is passed by value (BTW read this SO article article, it's about C, not C++ but the concept is the same).

The simplest here is just to pass the node by reference, which makes your code even simpler:

  void mainInsert(Tree* &subTree, string info)
  {
    if (subTree == NULL)
    {
      subTree = new Tree(info);
      return;
    }
    if (info.compare(subTree->info) == -1)
    {
      mainInsert(subTree->left, info);
    }
    else
    {
      mainInsert(subTree->right, info);
    }
  }

I renamed the newroot parameter into subTree, because there is actually only one root per tree and every node of the tree is actually a also tree.

BTW: your question about writing this code without using struct is pointless, you don't use struct at all in your code.

Hint: try to write an iterative version of mainInsert. It's pretty simple and straightforward as the problem is not inherently recursive.

Jabberwocky
  • 48,281
  • 17
  • 65
  • 115
1

Here is a (the?) culprit:

void mainInsert(Tree* newroot, string info)
{
    if (newroot == NULL)
    {
        Tree* newNode = new Tree(info);
        newroot = newNode;     // Oops, only changing a local pointer here!
        return;
    }
...

It is a common error of beginners: you passed a pointer to a function, change that pointer and wonder why the original pointer is still unchanged... The reason is that apart from being able to change its pointee value, a pointer is a mere variable. So the function has its local copy of the pointer, and changing it has no effect in the caller. Here a simple way is probably to return the new root:

Tree* mainInsert(Tree* newroot, string info)
{
    if (newroot == NULL)
    {
        Tree* newNode = new Tree(info);
        return newNode;
    }
    // remember to return newroot in other branches...

Just use that in insert:

    void insert(string info)
    {
        this->root = mainInsert(this->root , info);
    }

But there are tons of possible improvements here, like separating the public interface from the private implementation, so I would advise you to post your code on Code Review as soon as is will work without errors...

Serge Ballesta
  • 143,923
  • 11
  • 122
  • 252