0.5 Binary search trees  (Page 3/4)

There are several cases to be considered:

• Deleting a leaf: Deleting a node with no children is easy, as we can simply remove it from the tree.
• Deleting a node with one child: Delete it and replace it with its child.
• Deleting a node with two children: Suppose the node to be deleted is called N. We replace the value of N with either its in-order successor (the left-most child of the right subtree) or the in-order predecessor (the right-most child of the left subtree).

Once we find either the in-order successor or predecessor, swap it with N, and then delete it. Since both the successor and the predecessor must have fewer than two children, either one can be deleted using the previous two cases. In a good implementation, it is generally recommended to avoid consistently using one of these nodes, because this can unbalance the tree.

Here is C++ sample code for a destructive version of deletion. (We assume the node to be deleted has already been located using search.)

void DeleteNode(struct node *&node) {

if (node->left == NULL) {

struct node *temp = node;

node = node->right;

delete temp;

} else if (node->right == NULL) {

struct node *temp = node;

node = node->left;

delete temp;

} else {

// In-order predecessor (rightmost child of left subtree)

// Node has two children - get max of left subtree

struct node **temp =&node->left; // get left node of the original node

// find the rightmost child of the subtree of the left node

while ((*temp)->right != NULL) {

temp =&(*temp)->right;

}

// copy the value from the in-order predecessor to the original node

node->value = (*temp)->value;

// then delete the predecessor

DeleteNode(*temp);

}

}

Although this operation does not always traverse the tree down to a leaf, this is always a possibility; thus in the worst case it requires time proportional to the height of the tree. It does not require more even when the node has two children, since it still follows a single path and does not visit any node twice.

5.2.4. traversal

(From Wikipedia, the free encyclopedia)

Compared to linear data structures like linked lists and one dimensional arrays , which have only one logical means of traversal, tree structures can be traversed in many different ways. Starting at the root of a binary tree, there are three main steps that can be performed and the order in which they are performed define the traversal type. These steps are: Performing an action on the current node (referred to as "visiting" the node); or repeating the process with the subtrees rooted at our left and right children. Thus the process is most easily described through recursion .

To traverse a non-empty binary tree in preorder, we perform the following three operations: 1. Visit the root. 2. Traverse the left subtree in preorder. 3. Traverse the right subtree in preorder.

To traverse a non-empty binary tree in inorder, perform the following operations: 1. Traverse the left subtree in inorder. 2. Visit the root. 3. Traverse the right subtree in inorder.

To traverse a non-empty binary tree in postorder, perform the following operations: 1. Traverse the left subtree in postorder. 2. Traverse the right subtree in postorder. 3. Visit the root. This is also called Depth-first traversal