Need soem suggestions on my Binary Search Tree Implementation

I am implementing a binary search tree, and using non-recursive techniques in most of the algorithms. I think I finally have my deletion down, and considered several forms of a tree when a node is deleted that may cause problems for the non-recursive solutions. The one thing I'm having trouble with is non-recursive traversals (in-order, post-order, pre-order). Is it practical to devise a non-recursive algorithm for such functions. Also, is my delete function missing anything? I'm trying to get this down pat before I move on to R/B trees or AVL trees.

I'd say a non-recursive traversal algorithm is the most important of all, because you need it to implement iterator-style access.

The only problem I'm having in planning it out is would I have to make "doubly linked" nodes because the tree traversals eventually have to backtrack

>would I have to make "doubly linked" nodes because the tree traversals eventually have to backtrack
No, but you do need to store the backtracking data somehow. Another option is to save the nodes in a stack.

yeah, i thought of that soon before I saw your post. The iterator class would have a stack of addresses, starting from the root and pushing on each iterator dependign on the operation executed (child 0 for --, child 1 for ++), and pop it to go back up the chain. Makes more sense than what I was doing. I'm wondering if I could use this method to do a more generalized deletion algorithm, because now it seems like I'm just looking at all these possibilities rather than have the general rules (if a node has a child, then do this to the right subtree). But either way I got what I should do. Thanks for the info.

and your sig is so right.

>Makes more sense than what I was doing.
There are downsides to a stack too, but it's a fantastic way to iteratively walk a tree without having to add extra storage and maintenance logic to the tree itself. If you want to see something that already exists, my tutorials cover non-recursive iteration, and the tree libraries implement it using a stack.

>I'm wondering if I could use this method to do a more generalized deletion algorithm
If you're not doing any balancing, the deletion algorithm should be pretty simple. Even the most complex case is straightforward, so I'm guessing that you're over complicating things. ;)

Eventually I'm going to do balancing when I implement other trees, and just want to know how I can improve what I have for later use.

>Eventually I'm going to do balancing when I implement other trees
All the more reason to keep the basic algorithms as simple as possible. :)

What I'm really getting at is, is the one I posted "BSTree.h" simple ;b

I think you're (potentially), missing a lot of nodes in your clear method. Shouldn't you have to traverse through the branches and delete all nodes rather than just delete-ing the root?

Quote:

---

Originally Posted by twomers

I think you're (potentially), missing a lot of nodes in your clear method. Shouldn't you have to traverse through the branches and delete all nodes rather than just delete-ing the root?

---

The desturctor for the Node class iterates through it's children array and deletes them, so if I delete the root, it will call the destructor for it's children, which delete it's children.

Code:

---

    virtual ~Node()
    {
        for(size_t i = 0; i < size; ++i)
            delete child[i];
    }

---

>is the one I posted "BSTree.h" simple ;b
Gah, you're going to make me look at it, aren't you? ;)

I like that you're using the link array instead of symmetric cases, but you do know that a relational operation is required to return 0 or 1, right? You don't have to use the conditional operator for setting dir.

For Delete, you can merge the zero and one child cases into a single case:

Code:

---

// The two child case goes here
}
else {
  // One or both children are null
  int replace = ( next->child[0] == NULL );

  if (next == root)  //delete if data is at root
    root = next->child[replace];
  else
    prev->child[dir] = next->child[replace];

  delete next;
}

---

Even if next->child[replace] is NULL, you still get the correct behavior. Also, you don't need to set next->child[replace] to NULL in any of the three cases because next is going to be immediately deleted. It doesn't matter what the value of any of its members is.

Thanks for that tip. Though I do have to replace the child to null because of the node's destructors. They traverse the child array and delete any children it's linked to. So if I have to link a node a child of the node to be deleted, then delete the node without disconnecting it from it's child, I will have inadvertently deleted two or more nodes, since the destructor will delete the nodes below it, if it's the case they aren't null. I don't know if it was wise but it made destroying the entire tree easier.

And a lot of my code is verbose for the sake of me being explicit. I don't like having to go back and pen-n-paper my code to understand the logic (regarding using relational operators return values). In simple cases it's easy enough to udnerstand, but once I start using them a lot I miss my own logic sometimes.

ok my delete function has been washed and waxed as follows

Code:

---

template <typename T>
void BSTree<T>::Delete(T x)
{
    if (root == NULL)
    {
        std::cout << "-- Tree is empty --" << std::endl;
        return;
    }

    BinaryTreeNode<T>* next = root;    //points ahead
    BinaryTreeNode<T>* prev = next;    //points to previous node
    size_t dir = 0;                //stores pointer direction

    //search for the data to be replaced
    while(next->data != x)
    {
        prev = next;
        dir = next->data < x;
        next = next->child[dir];
    }

    //if there are two child nodes
    if(next->child[0] != NULL && next->child[1] != NULL)
    {
        //point to the root of right subtree
        BinaryTreeNode<T>* right = next->child[1];
        BinaryTreeNode<T>* rNext = right->child[0];

        //right is the leastmost node in subtree
        if(rNext == NULL)
        {
            next->data = right->data;
            next->child[1] = right->child[1];
            right->child[1] = NULL;
            delete right;
        }
        else    //otherwise find leastmost node
        {
            while(rNext->child[0] != NULL)
            {
                right = rNext;
                rNext = rNext->child[0];
            }

            //move subtrees upward to right's left tree
            next->data = rNext->data;
            right->child[0] = rNext->child[1];
            rNext->child[1] = NULL;
            delete rNext;
        }
    }
    else    //there is either none or one child node
    {
        //child to be moved to
        size_t replace = (next->child[0] == NULL);

        if(next == root)
        {
            root->data = root->child[replace];
            root->child[replace] = NULL;
        }
        else
        {
            prev->child[dir] = next->child[replace];
            next->child[replace] = NULL;
        }
    }
    std::cout << "-- " << x << " has been Deleted -- " << std::endl;
}

---

blech, didn't work.