Probably a pointer problem

Just messing around and refreshing on C++ and I happen to run into a little problem.

Code:

---


template <class T> class TraverseTree{
        public:
                TraverseTree();
                ~TraverseTree();
 
                static void preOrder(Node<T>*,Tree<T>*);
                static void postOrder(Node<T>*,Tree<T>*);
                static void inOrder(Node<T>*,Tree<T>*);
};

template <class T> void TraverseTree<T>::preOrder(Node<T>* l,Tree<T>* d){
        if(d!=NULL){
                l->v = d->v;
                l->next = new Node<T>;
                std::cout << l->v << std::endl;
                l = l->next;
                l->next = NULL;
                preOrder(l,d->left);
                preOrder(l,d->right);
        }
}

---

The cout line prints out the correct stuff and works great. However I wanted to use the variable that I passed in to the function to print out the answers. When I do I get some of the right numbers but not in the right order and the others are from some random memory. Is my logic here wrong?

The first problem I had was that I lost the root while it generated the list so I made a temporary root node and passed that in for the list to be generated. Now I'm not too sure what the problem is.

A traversal does not usually create new nodes. Your logic seems strange. Why do you have a tree ptr AND a node ptr?
EDIT: Sorry, I see. You're making a linked list out of the tree.

I'm thinking it might be something here that is the problem. Depending on the way I initialize stuff I am getting different results and I'm not sure why. I simply hardcoded a tree to test it.

Code:

---

          11
        /    \
      9      15
    /  \    /  \
          7  13
        / \ / \

---

Code:

---

int main(int argc, char* argv[]){

                Tree<int>* my_tree = new Tree<int>;
                Node<int>* my_list = new Node<int>;
                Tree<int>* tt = my_tree;
                Node<int>* tl = my_list;

                my_tree->v = 11;

                my_tree->left = new Tree<int>;
                my_tree->left->v = 9;
                my_tree->left->left = NULL;
                my_tree->left->right = new Tree<int>;
                my_tree->left->right->v = 7;
                my_tree->left->right->left = NULL;
                my_tree->left->right->right = NULL;
               
                my_tree->right = new Tree<int>;
                my_tree->right->v = 15;
                my_tree->right->right = NULL;
                my_tree->right->left = new Tree<int>;
                my_tree->right->left->v = 13;
                my_tree->right->left->left = NULL;
                my_tree->right->left->right = NULL;

               
                TraverseTree<int>::preOrder(tl,tt);
                for(tl = my_list; tl != NULL; tl = tl->next){
                        std::cout << tl->v << std::endl;
                }

                return 0;
}

---

The problem is with the way you're passing your list pointers around. It would be simpler to use a std::list instead and pass it as a reference. Here's an example:

Code:

---

#include <iostream>
#include <list>

typedef std::list<int>        LIST;
typedef LIST::const_iterator  LIST_cit;

struct Tree {
    int v;
    Tree *left, *right;
    Tree(int v_) : v(v_), left(0), right(0) { }
};

void traverse(Tree* d, LIST& lst) {
    if (d) {
        lst.push_back(d->v);
        traverse(d->left, lst);
        traverse(d->right, lst);
    }
}

int main() {
    Tree t(5);
    t.left = new Tree(3);
    t.right = new Tree(7);
    t.left->right = new Tree(4);
    t.right->left = new Tree(6);

    LIST lst;
    traverse(&t, lst);
   
    for (LIST_cit i = lst.begin(); i != lst.end(); ++i)
        std::cout << *i << "\n";
}

---

I don't care so much about getting it to work as understanding why it doesn't work. What exactly is wrong about it? I don't see it.

Two things that I can see:

1. You will have an extra node at the end of your list since in preOrder you make a new "next" node before you recurse, but the recursion may hit a null pointer so the list element will not be needed.

2. Both preOrder recursive calls are made with the same l, so they'll add list elements at the same place instead of at the end of the list.