Binary Tree Sort

[whathecode]

Hello everyone,

I have followed the Wikipedia Binary Tree Sort algorithm to solve it and this is what I came up with.

Issue:
The issue is that in main I do not know how to implement and execute my code.
I am not sure if all my functions are correct.

Question:
How can I convert my void functions to int?

  class Tree
{
public:
	int value;
	Tree* left;
	Tree* right;


void insert(Tree* root, int newValue)
{
	if(root== NULL)
	{
		root = new Tree;
		root-> value = newValue;
		root -> left = NULL;
		root -> right = NULL;
		return;
	}
	else if(newValue < root->value)
	{
		insert(root->left,newValue);
	}
	else
		insert(root->right,newValue);
}

void printInOrder(Tree* node)
{
	if(node = NULL)
		return;
	else
	{
		printInOrder(node->left);
		cout<<node;
		printInOrder(node->right);
	}
}
void TreeSort (int list[], int N)
{
	Tree* root;
	root= NULL;

	for (int i=0; i<N; i++)
	{
		insert(root, list[i]);
	}
	printInOrder(root);

}
};

int main()
{
	Tree bst;
	int* list = new int[];
	int numArray;
	cout<<"Enter num to be inserted in array\n";
	cin>>numArray;
	bst.TreeSort(list, numArray);

	return 0;
}

Any help is greatly appreciated.

[coder777]

Change the main code like so:

int main()
{
	Tree bst;
	int* list = new int[];
	int numArray;
	cout<<"Enter num to be inserted in array\n";
	cin>>numArray;
	int* list = new int[numArray];
	cout<<"Enter numbers:n";
for(int i = 0; i < numArray; ++i)
{
	cin>>list[i];
}
	bst.TreeSort(list, numArray);

	return 0;
}

How can I convert my void functions to int?

Why?

[dhayden]

Your insert code won't work because it passes root by value. You change root within insert, but once you return, the value is lost. So insert should be declared
void insert(Tree* &root, int newValue)

Here the root pointer is passed by reference, so when you change it, you change the parameter that was passed in.

Treesort leaks memory because it contains the root of the tree as a local variable.

An easy easy way to deal with the leak, and to make a lot of other code easier, is to create separate classes for the tree itself, and the nodes within it. Something like:

class Node {
public:
    int value;
    Node *left, *right;
    // etc.
};

class Tree {
public:
    bool insert(int value);
    void treeSort(int *list, size);
    void clear();
    void printInOrder();
private:
    Node *root;
};

[whathecode]

Thank you coder777 and dhayden for your suggestions.
@ coder777 - I was trying to trouble shoot and was wondering if I messed up the implementation of my functions, but I made the suggested changes and kept void. Also I uderstood your implementation, thank you, it helped.

@dhayden - I made some changes in my code and tried to fix the memory leek this way,I believe it might have worked because my code stopped crashing but now I am getting the following errors:

Error
- error LNK2019: unresolved external symbol "public: void __thiscall Tree::TreeSort(int * const,int)" (?TreeSort@Tree@@QAEXQAHH@Z) referenced in function _main
- fatal error LNK1120: 1 unresolved externals

I have done some research where the suggestions were to change some settings, as this did not happen in any other code before I still think that there might be something with my code and with The TreeSort function in particular. What do you think?

class Tree
{
private:
	Tree* root;
public:
	int value;
	Tree* left;
	Tree* right;
	
	void insert(Tree* &root, int newValue);
	void printInOrder(Tree* node);
	void TreeSort (int list[], int N);
};

void insert(Tree* &root, int newValue)
{
	if(root== NULL)
	{
		root = new Tree;
		root-> value = newValue;
		root -> left = NULL;
		root -> right = NULL;
		return;
	}
	else if(newValue < root->value)
	{
		insert(root->left,newValue);
	}
	else
		insert(root->right,newValue);
}

void printInOrder(Tree* node)
{
	if(node = NULL)
		return;
	else
	{
		printInOrder(node->left);
		cout<<node->value;
		printInOrder(node->right);
	}
}
void TreeSort (int list[], int N)
{
	Tree* root;
	root= NULL;

	for (int i=0; i<N; i++)
	{
		insert(root, list[i]);
	}
	printInOrder(root);

}


int main(int argc, char** argv[])
{
	Tree bst;
	int numArray;
	cout<<"Enter num to be inserted in array\n";
	cin>>numArray;
	int* list = new int[numArray];
	cout<<"Enter numbers:\n";
		for(int i=0; i>numArray; i++)
		{
			cin>>list[i];
		}
	bst.TreeSort(list, numArray);
	system("pause");
	return 0;
}

[dhayden]

Now you have declared methods Tree::insert, Tree::printInOrder() and Tree::TreeSort(). You have also defined global functions by the same names (insert, printInOrder and TreeSort) but these are different from the methods you declared. That's why you're getting an error.

Also, now every node in the tree has a root pointer. Ick. Take my advice and use two separate classes. Here it is with some of the code already written. Add your code to the parts that say "insert code here"

#include <iostream>

using std::cout;
using std::cin;

class Tree
{
private:
    class Node {
    public:
	Node(int v) : 
	    value(v),
	    left(NULL),
	    right(NULL)
	{}
	~Node();
	void insert(Node *newNode);
	void printInOrder();
	int value;
	Node *left, *right;
    };
    Node * root;

public:
    Tree() : root(NULL) {}
    ~Tree() { clear(); }
    void clear() { delete root; root = NULL; }
    void insert(int newValue);
    void printInOrder();
    void TreeSort(int list[], int N);
    
};

void
Tree::insert(int newValue)
{
    Node *newNode = new Node(newValue);
    if (root) {
	root->insert(newNode);
    } else {
	root = newNode;
    }
}

void
Tree::Node::insert(Node *newNode)
{
  // insert code here
}

void
Tree::printInOrder()
{
    if (root) {
	root->printInOrder();
    } else {
	cout << "Tree is empty\n";
    }
}

void
Tree::Node::printInOrder()
{
   // insert code here
}

Tree::Node::~Node()
{
    // Note that it's okay to delete a NULL pointer so no need to check
    // them in the code
    delete left;
    delete right;
}


void
Tree::TreeSort(int list[], int N)
{
    clear();

    for (int i = 0; i < N; i++) {
	insert(list[i]);
    }
    printInOrder();
}

int
main(int argc, char **argv[])
{
    Tree bst;
    int numArray;
    cout << "Enter num to be inserted in array\n";
    cin >> numArray;
    int *list = new int[numArray];
    cout << "Enter numbers:\n";
    for (int i = 0; i < numArray; i++) {
	cin >> list[i];
    }
    bst.TreeSort(list, numArray);
    system("pause");
    return 0;
}