Thread: Probably a pointer problem

  1. #1
    Registered User
    Join Date
    Feb 2006
    Posts
    71

    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.

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    Last edited by oogabooga; 01-09-2012 at 07:31 PM.

  3. #3
    Registered User
    Join Date
    Feb 2006
    Posts
    71
    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;
    }

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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";
    }

  5. #5
    Registered User
    Join Date
    Feb 2006
    Posts
    71
    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.

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with pointer to a pointer variable
    By Rodri in forum C Programming
    Replies: 2
    Last Post: 11-20-2011, 10:50 AM
  2. pointer to pointer realloc problem
    By prakash0104 in forum C Programming
    Replies: 14
    Last Post: 04-06-2009, 08:53 PM
  3. sturct/pointer problem, and fscanf problem
    By hiphop4reel in forum C Programming
    Replies: 6
    Last Post: 07-28-2008, 09:40 AM
  4. Replies: 4
    Last Post: 11-05-2006, 02:57 PM
  5. pointer to pointer how do i solve following problem?
    By kobra_swe in forum C Programming
    Replies: 5
    Last Post: 07-19-2006, 04:49 PM