Thread: Returning a node

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    94

    Returning a node

    I want to save the data found within my tree but I am not sure how to do this. I was thinking that my printInOrder() function could be changed to be generic and return the data to the calling function which is from another class. Can anyone help?

    Code:
    template <class T>
    struct AVLnode
    {
    	friend class AVLtree<T>;
    
    	T info;
    	int balance;
    	AVLnode<T> *right;
    	AVLnode<T> *left;
    
    	AVLnode () {right = left = NULL;}
    };
    Code:
    template <class T>
    class AVLtree
    { 
    	public:
    		AVLnode<T> *tree;
    		AVLtree () {tree=NULL; fail=false; srchResult=0;};
    		~AVLtree () {clear(tree);};
    		void insertData (const T &data);
    		void printAVLtree () {printInOrder(tree);};
    		T searchTree (T& data) {return (srchTreeHelper(tree, data));};
    
    	protected:
    
    		void insertHelper (AVLnode<T> *&root, AVLnode<T> *node, bool &higher, T data);
    		void rightBalance (AVLnode<T> *&root, bool &higher);
    		void leftBalance (AVLnode<T> *&root, bool &higher);
    		AVLnode<T>* rotateRight (AVLnode<T> *root);
    		AVLnode<T>* rotateLeft (AVLnode<T> *root);
    
    		void clear (AVLnode<T> *tree);
    		void printInOrder (AVLnode<T> *root);
    		T srchTreeHelper (AVLnode<T> *treeRoot, T& data);
    };
    Code:
    template <class T>
    void AVLtree<T>::printInOrder (AVLnode<T> *root)
    {    
    
    	if (root)
    	{
    
    		printInOrder (root->left);
    		cout <<root->info.key; <-- Not Generic
    		cout <<root->info.ID;   <-- Not Generic
    		cout <<root->info.txt;  <-- Not Generic
    		printInOrder (root->right);
    	}
    
    }
    simple is always an understatement.....

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Sounds like you might just need to overload the << output operator for any type you intend to use in your tree... then your PrintInOrder function should simply become something along the lines of:
    Code:
    template <class T>
    void AVLtree<T>::printInOrder (AVLnode<T> *root)
    {    
        if (root)
        {
            printInOrder (root->left);
            cout << root->info;
            printInOrder (root->right);
        }
    }
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User
    Join Date
    Apr 2002
    Posts
    94
    The thing is...I actually want the object within the node returned,so I can use the object in the calling function. The returned objects data are to be written to a file and used elsewhere....that's why I thought maybe, the print function could be changed and renamed so as it returns all the objects in each node.

    Sorry if I wasnt clearer before.
    simple is always an understatement.....

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Ok, returning a bunch of different objects one at a time via a recursive function to the caller isn't going to work. There may be several ways around this... You might try pushing the items onto a queue within the recursive function.

    Code:
    template <class T>
    void AVLTree<T>::printAVLtree(queue<T>& myqueue)
    {
        printInOrder(root,myqueue);
    }
    
    template <class T>
    void AVLtree<T>::printInOrder (AVLnode<T> *root,queue<T>& myqueue)
    {    
        if (root)
        {
            printInOrder (root->left);
            myqueue.push(root->info);
            printInOrder (root->right);
        }
    }
    Then any calling function does something like:
    Code:
    struct node
    {
        int data;
    };
    
    AVLtree<node> mytree;
    queue<node> myqueue;
    ...
    ...
    mytree.printAVLtree(myqueue);
    Now you have a queue containing the inorder traversal of the elements in the tree and you can do whatever you want with them...
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    If you don't need to modify the data, then you could provide a callback function to be called for each node:
    Code:
    template <class T>
    void AVLtree<T>::ForEach_InOrder(AVLnode<T> *root, void (*FECallback)(const T&))
    {
        if (root)
        {
            ForEach_InOrder(root->left, FECallback);
            FECallback(root->info);
            ForEach_InOrder(root->right, FECallback);
        }
    }
    gg

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help Debugging my AVL tree program.
    By Nextstopearth in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 01:48 AM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM