Binary trees

Finally, we look at a data structure called a binary tree . Despite the fact that there are many different types of trees, binary trees play a special role, because in the sorted state they allow for very fast insertion, deletion and searching. Each element of a binary tree consists of an informational part and pointers to the left and right elements. In fig. 22.8 shows a small binary tree.

  root
                                ↙
                       + ------- +
                       | data |
                       + --- + --- +
       left |  |  |  right
      subtree + --- + --- + subtree
          ↙ ↘ ↙
            + ------- + + ------- +
            | data |  | data |
            + --- + --- + + --- + --- +
            |  |  |  |  0 |  |
            + --- + --- + + --- + --- +
          ↘ ↘
 + ------- + + ------- + + ------- +
 | data |  | data |  | data |
 + --- + --- + + --- + --- + + --- + --- +
 |  0 |  0 |  |  0 |  0 |  |  0 |  0 |
 + --- + --- + + --- + --- + + --- + --- +
       ↑ ↑
       '----------------leaves-----------------'

When discussing trees, special terminology is used. Programmers are not experts in the field of philology, and therefore the terminology used in graph theory (and trees are a special case of graphs!) Is a classic example of the misuse of words. The first element of the tree is called the root . Each data element is called a tree node (node), and any fragment of a tree is called a subtree . A node to which no subtrees are attached is called a final node or a leaf. The height (height) of the tree is equal to the maximum number of levels from root to leaf. When working with trees, we can assume that in memory they exist in the same form as on paper. But remember that a tree is just a way to organize data in memory in memory, and memory is linear.

In a sense, a binary tree is a special kind of linked list. Items can be inserted, deleted and retrieved in any order. In addition, the extraction operation is not destructive. Despite the fact that trees are easy to imagine in the imagination, a number of complex tasks are associated with them in programming theory. In this section, trees are affected only superficially.

Most functions that work with trees are recursive, because the tree is inherently a recursive data structure. In other words, each subtree, in turn, is a tree. Therefore, the functions developed here will be recursive. There are not recursive versions of these functions, but their code is much more difficult to understand.

The way in which the tree is organized depends on how it is subsequently accessed. The process of accessing each vertex of a tree one at a time is called tree traversal. Consider the following tree:

  d 
     ↙ ↘
    bf
  ↘ ↙ ↘
 aceg

There are three tree traversal orders: symmetric traversal , or inorder traversal, forward traversal, forward traversal, ordered traversal, traversing from above , or traversing in width (preorder) and traversing in reverse order, traversing in depth, reverse traversing , traversing the bottom (postorder). For symmetric traversal, the left subtree is processed first, then the root, and then the right subtree. For a direct walk, the root is processed first, then the left subtree, and then the right. When traversing the bottom, the left subtree is processed first, then the right subtree, and finally the root. The access sequence for each bypass method is shown below:

  Abcdefg symmetric bypass
 Direct bypass dbacfeg
 Crawling below acbegfd

Although the tree does not have to be ordered, most of the tasks use just such trees. Of course, the structure of an ordered tree depends on how it is traversed. In the remainder of this chapter, symmetric traversal is assumed. Therefore, an ordered binary tree will be considered such a tree in which the left subtree contains vertices less than or equal to the root, and the right contains vertices that are larger than the root.

The following stree () function creates an ordered binary tree:

  struct tree {
   char info;
   struct tree * left;
   struct tree * right;
 };

 struct tree * stree (
   struct tree * root,
   struct tree * r,
   char info)
 {
   if (! r) {
     r = (struct tree *) malloc (sizeof (struct tree));
     if (! r) {
       printf ("Out of memory \ n");
       exit (0);
     }
     r-> left = NULL;
     r-> right = NULL;
     r-> info = info;
     if (! root) return r;  / * first entry * /
     if (info <root-> info) root-> left = r;
     else root-> right = r;
     return r;
   }
   if (info <r-> info)
     stree (r, r-> left, info);
   else
     stree (r, r-> right, info);

   return root; 
 }

The above algorithm simply follows the links of the tree, moving to the left or right branch of the next vertex based on the contents of the info field until it reaches the insertion point of a new element. To use this function, you must have a global pointer variable to the root of the tree. This pointer must initially have a value of null ( NULL ). When first called, the stree () function returns a pointer to the root of the tree, which must be assigned to a global variable. On subsequent calls, the function continues to return a pointer to the root. Suppose that a global variable containing the root of a tree is called rt . Then the stree () function is called as follows:

  / * call the street function () * /
 rt = street (rt, rt, info);

The stree () function uses a recursive algorithm, like most procedures for working with trees. Exactly the same function, based on iterative methods, would be several times longer. The stree () function must be called with the following parameters (from left to right): a pointer to the root of the entire tree, a pointer to the root of the next subtree to be searched, and the data to be saved. When first called, both first parameters point to the root of the whole tree. For simplicity, single characters are stored in the tree tops. However, you can use any type of data instead.

To bypass the tree created by the stree () function in a symmetrical order and print out the info field at each vertex, you can use the following inorder () function:

  void inorder (struct tree * root)
 {
   if (! root) return;

   inorder (root-> left);
   if (root-> info) printf ("% c", root-> info);
   inorder (root-> right);
 }

This recursive function terminates when it finds the final node (null pointer).

