Binary trees i need a help with making recursive functions non-recursive



  • hi everyone i'm having a problem with binary tree functions
    i don't know how to make functions traverse, insert and search to be non-recursive
    i have a recursive code for these functions

    here is code of "bintree.h" 

    #pragma once
    #include <iostream>
    using namespace std;
    template <typename Type>
    class bintree {

    public:
        struct treenode
            {
                Type Element;
                treenode *left, *right;
                treenode() : left(0), right(0) {}
                treenode(Type item, treenode *leftnode=0,treenode *rightnode=0) :
                Element(item), left(leftnode),right(rightnode) {}
            };
    protected:
        treenode *root;
        Type RefValue;
        bool Insert(treenode* &tree, const Type& item);
        bool NInsert(treenode* &tree,const Type& item);
        void Traverse(treenode *tree, ostream& out) const;
        bool Search(treenode* tree, const Type& item) const;
        void destroy(treenode *tree);
    public:
        bintree() : root(0) {}
        bintree(Type refvalue) : RefValue(refvalue),root(0) {}
        virtual ~bintree();
        virtual bool Insert(const Type& item);
        virtual bool Search(const Type& item) const;
        virtual bool Delete(const Type& item);
        friend istream& operator>><>(istream& in,bintree<Type>& Tree);
        friend ostream& operator<<<>(ostream& out, const bintree<Type>& Tree);
        };
     

    here is code of "bintemp.h" where functions are defined

    #pragma once
    #include "bintree.h"

    template <typename Type>
    bool bintree<Type>::Insert(treenode* &tree,const Type& item)

    {
        if (tree == 0) {
            tree = new treenode(item);
            return tree ? true : false;
            }
        else if (item < tree->Element)
            return Insert(tree->left, item);
        else return Insert(tree->right, item);
    }


    template <typename Type>
    void bintree<Type>::Traverse(treenode *tree,ostream& out) const
    {
        if (tree) {
            Traverse(tree->left, out);
            out << tree->Element << ' ';
            Traverse(tree->right, out);
        }
    }
    template <typename Type>
    bool bintree<Type>::Search(treenode* tree,const Type& item) const
    {
        if (tree) {
            if (tree->Element == item)
                return true;
            else if (item < tree->Element)
                return Search(tree->left, item);
            else
                return Search(tree->right, item);
        }
        return false;
    }

    i hope someone can help me

     

     

     



  • Let me guess: this is your homework assignment for CSCI 2270. First result on googling "bintree.h" is this, and that's the website for Michael Main, who happens to be teaching Data Structures this semester.



  • Close, but no cigar.

    1.  Google "class bintree" "struct treenode" -> http://www.computing.dundee.ac.uk/courses/ac21001/protected/WebVersion/Chapter%2014.html

    2.  "AC21001 Home page" -> http://www.computing.dundee.ac.uk/courses/ac21001/

    3.  "Course Guide" -> http://www.computing.dundee.ac.uk/Teaching/fullcoursedetails.asp?AC21001

    4.  Essential Titles: Introduction to data structures and algorithms with C++, Glenn W Rowe, Prentice Hall, 0-13-579178-2

    So this question is more than likely homework from a class which uses the above book (or at least uses code from that book).  The things you linked to are similar, but my find is the EXACT code.  I suppose it is possible the course you linked to uses that code, but hundreds of other courses could use it as well.

    I couldn't find any questions similar to what the guy was asking, so I don't think he is enrolled in that particular school/class (does TDWTF have an UK following?).  Anyone want to bother tracking this down any further?



  • Don't put

    using namespace std;
    in a header file

     



  • here is code of "bintree.h" 

    #pragma once

    non-portable, use include guards. 


    #include <iostream>
    using namespace std;

    don't put using namespace std; in a header file.


    template <typename Type>
    class bintree {

    public:
        struct treenode
            {
                Type Element;
                treenode *left, *right;
                treenode() : left(0), right(0) {}
                treenode(Type item, treenode *leftnode=0,treenode *rightnode=0) :
                Element(item), left(leftnode),right(rightnode) {}
            };


    protected:

    Make member variables private, not protected

     


        treenode *root;
        Type RefValue;
        bool Insert(treenode* &tree, const Type& item);
        bool NInsert(treenode* &tree,const Type& item);
        void Traverse(treenode *tree, ostream& out) const;
        bool Search(treenode* tree, const Type& item) const;
        void destroy(treenode *tree);
    public:
        bintree() : root(0) {}
        bintree(Type refvalue) : RefValue(refvalue),root(0) {}
        virtual ~bintree();
        virtual bool Insert(const Type& item);
        virtual bool Search(const Type& item) const;
        virtual bool Delete(const Type& item);


        friend istream& operator>><>(istream& in,bintree<Type>& Tree);
        friend ostream& operator<<<>(ostream& out, const bintree<Type>& Tree);

    These also need to be forwardly declared previously. 

        };

    Rule of 3? Assignment and copy-construct need to be disabled.  

    here is code of "bintemp.h" where functions are defined

    #pragma once
    #include "bintree.h"

    This is the wrong way round though, you'll get link errors. Your template
    must include this file. You are missing a bunch of other functions too.

    template <typename Type>
    bool bintree<Type>::Insert(treenode* &tree,const Type& item)

    {
        if (tree == 0) {
            tree = new treenode(item);
            return tree ? true : false;

    new never returns NULL, it throws an exception if it fails, either bad_alloc if the
    allocation itself failed, or another exception if the constructor threw.

    A tree, by the way, is one of the few examples where recursion can be useful, although
    if you are going only down one branch at each iteration it is possible to use a loop,
    terminating either when you have found the node you are looking for or have reached
    a leaf and there is no further to go.

     



  • While I won't give you the answer since this does look like a homework assignment, I will at least help you go in the right direction.

    Search is the easiest one to convert.

    Think about the job that function is supposed to do: it starts at the top of the tree and works its way down until it either finds a matching node or determines that the node isn't there.

    Look at the wording of that sentence.  You're doing something until one of two conditions is met.  That often lends itself well to a while loop.  In this case, while you have a current node to look at, and it's not the one you're looking for, you advance your current node to either its left child or its right child, depending on how its Element compares to the one you were given in the function call.  At any time that your current node is NULL, you know you didn't find what you were looking for, and you return false.

    Assuming you get out of the loop and your current node isn't NULL, you found what you were looking for, and you can return true.


    All that being said, the design of the Search function is a little light on capability, as it will only tell you whether something is in the tree.  If your Type is complex enough to have several fields that don't participate in the comparison operators, you have no way to get to it, because the function returns only a bool and doesn't ever give the caller any kind of reference to the node that was found.  If it's really going to do that little (and not change any of the nodes you travel through or look for), then the treenode that's passed into the top of it should be const.


    The code for Insert is only a little bit more complicated than Search.

    The one that's a real pain is the traversal.  There's no easy way to go through the whole tree in order without recursion.

    If I really needed to work my way through a whole tree in order like that, I'd probably at least do data recursion, if not code recursion, or else I would use a different data structure.  A simple binary tree is built for searching, not for iterating through the whole thing in order.  Always choose the right tool for the job.



  • it is not my homework

    i'm just preparing for exam and trying to find  how to make these functions non-recursive

    it's very possible that my teacher will give some of these functions for my next exam


     




       



  • thanks i think that some of tips you gave me will help me to solve my problem

     



  • Dumb comment:

    What "benefit" do you get from a recursive function? Its an "easy way" to navigate back to where you started/you currently are... What you would need is a way to determine how you can step back inside a loop... I would use a stack to get back once i am finished with my current node.. But thats all rambling.. Last time I wrote B-Tree code was about 10 years ago... Man I get old :)

     


Log in to reply