A binary search tree can be used to sort a list. WE simply insert the list elements into a BST, initially empty, and then use an inorder traversal to copy them back into the list. Write an algorithm for this treesort method of sorting, assuming that the list is stored in

a. an array

any tips, suggestions, help is very much appreciated

Merci beau coup!

French or not, you're going to have to show us that you have tried. We are not going to do your assignment for you, but we'd be happy to teach you something along the way!

French or not, you're going to have to show us that you have tried. We are not going to do your assignment for you, but we'd be happy to teach you something along the way!

Sorry forgot to add my code

Here is my insert function and inorder traversal are these correct?
As in is it an efficient way to sort LinkedLists when passed through the insert and then the inorder?

``````//--- Definition of insert()
template <typename DataType>
inline void BST<DataType>::insert(const DataType & item)
{
BST<DataType>::BinNodePointer
locptr = myRoot,   // search pointer
parent = 0;        // pointer to parent of current node
bool found = false;     // indicates if item already in BST
while (!found && locptr != 0)
{
parent = locptr;
if (item < locptr->data)       // descend left
locptr = locptr->left;
else if (locptr->data < item)  // descend right
locptr = locptr->right;
else                           // item found
found = true;
}
if (!found)
{                                 // construct node containing item
locptr = new(nothrow) BST<DataType>::BinNode(item);
if (locptr == 0)
{
cerr << "*** Out of memory -- terminating program ***\n";
exit(1);
}

if (parent == 0)               // empty tree
myRoot = locptr;
else if (item < parent->data )  // insert to left of parent
parent->left = locptr;
else                           // insert to right of parent
parent->right = locptr;
}
else
cout << "Item already in the tree\n";
}``````

Here is my inorder traversal...

``````/--- Definition of inorder()
template <typename DataType>
inline void BST<DataType>::inorder(ostream & out) const
{
inorderAux(out, myRoot);
}

//--- Definition of inorderAux()
template <typename DataType>
void BST<DataType>::inorderAux(ostream & out,
BinNodePointer subtreeRoot) const
{
if (subtreeRoot != 0)
{
inorderAux(out, subtreeRoot->left);    // L operation
out << subtreeRoot->data << "  ";      // V operation
inorderAux(out, subtreeRoot->right);   // R operation
}
}``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.