NOTE: The algorithm given in The Essential of Data Structures makes use of one loop to find the proper location at which to insert a new node. At each pass of the loop, a test is made to determine whether the current node has a child, in which the looping continues, or whether the data should be inserted at that point in a new node.
In contrast, the algorithm presented in F&T separates the "searching" aspect from the "insertion" aspect of the code. The loop to find the proper location occurs in the code first. Then a node is created and linked to the proper place (as the new left or right child).
The cases are enumerated differently in the two books (as to be expected).
The following code implements an inorder traversal of a threaded tree. The advantage of this code (in comparison with more typical implementation) is that it avoid recursion and thus is usually more efficient, though the data structure for each node is slightly more complicated.
We assume the node has an extra field called rthread which is TRUE (i.e., 1) if the right pointer actually is a thread pointing to an ancestor rather than a link to a child.
void intraversal(node * tree)
{
node * p, * q;
p = tree;
do {
q = NULL;
while (p != NULL) { // traverse left branch
q = p; // q is the parent of p
p = p->left;
}
// after reaching a NULL left pointer,
// print out the parent info and move right
if (q != NULL) {
cout << q->info << endl;
p = q->right;
while ( q->rthread && p != NULL) {
cout << p->info << endl;
q = p;
p = p->right;
}
}
} while (q != NULL)
}
This page is maintained by Dennis C. Smolarski, S.J.
© Copyright 1998, 1999 Dennis C. Smolarski, SJ, All rights reserved.
Last changed: 7 April 1999.