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;
}

CodePudding user response：

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...

CodePudding user response：

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.