The following listing shows functions that traverse the tree in width and depth.

  void preorder (struct tree * root)
 {
   if (! root) return;

   if (root-> info) printf ("% c", root-> info);
   preorder (root-> left);
   preorder (root-> right);
 }

 void postorder (struct tree * root)
 {
   if (! root) return;

   postorder (root-> left);
   postorder (root-> right);
   if (root-> info) printf ("% c", root-> info);
 }

Now let's look at a short but interesting program that builds an ordered binary tree, and then, bypassing it in a symmetric way, displays it sideways on the screen. To display the tree, you only need to slightly modify the inorder () function. Since the tree is printed sideways on the screen, in order to correctly display the right subtree it is necessary to print before the left one. (Technically, this is the opposite of symmetric traversal.) The new function is called printtree () , and its code is shown below:

  void print_tree (struct tree * r, int l)
 {
   int i;

   if (r == NULL) return;

   print_tree (r-> right, l + 1);
   for (i = 0; i <l; ++ i) = "" printf ("=" ""); = "" printf ("% c \ n", = "" r - = ""> info);
   print_tree (r-> left, l + 1);
 }

The following is the text of the entire tree printing program. Try introducing different trees to see how they are built.

  / * This program displays a binary tree.  * /

 #include <stdlib.h>
 #include <stdio.h>

 struct tree {
   char info;
   struct tree * left;
   struct tree * right;
 };

 struct tree * root;  / * initial tree top * /
 struct tree * stree (struct tree * root,
                    struct tree * r, char info);
 void print_tree (struct tree * root, int l);

 int main (void)
 {
   char s [80];

   root = NULL;  / * root tree initialization * /

   do {
     printf ("Enter the letter:");
     gets (s);
     root = stree (root, root, * s);
   } while (* s);

   print_tree (root, 0);

   return 0;
 }

 struct tree * stree (
   struct tree * root,
   struct tree * r,
   char info)
 {

   if (! r) {
     r = (struct tree *) malloc (sizeof (struct tree));
     if (! r) {
       printf ("Out of memory \ n");
       exit (0);
     }
     r-> left = NULL;
     r-> right = NULL;
     r-> info = info;
     if (! root) return r;  / * first entry * /
     if (info <root-> info) root-> left = r;
     else root-> right = r;
     return r;
   }

   if (info <r-> info)
     stree (r, r-> left, info);
   else
     stree (r, r-> right, info);

   return root;
 }

 void print_tree (struct tree * r, int l)
 {
   int i;

   if (! r) return;

   print_tree (r-> right, l + 1);
   for (i = 0; i <l; ++ i) = "" printf ("=" ""); = "" printf ("% c \ n", = "" r - = ""> info);
   print_tree (r-> left, l + 1);
 }

Essentially, this program sorts the input information. The sorting method is one of the varieties of sorting by the method of inserts, which was discussed in the previous chapter. On average, performance can be quite good.

If you run a tree printing program, you probably noticed that some trees are balanced (i.e., balanced). each subtree has approximately the same height as the others, and some trees are very far from this state. For example, the tree a ⇒ b ⇒ c ⇒ d looks like this:

  a
  ↘
    b
     ↘
       c
        ↘
          d

There are no left subtrees in this tree. Such a tree is called degenerate , since in fact it degenerated into a linear list. In the general case, if the input data is random when building a tree, the resulting tree is close to balanced. If the information is pre-sorted, a degenerate tree is created. (Therefore, sometimes with each insertion, the tree is adjusted so that it is balanced, but this process is rather complicated and is beyond the scope of this chapter.)

In binary trees, search functions are easily implemented. The following function returns a pointer to the top of the tree, in which the information matches the search key, or zero ( NULL ) if there is no such vertex.

  struct tree * search_tree (struct tree * root, char key)
 {
   if (! root) return root;  / * empty tree * /
   while (root-> info! = key) {
     if (keyinfo) root = root-> left;
     else root = root-> right;
     if (root == NULL) break;
   }
   return root;
 }

Unfortunately, removing a tree top is not as easy as finding it. The removed vertex can be either a root, or a left, or a right vertex. In addition, subtrees can be attached to the top (the number of attached subtrees can be 0, 1, or 2). The process of reinstalling pointers is suggested by the recursive algorithm below:

  struct tree * dtree (struct tree * root, char key)
 {
   struct tree * p, * p2;

   if (! root) return root;  / * vertex not found * /

   if (root-> info == key) {/ * root removal * /
     / * it means an empty tree * /
     if (root-> left == root-> right) {
       free (root);
       return NULL;
     }
     / * or if one of the subtrees is empty * /
     else if (root-> left == NULL) {
       p = root-> right;
       free (root);
       return p;
     }
     else if (root-> right == NULL) {
       p = root-> left;
       free (root);
       return p;
     }
     / * or there are both subtrees * /
     else {
       p2 = root-> right;
       p = root-> right;
       while (p-> left) p = p-> left;
       p-> left = root-> left;
       free (root);
       return p2;
     }
   }
   if (root-> info <key) root-> right = dtree (root-> right, key);
   else root-> left = dtree (root-> left, key);
   return root;
 }

You must also ensure that the pointer to the root of the tree described outside this function is updated correctly, since the vertex to be deleted may be the root. It is best for this purpose to assign a pointer to the root to the value returned by the dtree () function:

  root = dtree (root, key); 

Binary trees are an extremely powerful, flexible and effective tool. Since when searching in a balanced tree, log ₂ n comparisons are performed in the worst case, it is much better than a linked list, in which only sequential search is possible.