comments on this Binary Searh Tree template?

Discussion in 'C++' started by Nobody, Feb 14, 2004.

  1. Nobody

    Nobody Guest

    This is sort of my first attempt at writing a template container class, just
    wanted some feedback if everything looks kosher or if there can be any
    improvements. This is a template class for a binary search tree. Note there
    is a requirement for this to be a Win32/MFC "friendly" class, thus the use
    of CObject and POSITION. There is also a requirement for there not to be a
    separate iterator class.

    template <class TYPE, class ARG_TYPE = const TYPE&> class CBinarySearchTree;

    template <class TYPE, class ARG_TYPE>
    class CBinarySearchTree : public CObject
    {
    // Constructors
    public:
    CBinarySearchTree();
    // Attributes
    public:
    int GetCount() const;
    POSITION GetRoot() const;
    POSITION GetLeft(POSITION& pos) const;
    POSITION GetRight(POSITION& pos) const;
    ARG_TYPE GetElement(POSITION& pos) const;
    // Operations
    public:
    BOOL Insert(ARG_TYPE newElement);
    BOOL Remove(ARG_TYPE element);
    void RemoveAll();
    POSITION Find(ARG_TYPE element);
    // Implementation
    public:
    virtual ~CBinarySearchTree();
    protected:
    struct _TREENODE
    {
    TYPE element;
    _TREENODE* pLeft;
    _TREENODE* pRight;
    };
    protected:
    _TREENODE* m_pRoot;
    UINT m_nCount;
    protected:
    BOOL Insert(ARG_TYPE newElement, _TREENODE*& pNode);
    BOOL Remove(ARG_TYPE element, _TREENODE*& pNode);
    LPVOID FindMin(_TREENODE* pNode);
    };

    ////////////////////////////////////////////////////////////////////////////
    /

    template <class TYPE, class ARG_TYPE>
    CBinarySearchTree<TYPE, ARG_TYPE>::CBinarySearchTree()
    {
    m_pRoot = NULL;
    m_nCount = 0;
    }

    template <class TYPE, class ARG_TYPE>
    CBinarySearchTree<TYPE, ARG_TYPE>::~CBinarySearchTree()
    {
    RemoveAll();
    }

    template <class TYPE, class ARG_TYPE>
    int CBinarySearchTree<TYPE, ARG_TYPE>::GetCount() const
    {
    return m_nCount;
    }

    template <class TYPE, class ARG_TYPE>
    POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetRoot() const
    {
    return (POSITION)m_pRoot;
    }

    template <class TYPE, class ARG_TYPE>
    POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetLeft(POSITION& pos) const
    {
    return (POSITION)(((_TREENODE*)pos)->pLeft);
    }

    template <class TYPE, class ARG_TYPE>
    POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetRight(POSITION& pos) const
    {
    return (POSITION)(((_TREENODE*)pos)->pRight);
    }

    template <class TYPE, class ARG_TYPE>
    ARG_TYPE CBinarySearchTree<TYPE, ARG_TYPE>::GetElement(POSITION& pos) const
    {
    return ((_TREENODE*)pos)->element;
    }

    template <class TYPE, class ARG_TYPE>
    BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Insert(ARG_TYPE newElement)
    {
    return Insert(newElement, m_pRoot);
    }

    template <class TYPE, class ARG_TYPE>
    BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Remove(ARG_TYPE element)
    {
    return Remove(element, m_pRoot);
    }

    template <class TYPE, class ARG_TYPE>
    void CBinarySearchTree<TYPE, ARG_TYPE>::RemoveAll()
    {
    while (m_pRoot != NULL)
    Remove(m_pRoot->element);
    }

    template <class TYPE, class ARG_TYPE>
    POSITION CBinarySearchTree<TYPE, ARG_TYPE>::Find(ARG_TYPE element)
    {
    return NULL;
    }

    template <class TYPE, class ARG_TYPE>
    BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Insert(ARG_TYPE newElement,
    _TREENODE*& pNode)
    {
    if (pNode != NULL)
    {
    if (newElement < pNode->element)
    return Insert(newElement, pNode->pLeft);

    if (newElement > pNode->element)
    return Insert(newElement, pNode->pRight);
    }
    else
    {
    pNode = new _TREENODE;

    if (!pNode)
    return FALSE;

    m_nCount++;

    pNode->element = newElement;
    pNode->pLeft = NULL;
    pNode->pRight = NULL;

    return TRUE;
    }

    return TRUE;
    }

    template <class TYPE, class ARG_TYPE>
    BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Remove(ARG_TYPE element, _TREENODE*&
    pNode)
    {
    _TREENODE* pTempNode = NULL;

    if (!pNode)
    return TRUE;

    if (element < pNode->element)
    {
    Remove(element, pNode->pLeft);
    }
    else if (element > pNode->element)
    {
    Remove(element, pNode->pRight);
    }
    else if (pNode->pLeft != NULL && pNode->pRight != NULL)
    {
    pTempNode = (_TREENODE*)FindMin(pNode->pRight);
    pNode->element = pTempNode->element;
    Remove(element, pNode->pRight);
    }
    else
    {
    pTempNode = pNode;

    if (m_nCount > 0)

    m_nCount--;

    if (!pNode->pLeft)
    pNode = pNode->pRight;
    else if (!pNode->pRight)
    pNode = pNode->pLeft;

    delete pTempNode;
    }

    return TRUE;
    }

    template <class TYPE, class ARG_TYPE>
    LPVOID CBinarySearchTree<TYPE, ARG_TYPE>::FindMin(_TREENODE* pNode)
    {
    if (!pNode)
    return NULL;
    else if (!pNode->pLeft)
    return (LPVOID)pNode;

    return FindMin(pNode->pLeft);
    }


    Thanks!
     
    Nobody, Feb 14, 2004
    #1
    1. Advertising

  2. Miscellaneous comments below

    "Nobody" <> wrote in message
    news:%ZjXb.33476$1O.26297@fed1read05...
    > This is sort of my first attempt at writing a template container class,

    just
    > wanted some feedback if everything looks kosher or if there can be any
    > improvements. This is a template class for a binary search tree. Note

    there
    > is a requirement for this to be a Win32/MFC "friendly" class, thus the use
    > of CObject and POSITION. There is also a requirement for there not to be a
    > separate iterator class.
    >
    > template <class TYPE, class ARG_TYPE = const TYPE&> class

    CBinarySearchTree;
    >
    > template <class TYPE, class ARG_TYPE>
    > class CBinarySearchTree : public CObject
    > {
    > // Constructors
    > public:
    > CBinarySearchTree();
    > // Attributes
    > public:
    > int GetCount() const;
    > POSITION GetRoot() const;
    > POSITION GetLeft(POSITION& pos) const;
    > POSITION GetRight(POSITION& pos) const;
    > ARG_TYPE GetElement(POSITION& pos) const;


    None of the above three functions modify the pos argument, therefore it
    should be

    ARG_TYPE GetElement(const POSITION& pos) const;

    As you have coded it the following is illegal C++

    mytree.GetElement(mytree.GetRoot())

    which is a bit of a restriction. As it happens MSVC++ does not enforce this,
    but that is MSVC++'s problem, there's still no excuse for using non-const
    references where const references are correct.

    Also can't you make GetLeft, GetRight and GetElement static? It would make
    them very slightly more useable (in the absense of a seperate iterator
    class).


    > // Operations
    > public:
    > BOOL Insert(ARG_TYPE newElement);
    > BOOL Remove(ARG_TYPE element);


    bool not BOOL. bool is standard C++, BOOL is not. Try to avoid non-standard
    code when there is no good reason for it. (Being more like MFC is not a good
    enough reason).

    > void RemoveAll();
    > POSITION Find(ARG_TYPE element);
    > // Implementation
    > public:
    > virtual ~CBinarySearchTree();
    > protected:
    > struct _TREENODE


    Names with an underscore followed by a capital letter are reserved for
    compiler and standard library uses. So _TREENODE is not legal.

    > {
    > TYPE element;
    > _TREENODE* pLeft;
    > _TREENODE* pRight;
    > };
    > protected:
    > _TREENODE* m_pRoot;
    > UINT m_nCount;


    Ditto unsigned not UINT. Actually probably should be size_t (64 bit
    computing is round the corner, size_t will be a 64 bit type when it arrives)

    > protected:
    > BOOL Insert(ARG_TYPE newElement, _TREENODE*& pNode);
    > BOOL Remove(ARG_TYPE element, _TREENODE*& pNode);
    > LPVOID FindMin(_TREENODE* pNode);


    Ditto, void* not LPVOID.

    > };


    No copy constructor or assignment operator. You can implement these easily
    enough using the member functions you have already defined, so why not do
    it?

    >
    >

    ////////////////////////////////////////////////////////////////////////////
    > /
    >
    > template <class TYPE, class ARG_TYPE>
    > CBinarySearchTree<TYPE, ARG_TYPE>::CBinarySearchTree()
    > {
    > m_pRoot = NULL;
    > m_nCount = 0;
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > CBinarySearchTree<TYPE, ARG_TYPE>::~CBinarySearchTree()
    > {
    > RemoveAll();
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > int CBinarySearchTree<TYPE, ARG_TYPE>::GetCount() const
    > {
    > return m_nCount;
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetRoot() const
    > {
    > return (POSITION)m_pRoot;
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetLeft(POSITION& pos) const
    > {
    > return (POSITION)(((_TREENODE*)pos)->pLeft);
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetRight(POSITION& pos) const
    > {
    > return (POSITION)(((_TREENODE*)pos)->pRight);
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > ARG_TYPE CBinarySearchTree<TYPE, ARG_TYPE>::GetElement(POSITION& pos)

    const
    > {
    > return ((_TREENODE*)pos)->element;
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Insert(ARG_TYPE newElement)
    > {
    > return Insert(newElement, m_pRoot);
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Remove(ARG_TYPE element)
    > {
    > return Remove(element, m_pRoot);
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > void CBinarySearchTree<TYPE, ARG_TYPE>::RemoveAll()
    > {
    > while (m_pRoot != NULL)
    > Remove(m_pRoot->element);
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > POSITION CBinarySearchTree<TYPE, ARG_TYPE>::Find(ARG_TYPE element)
    > {


    Huh?

    > return NULL;
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Insert(ARG_TYPE newElement,
    > _TREENODE*& pNode)


    I'd like to see this function return true if an element was inserted and
    false if you attempt to insert a duplicate element, and a exception thrown
    for the out of memory error.

    This code is not exception safe, but I guess you aren't too worried about
    that.

    > {
    > if (pNode != NULL)
    > {
    > if (newElement < pNode->element)
    > return Insert(newElement, pNode->pLeft);
    >
    > if (newElement > pNode->element)
    > return Insert(newElement, pNode->pRight);
    > }
    > else
    > {
    > pNode = new _TREENODE;
    >
    > if (!pNode)
    > return FALSE;


    More MCVC++ specific code. new does return NULL on memory exhaustion in
    standard C++, it throws an exception instead.

    >
    > m_nCount++;
    >
    > pNode->element = newElement;
    > pNode->pLeft = NULL;
    > pNode->pRight = NULL;


    I think the above is better written like this


    _TREENODE* tmp;
    tmp = new _TREENODE(newElement);
    if (tmp == 0) // MSVC++ specific code, new can return NULL in MSVC++
    throw std::bad_alloc(); // do the right thing on memory
    exhaustion
    pNode = tmp;
    ++m_nCount;

    You'll have to add the constructor for _TREENODE.

    This code has two points, it does the correct thing on memory exhaustion,
    and it is exception safe, i.e. if either you run out of memory, or if
    copying the newElement throws an exception then your tree is left unchanged,
    that is not the case with your current code.

    >
    > return TRUE;
    > }
    >
    > return TRUE;
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Remove(ARG_TYPE element,

    _TREENODE*&
    > pNode)
    > {
    > _TREENODE* pTempNode = NULL;
    >
    > if (!pNode)
    > return TRUE;
    >
    > if (element < pNode->element)
    > {
    > Remove(element, pNode->pLeft);
    > }
    > else if (element > pNode->element)
    > {
    > Remove(element, pNode->pRight);
    > }
    > else if (pNode->pLeft != NULL && pNode->pRight != NULL)
    > {
    > pTempNode = (_TREENODE*)FindMin(pNode->pRight);
    > pNode->element = pTempNode->element;
    > Remove(element, pNode->pRight);
    > }
    > else
    > {
    > pTempNode = pNode;
    >
    > if (m_nCount > 0)
    >
    > m_nCount--;
    >
    > if (!pNode->pLeft)
    > pNode = pNode->pRight;
    > else if (!pNode->pRight)
    > pNode = pNode->pLeft;
    >
    > delete pTempNode;
    > }
    >
    > return TRUE;
    > }
    >
    > template <class TYPE, class ARG_TYPE>
    > LPVOID CBinarySearchTree<TYPE, ARG_TYPE>::FindMin(_TREENODE* pNode)
    > {
    > if (!pNode)
    > return NULL;
    > else if (!pNode->pLeft)
    > return (LPVOID)pNode;
    >
    > return FindMin(pNode->pLeft);
    > }
    >
    >
    > Thanks!
    >


    john
     
    John Harrison, Feb 14, 2004
    #2
    1. Advertising

  3. >
    > No copy constructor or assignment operator. You can implement these easily
    > enough using the member functions you have already defined, so why not do
    > it?
    >


    Actually scratch that. A copy ctor written that way would not be efficient.
    You should use a straightforward recursive tree copy instead.

    john
     
    John Harrison, Feb 14, 2004
    #3
  4. Nobody

    Nobody Guest

    Thanks for the feedback John. Some good technical points here that I will
    modify my code for and some style issues that are "to each his own" :).

    Ooops, in the code posted, the Find function was not implemented.

    Why make the GetElement, GetLeft and GetRight static? I understand they
    operate on the node struct and not the tree itself, but does it add anything
    to be static?

    If those methods were static, wouldn't I have to call them with some ugly
    code like:

    CBinarySearchTree<int>::GetLeft(pos);

    or something of that nature? vs.

    tree.GetLeft(pos);

    I have always followed the belief of not making class functions or members
    static. If a member function is static, it probably shouldn't be a member
    function.

    Yes, I do need to implement a copy constructor as well.

    Again, thanks for the feedback, much appreciated.

    "John Harrison" <> wrote in message
    news:c0kkar$165v2l$-berlin.de...
    > Miscellaneous comments below
    >
    > "Nobody" <> wrote in message
    > news:%ZjXb.33476$1O.26297@fed1read05...
    > > This is sort of my first attempt at writing a template container class,

    > just
    > > wanted some feedback if everything looks kosher or if there can be any
    > > improvements. This is a template class for a binary search tree. Note

    > there
    > > is a requirement for this to be a Win32/MFC "friendly" class, thus the

    use
    > > of CObject and POSITION. There is also a requirement for there not to be

    a
    > > separate iterator class.
    > >
    > > template <class TYPE, class ARG_TYPE = const TYPE&> class

    > CBinarySearchTree;
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > class CBinarySearchTree : public CObject
    > > {
    > > // Constructors
    > > public:
    > > CBinarySearchTree();
    > > // Attributes
    > > public:
    > > int GetCount() const;
    > > POSITION GetRoot() const;
    > > POSITION GetLeft(POSITION& pos) const;
    > > POSITION GetRight(POSITION& pos) const;
    > > ARG_TYPE GetElement(POSITION& pos) const;

    >
    > None of the above three functions modify the pos argument, therefore it
    > should be
    >
    > ARG_TYPE GetElement(const POSITION& pos) const;
    >
    > As you have coded it the following is illegal C++
    >
    > mytree.GetElement(mytree.GetRoot())
    >
    > which is a bit of a restriction. As it happens MSVC++ does not enforce

    this,
    > but that is MSVC++'s problem, there's still no excuse for using non-const
    > references where const references are correct.
    >
    > Also can't you make GetLeft, GetRight and GetElement static? It would make
    > them very slightly more useable (in the absense of a seperate iterator
    > class).
    >
    >
    > > // Operations
    > > public:
    > > BOOL Insert(ARG_TYPE newElement);
    > > BOOL Remove(ARG_TYPE element);

    >
    > bool not BOOL. bool is standard C++, BOOL is not. Try to avoid

    non-standard
    > code when there is no good reason for it. (Being more like MFC is not a

    good
    > enough reason).
    >
    > > void RemoveAll();
    > > POSITION Find(ARG_TYPE element);
    > > // Implementation
    > > public:
    > > virtual ~CBinarySearchTree();
    > > protected:
    > > struct _TREENODE

    >
    > Names with an underscore followed by a capital letter are reserved for
    > compiler and standard library uses. So _TREENODE is not legal.
    >
    > > {
    > > TYPE element;
    > > _TREENODE* pLeft;
    > > _TREENODE* pRight;
    > > };
    > > protected:
    > > _TREENODE* m_pRoot;
    > > UINT m_nCount;

    >
    > Ditto unsigned not UINT. Actually probably should be size_t (64 bit
    > computing is round the corner, size_t will be a 64 bit type when it

    arrives)
    >
    > > protected:
    > > BOOL Insert(ARG_TYPE newElement, _TREENODE*& pNode);
    > > BOOL Remove(ARG_TYPE element, _TREENODE*& pNode);
    > > LPVOID FindMin(_TREENODE* pNode);

    >
    > Ditto, void* not LPVOID.
    >
    > > };

    >
    > No copy constructor or assignment operator. You can implement these easily
    > enough using the member functions you have already defined, so why not do
    > it?
    >
    > >
    > >

    >

    ////////////////////////////////////////////////////////////////////////////
    > > /
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > CBinarySearchTree<TYPE, ARG_TYPE>::CBinarySearchTree()
    > > {
    > > m_pRoot = NULL;
    > > m_nCount = 0;
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > CBinarySearchTree<TYPE, ARG_TYPE>::~CBinarySearchTree()
    > > {
    > > RemoveAll();
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > int CBinarySearchTree<TYPE, ARG_TYPE>::GetCount() const
    > > {
    > > return m_nCount;
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetRoot() const
    > > {
    > > return (POSITION)m_pRoot;
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetLeft(POSITION& pos) const
    > > {
    > > return (POSITION)(((_TREENODE*)pos)->pLeft);
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > POSITION CBinarySearchTree<TYPE, ARG_TYPE>::GetRight(POSITION& pos)

    const
    > > {
    > > return (POSITION)(((_TREENODE*)pos)->pRight);
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > ARG_TYPE CBinarySearchTree<TYPE, ARG_TYPE>::GetElement(POSITION& pos)

    > const
    > > {
    > > return ((_TREENODE*)pos)->element;
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Insert(ARG_TYPE newElement)
    > > {
    > > return Insert(newElement, m_pRoot);
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Remove(ARG_TYPE element)
    > > {
    > > return Remove(element, m_pRoot);
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > void CBinarySearchTree<TYPE, ARG_TYPE>::RemoveAll()
    > > {
    > > while (m_pRoot != NULL)
    > > Remove(m_pRoot->element);
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > POSITION CBinarySearchTree<TYPE, ARG_TYPE>::Find(ARG_TYPE element)
    > > {

    >
    > Huh?
    >
    > > return NULL;
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Insert(ARG_TYPE newElement,
    > > _TREENODE*& pNode)

    >
    > I'd like to see this function return true if an element was inserted and
    > false if you attempt to insert a duplicate element, and a exception thrown
    > for the out of memory error.
    >
    > This code is not exception safe, but I guess you aren't too worried about
    > that.
    >
    > > {
    > > if (pNode != NULL)
    > > {
    > > if (newElement < pNode->element)
    > > return Insert(newElement, pNode->pLeft);
    > >
    > > if (newElement > pNode->element)
    > > return Insert(newElement, pNode->pRight);
    > > }
    > > else
    > > {
    > > pNode = new _TREENODE;
    > >
    > > if (!pNode)
    > > return FALSE;

    >
    > More MCVC++ specific code. new does return NULL on memory exhaustion in
    > standard C++, it throws an exception instead.
    >
    > >
    > > m_nCount++;
    > >
    > > pNode->element = newElement;
    > > pNode->pLeft = NULL;
    > > pNode->pRight = NULL;

    >
    > I think the above is better written like this
    >
    >
    > _TREENODE* tmp;
    > tmp = new _TREENODE(newElement);
    > if (tmp == 0) // MSVC++ specific code, new can return NULL in

    MSVC++
    > throw std::bad_alloc(); // do the right thing on memory
    > exhaustion
    > pNode = tmp;
    > ++m_nCount;
    >
    > You'll have to add the constructor for _TREENODE.
    >
    > This code has two points, it does the correct thing on memory exhaustion,
    > and it is exception safe, i.e. if either you run out of memory, or if
    > copying the newElement throws an exception then your tree is left

    unchanged,
    > that is not the case with your current code.
    >
    > >
    > > return TRUE;
    > > }
    > >
    > > return TRUE;
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > BOOL CBinarySearchTree<TYPE, ARG_TYPE>::Remove(ARG_TYPE element,

    > _TREENODE*&
    > > pNode)
    > > {
    > > _TREENODE* pTempNode = NULL;
    > >
    > > if (!pNode)
    > > return TRUE;
    > >
    > > if (element < pNode->element)
    > > {
    > > Remove(element, pNode->pLeft);
    > > }
    > > else if (element > pNode->element)
    > > {
    > > Remove(element, pNode->pRight);
    > > }
    > > else if (pNode->pLeft != NULL && pNode->pRight != NULL)
    > > {
    > > pTempNode = (_TREENODE*)FindMin(pNode->pRight);
    > > pNode->element = pTempNode->element;
    > > Remove(element, pNode->pRight);
    > > }
    > > else
    > > {
    > > pTempNode = pNode;
    > >
    > > if (m_nCount > 0)
    > >
    > > m_nCount--;
    > >
    > > if (!pNode->pLeft)
    > > pNode = pNode->pRight;
    > > else if (!pNode->pRight)
    > > pNode = pNode->pLeft;
    > >
    > > delete pTempNode;
    > > }
    > >
    > > return TRUE;
    > > }
    > >
    > > template <class TYPE, class ARG_TYPE>
    > > LPVOID CBinarySearchTree<TYPE, ARG_TYPE>::FindMin(_TREENODE* pNode)
    > > {
    > > if (!pNode)
    > > return NULL;
    > > else if (!pNode->pLeft)
    > > return (LPVOID)pNode;
    > >
    > > return FindMin(pNode->pLeft);
    > > }
    > >
    > >
    > > Thanks!
    > >

    >
    > john
    >
    >
     
    Nobody, Feb 14, 2004
    #4
  5. "Nobody" <> wrote in message
    news:0hlXb.33481$1O.1549@fed1read05...
    > Thanks for the feedback John. Some good technical points here that I will
    > modify my code for and some style issues that are "to each his own" :).
    >
    > Ooops, in the code posted, the Find function was not implemented.
    >
    > Why make the GetElement, GetLeft and GetRight static? I understand they
    > operate on the node struct and not the tree itself, but does it add

    anything
    > to be static?
    >
    > If those methods were static, wouldn't I have to call them with some ugly
    > code like:
    >
    > CBinarySearchTree<int>::GetLeft(pos);
    >
    > or something of that nature? vs.
    >
    > tree.GetLeft(pos);
    >


    No, you can use EITHER syntax if the function is static. The point of making
    them static is that you can do node iteration without having the original
    tree.

    > I have always followed the belief of not making class functions or members
    > static. If a member function is static, it probably shouldn't be a member
    > function.


    Fair enough, although I wouldn't be as categorical as you are being. But in
    this case these three functions should be part of a seperate iterator class,
    but you've already ruled that out, so I thought making them static is the
    next best thing.

    It's going to get very tedious when writing functions that use GetLeft,
    GetRight and GetElement to always have to pass the tree itself to that
    function as well.

    >
    > Yes, I do need to implement a copy constructor as well.
    >
    > Again, thanks for the feedback, much appreciated.
    >


    john
     
    John Harrison, Feb 14, 2004
    #5
  6. Nobody

    Jon Willeke Guest

    size_t (was Re: comments on this Binary Searh Tree template?)

    John Harrison wrote:
    > Miscellaneous comments below
    >
    > "Nobody" <> wrote in message
    > news:%ZjXb.33476$1O.26297@fed1read05...
    >
    >> {
    >> TYPE element;
    >> _TREENODE* pLeft;
    >> _TREENODE* pRight;
    >> };
    >>protected:
    >> _TREENODE* m_pRoot;
    >> UINT m_nCount;

    >
    > Ditto unsigned not UINT. Actually probably should be size_t (64 bit
    > computing is round the corner, size_t will be a 64 bit type when it arrives)


    I noticed the following comment in gc.h from Hans Boehm's garbage
    collector: "[size_t] and [ptr_diff_t] appear to have incorrect
    definitions on many systems. Notably 'typedef int size_t' seems to be
    both frequent and WRONG." Comments?
     
    Jon Willeke, Feb 15, 2004
    #6
  7. Re: size_t (was Re: comments on this Binary Searh Tree template?)

    "Jon Willeke" <> wrote in message
    news:qNOXb.26724$...
    > John Harrison wrote:
    > > Miscellaneous comments below
    > >
    > > "Nobody" <> wrote in message
    > > news:%ZjXb.33476$1O.26297@fed1read05...
    > >
    > >> {
    > >> TYPE element;
    > >> _TREENODE* pLeft;
    > >> _TREENODE* pRight;
    > >> };
    > >>protected:
    > >> _TREENODE* m_pRoot;
    > >> UINT m_nCount;

    > >
    > > Ditto unsigned not UINT. Actually probably should be size_t (64 bit
    > > computing is round the corner, size_t will be a 64 bit type when it

    arrives)
    >
    > I noticed the following comment in gc.h from Hans Boehm's garbage
    > collector: "[size_t] and [ptr_diff_t] appear to have incorrect
    > definitions on many systems. Notably 'typedef int size_t' seems to be
    > both frequent and WRONG." Comments?


    I believe the standard requires size_t to be an unsigned integral type. Hans
    Boehm's garbage collector is very old. I doubt that many compilers get
    size_t wrong nowadays.

    john
     
    John Harrison, Feb 15, 2004
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Miguel Dias Moura

    How to create a searh in a database field?

    Miguel Dias Moura, Nov 24, 2004, in forum: ASP .Net
    Replies:
    3
    Views:
    380
    Jeff Dillon
    Nov 24, 2004
  2. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,127
  3. sharan
    Replies:
    4
    Views:
    690
    CBFalconer
    Oct 30, 2007
  4. sharan
    Replies:
    2
    Views:
    833
    SM Ryan
    Oct 31, 2007
  5. sharan
    Replies:
    1
    Views:
    691
    CBFalconer
    Oct 30, 2007
Loading...

Share This Page