You get a bonus - 1 coin for daily activity. Now you have 1 coin

4. Recursive data structures

Lecture



Consider recursive algorithms and recursive data structures.

Recursion is a process, the flow of which is associated with appeal to oneself (to the same process).

An example of a recursive data structure is a data structure whose elements are the same data structures (Fig. 4.1).


  4. Recursive data structures


4.1 Trees




Tree is a non-linear bound data structure
(Fig. 4.2).


  4. Recursive data structures


The tree is characterized by the following features:

- The tree has 1 element that is not referenced by other elements. This element is called the root of the tree;

- in the tree, you can access any element by passing a finite number of links (pointers);

- each element of the tree is associated with only one previous element. Any node of the tree can be either intermediate or terminal (leaf). In fig. 4.2 intermediate elements are M1, M2, leaves - A, B, C, D, E. A characteristic feature of the terminal node is the absence of branches.

Height is the number of levels of the tree. At the tree in fig. 4.2 height is two.

The number of branches growing from a tree node is called the degree of outcome of the node (in Fig. 4.2 for M1, the degree of outcome is 2, for M2 - 3). By degree of outcome trees are classified:

1) if the maximum degree of outcome is m, then this is an m-ary tree;

2) if the degree of outcome is either 0 or m, then this is a complete m-ary tree;

3) if the maximum degree of outcome is 2, then this is a binary tree;

4) if the degree of outcome is either 0 or 2, then this is a complete binary tree.

The following terminology is also used to describe the connections between the nodes of the tree: M1 is the “father” for elements A and B. A and B are the “sons” of the node M1.

4.1.1 Representation of trees




  4. Recursive data structures


The most convenient trees to represent in the memory of a computer in the form of linked lists. The list element should contain information fields that contain the node value and the degree of outcome, as well as pointer fields, the number of which is equal to the degree of outcome (Fig. 4.3). That is, any element pointer orients this node element with the sons of this node.  

4.2 Binary trees



Binary trees are the most commonly used tree species.

According to the representation of trees in the computer memory, each element will be a record containing 4 fields. The values ​​of these fields will be respectively the key of the record, the link to the element left-down, the element to the right-down and the text of the record.

When building it is necessary to remember that the left son has a key smaller than that of the father, and the key value of the right son is greater than the key value of the father. For example, we build a binary tree of the following elements: 50, 46, 61, 48, 29, 55, 79. It has the following form:


  4. Recursive data structures


We got an ordered binary tree with the same number of levels in the left and right subtrees. This is a perfectly balanced tree, that is, a tree in which the left and right subtrees have levels that differ by no more than one.

To create a binary tree, you need to create elements of the type in memory (Fig. 4.5):


  4. Recursive data structures


Operation V = MakeTree (Key, Rec) - creates an element (tree node) with two pointers and two fields (key and informational).


Type of MakeTree procedure:

Pseudocode

p = getnode

r (p) = rec

k (p) = key

v = p

left (p) = nil

right (p) = nil

Pascal

New (p);

p ^ .r: = rec;

p ^ .k: = key;

v: = p;

p ^ .left: = nil;

p ^ .right: = nil;



4.2.1 M-ary tree reduction to binary


Informal algorithm:


1. In any node of the tree, all branches are cut off, except the leftmost one, corresponding to the eldest sons.

2. The horizontal lines are all the sons of the same parent.

3. The eldest son in any node of the resulting structure will be the node under the given node (if any).

The sequence of actions of the algorithm is shown in Fig. 4.6.


  4. Recursive data structures


  4. Recursive data structures


  4. Recursive data structures


    1. Basic tree operations



1. Bypassing the tree.

2. Delete the subtree.

3. Insert a subtree.


To perform a tree walk , you must perform three procedures:

1. Processing of the root.

2. Processing of the left branch.

3. Processing of the right branch.


Depending on the sequence in which these three procedures are performed, there are three types of workarounds.

1. Turning from top to bottom. Procedures are performed in sequence.

