A binary search tree works greatest when code is on the market to go looking the tree. Earlier than doing so, I’d wish to reveal how a tree is processed, one node at a time.
Persevering with from final week’s Lesson, to go to every node within the tree you have to traverse the tree, plumbing its depths. I name this operate traverse():
void traverse(struct node *r)
{
if( r==NULL )
return;
printf("%dn",r->key);
traverse(r->proper);
traverse(r->left);
}
As with the add_node() operate, traverse() is recursive. When a NULL node is encountered, indicating an empty merchandise, the operate returns. In any other case, it fetches a key worth from the node after which traverses first the proper branches after which the left branches within the tree. Ultimately, all values are output, although in a fashion that dominates the proper branches (as a result of the proper node is inspected first).
Right here’s pattern output from the up to date code, obtainable on GitHub:
50
85
96
59
68
20
41
16
3
Examine this output with the way in which the information is saved internally, which is illustrated in Determine 1. You’ll be able to see how the output favors climbing down the proper branches first.
Determine 1. A Binary Search Tree.
In case you change the order of the traverse() recursive name, placing the traverse(r->left) assertion first, the output seems in a unique order. Regardless, these capabilities are used extra correctly to seek for information than to output an correct illustration of the tree.
The second enchancment to the unique code I promised is to free the allotted nodes earlier than this system quits. As with all a program’s allotted storage, nodes are freed mechanically when this system ends. Nonetheless, C coders are persnickety (as they need to be) on the subject of liberating reminiscence.
To de-allocate the binary search tree’s storage, I added the free_tree() operate to the pattern code:
void free_tree(struct node *r)
{
if( r==NULL )
return;
free_tree(r->left);
free_tree(r->proper);
free(r);
}
As it’s possible you’ll suspect, this operate can also be recursive. It seeks the bottom-most (top-most?) node within the tree and frees it, free(r). This operate is added to the tip of the predominant() operate and is on the market on GitHub right here.
The following process is to go looking the tree for a particular tidbit of information. I current this addition to the code in subsequent week’s Lesson.
