0

I'm trying to create a program to work with binary search trees and my instructor has this function set up with this declaration, which must stay the same.

void BSTType<T>::traverse(std::ostream& out, TravType trav) const{

this is currently how i have it implemented, but what is the std::ostream& out used for and how do i use this is my main program? I don't understand why we need this as a parameter and not the current tree I am working with. please help soon. this is due at 8pm and my instructor won't help. if more info is needed just let me know in comments or something.

template <class T>
void BSTType<T>::traverse(std::ostream& out, TravType trav) const{
    if(trav==IN)
        inorder(root);
    else if(trav=PRE)
        preorder(root);
    else
        postorder(root);
}

this is the idea i have for calling this function from my main program

tree.traverse(???, IN);

this should output the tree using inorder traversal by calling the inorder(root) function. I don't understand what goes where the question marks are

here are my functions that traverse can call, depending on what travType the user enters

void BSTType<T>::inorder(BTNodeType<T>* node) const{
    if (node!= NULL){
        inorder(node->left);
        std::cout << node->item << " ";
        inorder(node->right);
    }
}

template <class T>
void BSTType<T>::postorder(BTNodeType<T>* node) const{
    if (node!= NULL){
        postorder(node->left);
        postorder(node->right);
        std::cout << node->item << " ";
    }
}

template <class T>
void BSTType<T>::preorder(BTNodeType<T>* node) const{
    if(node!=NULL){
        std::cout << node->item<< " ";
        preorder(node-> left);
        preorder(node-> right);
    }
}

edit: for some reason this function isn't copying my tree correctly, anyone know why?

template <class T>
void BSTType<T>::copy(BTNodeType<T>*& node1, BTNodeType<T>* node2){
    if(node2==NULL)
        node1=NULL;
    else{
        node1=new BTNodeType<T>;
        node1->item=node2->item;
        copy(node1->left, node2->left);
        copy(node1->right, node2->right);
    }
}
user3587098
  • 1
  • 3

2 Answers2

2

tree.traverse(???, IN); I don't understand what goes where the question marks are.

You could just put:

??? = std::cout

If you want to print at the standard output (i.e., it needs an output stream).

Also it's recommended to pass the output stream as input argument to the member functions you posted, that is your member functions will become:

 void BSTType<T>::inorder(BTNodeType<T>* node, std::ostream& out) const{
    if (node!= 0){
        inorder(node->left);
        out << node->item << " ";
        inorder(node->right);
    }
}

template <class T>
void BSTType<T>::postorder(BTNodeType<T>* node, std::ostream& out) const{
    if (node!= 0){
        postorder(node->left);
        postorder(node->right);
        out << node->item << " ";
    }
}

template <class T>
void BSTType<T>::preorder(BTNodeType<T>* node, std::ostream& out) const{
    if(node!=0){
        out << node->item<< " ";
        preorder(node-> left);
        preorder(node-> right);
    }
}

Then traverse will become:

template <class T>
void BSTType<T>::traverse(std::ostream& out, TravType trav) const{
    if(trav==IN)
        inorder(root, out);
    else if(trav=PRE)
        preorder(root, out);
    else
        postorder(root, out);
}
101010
  • 41,839
  • 11
  • 94
  • 168
0
std::ostream& out

is the output stream, used to append the different node information when visited, in order to be able to print the whole tree in the order it was visited.

The algorithm should be something like this: out << node.getValue(). This would append the current value to the output string. According to each algorithm, the order of the calls will change, but they will all result in a different order of this 3 actions: append the node's information, then call left or right child.

inorder(root); should be replaced by inorder(out, root);

Inside inorder it should have: out << root.getValue() to append the value

Add: using namespace std; so you can call tree.traverse(cout, IN); to use the standard output

Troveldom
  • 356
  • 1
  • 10
  • I've never used c++, but this may help -> http://stackoverflow.com/questions/15106102/how-to-use-c-stdostream-with-printf-like-formatting – Troveldom Apr 29 '14 at 22:04
  • I know that that is the output stream, but how do i use it in this situation? – user3587098 Apr 29 '14 at 22:09
  • It should be something like this: out << node.getValue(). This would append the current value to the output string. According to each algorithm, the order of the calls will change, but they will all result in a different order of this 3 actions: append the node's information, then call left or right child. – Troveldom Apr 29 '14 at 22:11
  • it wont let me comment on this the way i want to so check my edits in my post. i added my functions 'inorder' 'preorder' and 'postorder' – user3587098 Apr 29 '14 at 22:15
  • inorder(root); should be replaced by inorder(out, root); and inside inorder it should have: out << root.getValue() to append the value – Troveldom Apr 29 '14 at 22:19
  • and if you add: using namespace std; you can call tree.traverse(cout, IN); where cout is the standard output – Troveldom Apr 29 '14 at 22:21
  • ok, but after i change that, how do i call this in my main program – user3587098 Apr 29 '14 at 22:21
  • 1
    ok, sorry! thanks for all your help, I'm retarded. I figured it out, in the main program you just say tree.traverse(cout, IN); like 40two said! – user3587098 Apr 29 '14 at 22:33
  • can you look at my copy function please? – user3587098 Apr 29 '14 at 22:57