1-2-3.

2. Turn left to right. Procedures are performed in sequence.

2 - 1 - 3.

3. Turning up from the bottom. Procedures are performed in sequence.

2 - 3 -1.


Depending on which entry in the node leads to the processing of the node, it turns out the implementation of one of the three types of bypass. If the processing goes after the first entry into the node, then from top to bottom, if after the second, then from left to right, if after the third, then from bottom to top (see. Fig. 4. 7).


  4. Recursive data structures


The operation to exclude a subtree. You must specify the node to which the excluded subtree is connected and the index of this subtree. The exception of a subtree is that the connection with the excluded subtree is broken, i.e. the element pointer is set to nil, and the outcome of this node is reduced by one.

Inserting a subtree is the inverse operation of an exception. You need to know the index of the included subtree, the node to which the tree is suspended, set the pointer of this node to the root of the subtree, and the degree of outcome of this node is increased by one. In this case, it is generally necessary to renumber the sons of the node to which the subtree is suspended.

The insertion and deletion algorithm is discussed in Chapter 5.

4.2.3 Algorithm for creating a binary search tree


Let the elements with the keys be set: 14, 18, 6, 21, 1, 13, 15. After executing the algorithm below, you will get the tree shown in Fig.4.6. If we go around the resulting tree from left to right, we get the ordering: 1, 6, 13, 14, 15, 18, 21.

  4. Recursive data structures


Pseudocode


read (key, rec)

tree = maketree (key rec)

p = tree

q = tree

while not eof do

read (key, rec)

v = maketree (key, rec)

while p <> nil do

q = p

if key <k (p) then

p = left (p)

else

p = right (p)

endif

endwhile

if key <k (q) then

left (p) = v

else

right (p) = v

endif

if q = tree then

'root only'

endif

return

Pascal


read (key, rec);

tree: = maketree (key rec);

p: = tree;

q: = tree;

while not eof do

begin

read (key, rec);

v: = maketree (key, rec);

while p <> nil do

begin

q: = p;

if key <p ^ .k then

p: = p ^ .left

else

p: = p ^ .right;

end;

if key <q ^ .k then

p ^ .left: = v

else

p ^ .right: = v;

end

if q = tree

then writeln ('Root only');

exit




4.2.4 Passage of binary trees


Depending on the sequence of traversing subtrees, there are three types of traversing (passing) of trees (Fig.4.9):


  4. Recursive data structures


1. From top to bottom A, B, C.

2. From left to right or symmetrical passage B, A, C.

3. Bottom up B, C, A.


The second method is most often used.

Below are the recursive algorithms for passing binary trees.


subroutine pretrave (tree) 'top to bottom

if tree <> nil then

print info (tree)

pretrave (left (tree))

pretrave (right (tree))

endif

return


subroutine intrave (tree) 'symmetrical

if tree <> nil then

intrave (left (tree))

print info (tree)

intrave (right (tree))

endif

return


Procedure pretrave (tree: tnode)

Begin

if tree <> nil then

begin

WriteLn (Tree ^ .Info);

Pretrave (Tree ^ .left);

Pretrave (Tree ^ .right);

End;

end;


procedure intrave (tree: tnode)

begin

if tree <> nil then

begin

intrave (Tree ^ .left);

writeLn (Tree ^ .info);

intrave (Tree ^ .right);

end;

end;


  4. Recursive data structures

Let us explain in more detail the recursion of the tree traversal algorithm from left to right.

Number the algorithm strings.   intrave ( tree ):


  1. if tree <> nil

  2. then intrave (left (tree))

  3. print info (tree)

  4. intrave (right (tree))

  5. endif

  6. return



Denote pointers: ttree; lleft; rright

In the above figure. 4.11 illustrates the sequence of calling the intrave ( tree ) procedure as you traverse the nodes of the simplest tree shown in Figure. 4. 10.


  4. Recursive data structures


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Structures and data processing algorithms.

Terms: Structures and data processing algorithms.