Thread: Should be a simple?......Binary Tee....passing of parameters...

  1. #1
    Registered User
    Join Date
    Jun 2005
    Posts
    131

    Should be a simple?......Binary Tee....passing of parameters...

    I recentley have been learning about binary trees and have been trying to learn each one of these functions but one of them I am having trouble with.... That function is copyTree... Hear is the code...all of it works but I don't know what I am suppose to list as my arguments when I call copyTree() from main....
    Code:
    //Header File Binary Search Tree
    #ifndef H_binaryTree
    #define H_binaryTree
    
    #include "string"
    #include <cassert>
    #include <iostream>
    
    using namespace std;
    
    template <class elemType>
    struct nodeType
    {
    	elemType			info;
    	nodeType<elemType>  *llink;
    	nodeType<elemType>  *rlink;
    };
    	
    template <class elemType>
    class binaryTreeType
    {
    public:
        const binaryTreeType<elemType>& operator=
                     (const binaryTreeType<elemType>&); 
        void copyTree(nodeType<elemType>* &copiedTreeRoot,
                      nodeType<elemType>* otherTreeRoot);HELP see main
        bool isEmpty() const;
        void inorderTraversal() const;
        void preorderTraversal() const;
        void postorderTraversal() const;
        int treeHeight() const;
        int treeNodeCount() const;
        int treeLeavesCount() const;
        void destroyTree();
        void printTree();
        void printTree(nodeType<elemType> *p);
        void printTreeNode(string label, nodeType<elemType> *p);
        binaryTreeType(const binaryTreeType<elemType>& otherTree); 
        binaryTreeType();   
        ~binaryTreeType();   
    
    protected:
        nodeType<elemType>  *root;
    
    private:
    
        void destroy(nodeType<elemType>* &p);
        void inorder(nodeType<elemType> *p) const;
        void preorder(nodeType<elemType> *p) const;
        void postorder(nodeType<elemType> *p) const;
        int height(nodeType<elemType> *p) const;
        int max(int x, int y) const;
    };
    
    template<class elemType>
    binaryTreeType<elemType>::binaryTreeType()
    {
    	root = NULL;
    }
    
    template<class elemType>
    bool binaryTreeType<elemType>::isEmpty() const
    {
    	return (root == NULL);
    }
    
    template<class elemType>
    void binaryTreeType<elemType>::inorderTraversal() const
    {
    	inorder(root);
    }
    
    template<class elemType>
    void binaryTreeType<elemType>::preorderTraversal() const
    {
    	preorder(root);
    }
    
    template<class elemType>
    void binaryTreeType<elemType>::postorderTraversal() const
    {
    	postorder(root);
    }
    
    template<class elemType>
    int binaryTreeType<elemType>::treeHeight() const
    {
    	return height(root);
    }
    
    template<class elemType>
    int binaryTreeType<elemType>::treeNodeCount() const
    {
    	return nodeCount(root);
    }
    
    template<class elemType>
    int binaryTreeType<elemType>::treeLeavesCount() const
    {
    	return leavesCount(root);
    }
    
    template <class elemType>
    void  binaryTreeType<elemType>::copyTree
                          (nodeType<elemType>* &copiedTreeRoot,
    		               nodeType<elemType>* otherTreeRoot)
    {
    	if (otherTreeRoot == NULL)
    		copiedTreeRoot = NULL;
    	else
    	{
    		copiedTreeRoot = new nodeType<elemType>;
    		copiedTreeRoot->info = otherTreeRoot->info;
    		copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
    		copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
    	}
    } //end copyTree
    
    
    template<class elemType>
    void binaryTreeType<elemType>::inorder(nodeType<elemType> *p) const
    {
    	if (p != NULL)
    	{
    		inorder(p->llink);
    		cout << p->info << " ";
    		inorder(p->rlink);
    	}
    }
    
    template<class elemType>
    void binaryTreeType<elemType>::preorder(nodeType<elemType> *p) const
    {
    	if (p != NULL)
    	{
    		cout << p->info << " ";
    		preorder(p->llink);
    		preorder(p->rlink);
    	}
    }
    
    template<class elemType>
    void binaryTreeType<elemType>::postorder(nodeType<elemType> *p) const
    {
    	if (p != NULL)
    	{
    		postorder(p->llink);
    		postorder(p->rlink);
    		cout << p->info << " ";
    	}		
    }
    
       //Overload the assignment operator
    template<class elemType>
    const binaryTreeType<elemType>& binaryTreeType<elemType>::
               operator=(const binaryTreeType<elemType>& otherTree)
    { 
    	if (this != &otherTree) //avoid self-copy
    	{
    		if (root != NULL)  //if the binary tree is not empty, 
    			              //destroy the binary tree
    			destroy(root);
    
    		if (otherTree.root == NULL) //otherTree is empty
    			root = NULL;
    		else
    			copyTree(root, otherTree.root);
    	}//end else
    
       return *this; 
    }
    
    template <class elemType>
    void  binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
    {
    	if (p != NULL)
    	{
    		destroy(p->llink);
    		destroy(p->rlink);
    		delete p;
    		p = NULL;
    	}
    }
    
    template <class elemType>
    void  binaryTreeType<elemType>::destroyTree()
    {
    	destroy(root);
    }
    
    	//copy constructor
    template <class elemType>
    binaryTreeType<elemType>::binaryTreeType
                  (const binaryTreeType<elemType>& otherTree)
    {
    	if (otherTree.root == NULL) //otherTree is empty
    		root = NULL;
    	else
    		copyTree(root, otherTree.root);
    }
    
    template <class elemType>
    binaryTreeType<elemType>::~binaryTreeType()
    {
    	destroy(root);
    }
    
    template<class elemType>
    int binaryTreeType<elemType>::height(nodeType<elemType> *p) const
    {
    	if (p == NULL)
    		return 0;
    	else
    		return 1 + max(height(p->llink), height(p->rlink));
    }
    
    template<class elemType>
    int binaryTreeType<elemType>::max(int x, int y) const
    {
    	if (x >= y)
    		return x;
    	else
    		return y;
    }
    
    template<class elemType>
    void binaryTreeType<elemType>::insert(const elemType& insertItem)
    {
        nodeType<elemType> *current;  //pointer to traverse the tree
        nodeType<elemType> *trailCurrent; //pointer behind current
        nodeType<elemType> *newNode;  //pointer to create the node
    
        newNode = new nodeType<elemType>;
        assert(newNode != NULL);
        newNode->info = insertItem;
        newNode->llink = NULL;
        newNode->rlink = NULL;
    
        if (root == NULL)
           root = newNode;
        else
        {
           current = root;
     
           while (current != NULL)
           {
               trailCurrent = current;
    
               if (current->info == insertItem)
               {
                   cout << "The item to be inserted is already in ";
                   cout << "the list -- duplicates are not allowed."
                        << endl;
                   return;
               }
               else
                   if (current->info > insertItem)
                       current = current->llink;
                   else
                       current = current->rlink;
           }//end while
    
           if (trailCurrent->info > insertItem)
               trailCurrent->llink = newNode;
           else
               trailCurrent->rlink = newNode;
       }
    }//end insert
    
    
    template<class elemType>
    void binaryTreeType<elemType>::printTree()
    {
    	printTree(root);
    }
    
    template<class elemType>
    void binaryTreeType<elemType>::printTree(nodeType<elemType> *p)
    {
        cout << "    root:  " << p->info << endl;
        printTreeNode("left", p->llink);
        printTreeNode("right", p->rlink);
    }
    
    template<class elemType>
    void binaryTreeType<elemType>::printTreeNode(string label, nodeType<elemType> *p)
    {
    	if(p != NULL)
        {
    		cout << "    " << label << "  " << p->info;
            printTreeNode("left:", p->llink);
            printTreeNode("right:", p->rlink);
            cout << endl;
        }
    }
    
    #endif
    
    void main()
    {
    	binaryTreeType<int> treeRoot;
    	int num;
    
    	cout << "You are going to populate the tree now" << endl;
    	cout << "Enter a number then hit enter. This will add the number to the tree" << endl;
    	cout << "When you don't want to enter anymore numbers" <<endl; 
    	cout << "into the tree type -1111 and hit enter" << endl << endl;
    	cout << "Enter Numbers now" <<endl;
    	cin >> num;
    
    	while (num != -1111)
    	{
    		treeRoot.insert(num);
    		cin >> num;
    	}
    
    	cout << endl << "Tree nodes in inorder sequence: ";
    	treeRoot.inorderTraversal();
    
    	cout << endl << "Tree nodes in preorder sequence: ";
    	treeRoot.preorderTraversal();
    
    	cout << endl << "Tree nodes in postorder sequence: ";
    	treeRoot.postorderTraversal();
    	cout << endl;
    	cout << "Tree Height: " << treeRoot.treeHeight()
    		 << endl << endl;
    	cout << "Tree in current state" << endl;
    	treeRoot.printTree();
    	
    	treeRoot.copyTree(? 2 arguments but what);HELP
    
    	treeRoot.printTree();
    }
    It looks like a pointer to the root node and then...ahh who am I kidding I really don't know....any insight would be great...

    Thanks

    Chad

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Don't use void main. Use int main and add return 0; to the end.

    Code:
    nodeType<elemType>* &copiedTreeRoot,
    Is it a pointer or a reference? Make up your mind.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    If it's a pointer:
    Code:
    treeRoot.copyTree(&treeRoot, ...);
    A reference:
    Code:
    treeRoot.copyTree(treeRoot, ...);
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> Is it a pointer or a reference? Make up your mind.

    It's a reference to a pointer, which is a perfectly valid way of modifying what a pointer points to in a function.

    You can create a nodeType pointer variable and pass it to the function. When the function returns, it will point to the copied tree, and then you will have to delete it in the main code.

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    131
    Quote Originally Posted by Daved
    >> Is it a pointer or a reference? Make up your mind.

    It's a reference to a pointer, which is a perfectly valid way of modifying what a pointer points to in a function.

    You can create a nodeType pointer variable and pass it to the function. When the function returns, it will point to the copied tree, and then you will have to delete it in the main code.
    Still a little bit confused....


    nodeType<int> * current;
    nodeTYpe<int> * copy:

    ?

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    It really depends on what you want to do. The copyTree method is a bit odd in that it is a member of the binaryTree class but ignores the data of the binaryTree that it is called from. You could pass copy from your text above by just passing it directly. What you would pass as the second parameter is a little more confusing. Look at the code in the operator=. It calls copyTree perfectly. That seems to be the intended usage... internal copying of one tree's data to another. Im not sure why you would want to call it from main, you'd have to be more clear on what you are trying to accomplish with that.

  7. #7
    Registered User
    Join Date
    Jun 2005
    Posts
    131
    Well, basically this is all a learning excersie for me. I am trying to rip these functions apart in my head to learn more about the binary tree. As far as accessing the the copyTree goes I am more intrested in basically making it work and understand why it works. So with that in mind all I am simply tyring to do is copy the tree into a tempTree and print it back out to me. I guess a more better way to confirm this is if maybe I swapped the left and right subTrees like this.

    Code:
    template <class elemType>
    void binaryTreeType<elemType>::swapTree
                          (nodeType<elemType>* &copiedTreeRoot,
    		               nodeType<elemType>* otherTreeRoot)
    {
    	if(otherTreeRoot == NULL)
    		copiedTreeRoot = NULL;
    	else
    	{
    		copiedTreeRoot = new nodeType<elemType>;  //first time it get the root
    		copiedTreeRoot->info = otherTreeRoot->info;
    		//I am swapping this so when I do print the 
                   //tree back to me the subtrees will be swapped.  It is strickly for conformation...
    		swapTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
    		
    		swapTree(copiedTreeRoot->llink, otherTreeRoot->llink);
    
    	}
    } //end copyTree
    Like I said my whole goal now is to populate the tree, print the tree, copy the tree (i.e. swapTree), and print new swapped subtree tree. I have all the way to the copy part down.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Passing parameters to a module
    By Sue Paterniti in forum C Programming
    Replies: 25
    Last Post: 05-09-2002, 06:47 PM
  2. passing parameters to main
    By jpchand in forum C++ Programming
    Replies: 4
    Last Post: 04-13-2002, 02:27 PM
  3. passing templates as parameters - something funky?
    By archetype in forum C++ Programming
    Replies: 1
    Last Post: 02-20-2002, 08:38 PM
  4. Passing parameters to other programs...is it possible?
    By face_master in forum Windows Programming
    Replies: 3
    Last Post: 01-28-2002, 07:48 AM
  5. problems passing parameters between functions
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 11-21-2001, 11:41 AM