View source for Epita:Algo:Course:Info-Sup:Trees Structures

A '''tree''' is a set of '''nodes''' storing elements in a '''parent-child''' relationship with different properties.
 
== Binary trees ==

A binary tree is a recursive structure. It is either a null tree '''''( Ø )''''', or a tree that contains a root node and at most two subtrees ( '''''< o, G, D >''''' ) where '''o''' is the root node and '''L''' and '''R''' are two distinct subtrees (respectively left subtree and right subtree).

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:drawing_binary_tree_example.png|250px| ''Graphical example of binary tree'']]
|+ '''Figure 1. Graphical example of binary tree.'''
|}

<br/>

In this example, we have numbered each node to differentiate them. Something important to note is that a binary tree is not necessarily symmetric.

''<u>Remark:</u> by convention, trees are drawn growing downwards.''

<br/>

===''Binary tree'' Algebraic Abstract Type ===

 '''types'''<br/>
    binarytree<br/>
 '''uses'''<br/>
    node, <span style="color:#0000FF;">element</span><br/><br/>
 '''operations'''<br/>
    emptytree : <math>\rightarrow</math> binarytree
      <_,_,_> : node x binarytree x binarytree <math>\rightarrow</math> binarytree
         root : binarytree <math>\rightarrow</math> node
            l : binarytree <math>\rightarrow</math> binarytree
            r : binarytree <math>\rightarrow</math> binarytree
      <span style="color:#0000FF;">content : node <math>\rightarrow</math> element</span><br/>
 '''preconditions'''<br/>
    root(''B'') is-defined-iaoi ''B'' ≠ emptytree
    l(''B'') is-defined-iaoi ''B'' ≠ emptytree
    r(''B'') is-defined-iaoi ''B'' ≠ emptytree<br/>
 '''axioms'''<br/>
    root (<''r,L,R''>)=''r''
    l(<''r,L,R''>)=''L''
    r(<''r,L,R''>)=''R''<br/>
 '''with'''
    node r
    binarytree B,L,R

''We can notice in <span style="color:#0000FF;">blue</span> the necessary operation to get the content of a node. This operation is necessary for a '''Labeled tree'''.''


<br/>

====Terminology====

The handling of binary trees requires the use of appropriate vocabulary.
The main elements are:

let <tt><r,L,R></tt> be the binary tree <tt>B</tt><br/>

* <tt>r</tt> is the '''root''' of <tt>B</tt>, with no parent node
* <tt>L</tt> is the '''left subtree''' of <tt>B</tt>
* <tt>R</tt> is the '''right subtree''' of <tt>B</tt>
* we call '''left child''' ('''''right child''''') of the node <tt>n<sub>i</sub></tt> the root node of the left subtree (''right subtree'') of the tree rooted by <tt>n<sub>i</sub></tt>
* the link from a parent to a child is called '''directed-edge'''. If it is to the left child (''right child''), we call it the '''left link''' ('''''right link''''')
* if a node <tt>n<sub>j</sub></tt> is the child of a node <tt>n<sub>i</sub></tt>, we say that <tt>n<sub>i</sub></tt> is the '''parent''' of <tt>n<sub>j</sub></tt>
* Two nodes that are children of the same parent are '''siblings'''
* A node <tt>n<sub>i</sub></tt> is an '''ancestor''' of a node <tt>n<sub>j</sub></tt> if it exists on the path from the root to node <tt>n<sub>j</sub></tt> (''if <tt>n<sub>i</sub></tt> is either the parent of <tt>n<sub>j</sub></tt> or an ancestor of the parent of <tt>n<sub>j</sub></tt>''). 
* Conversely, we say that a node <tt>n<sub>i</sub></tt> is a '''descendant''' of a node<tt>n<sub>j</sub></tt> if <tt>n<sub>j</sub></tt> is the '''ancestor''' of <tt>n<sub>i</sub></tt> (''if <tt>n<sub>i</sub></tt> is either the child of <tt>n<sub>j</sub></tt> or a descendant of the child of <tt>n<sub>j</sub></tt>'').
* each node has at most two child nodes
* if a node has one left child (''right child''), it is a '''left (''right'') single internal node'''
* if a node has two children, it is a '''double internal node'''
* A node is an '''external node''' if it has no children. It is also called a '''leaf'''
* A path from the root to a leaf is called a '''branch'''
* A binary tree has as many branches as leaves
* the path obtained by following just the left links (''right links'') is called '''left edge''' ('''''right edge''''') of <tt>B</tt><br/>

<br/>

<u>''Remarks:</u> Unlike in real life, binary trees are not varieties of evergreens or deciduous. When I want to delete a leaf, I do. But the most amazing thing is that I create a (leaf) whenever I want. We also forget the notions of family and kinship.'' 

<br/>

====Properties of binary trees====

Now we will see operations on trees that calculate various measures and then determine the complexity of algorithms applied to them (the trees of course, what are we talking about ?).

These operations are the following :

* '''The size of a tree ''B''''' is the number of nodes of this tree, which is defined by:

{| border="0" cellpadding="3" align="left"
| align="right" rowspan="2" | '''''S(B)='''''
| rowspan="2" |  <math>\Bigg\{</math>
| align="left" | ''0'' 
| align="left" | if '''B''' is a null tree (''empty'')
|-
| align="left" | ''1+S(l('''B'''))+S(r('''B'''))'' 
| align="left" | otherwise
|}

<br/>

* '''The depth (''level'', ''height'') of a node <tt>x</tt> of a tree <tt>B</tt>''' is the distance from the node to the root of the tree, it's defined by :

{| border="0" cellpadding="3" align="left"
| align="right" rowspan="2" | '''''D(x)='''''
| rowspan="2" |  <math>\Bigg\{</math>
| align="left" | ''0'' 
| align="left" | if '''x''' is the root of '''B'''
|-
| align="left" | ''1+D('''y''')'' 
| align="left" | if '''y''' is the parent of '''x'''
|}

<br/>

* '''The height (''order'') of a tree <tt>B</tt>''' is the maximum depth of any node from the root. ''If a tree has only one node (the root), the height is zero. The height of an empty tree is not defined but could be considered as -1''. The height of a tree <tt>B</tt> is specified by:

'''''H(B)''''' = max(H('''x''')) where '''x''' are the nodes of '''B'''

<br/>

* '''The path Length (''sum of the depth of all the nodes'') of a tree ''B''''' that is defined by:

'''''PL(B)''''' = <math>\Sigma</math>D('''x''') where '''x''' are all the nodes of '''B'''

<br/>

* '''The external path length (''sum of the depth of all the external nodes'') of a tree ''B''''' that is defined by:

'''''EPL(B)'''''=<math>\Sigma</math>D('''xe''') where '''xe''' are only the external nodes (''leaves'') of '''B'''

<br/>

* '''The internal path length (''sum of the depth of all the internal nodes'') of a tree ''B''''' that is defined by:

'''''IPL(B)'''''=<math>\Sigma</math>D('''xi''') where '''xi''' are only the internal nodes of '''B'''

<br/>
then we have the following relation : '''PL(B)=EPL(B)+IPL(B)'''

<br/>

* '''The average depth of a tree ''B''''' that is defined by:

'''''AD(B)'''''=PL(B)/S(B) 

<br/>

* '''The external average depth of a tree ''B''''' that is defined by:

'''''EAD(B)'''''=EPL(B)/Nbe where '''Nbe'''  is the number of external nodes of '''B'''

<br/>

* '''The internal average depth of a tree ''B''''' that is defined by:

'''''IAD(B)'''''=IPL(B)/Nbi where '''Nbi'''  is the number of internal nodes of '''B'''

<br/>

''<u>Note :</u> Measures like '''path length''' and '''average depth''' will be very useful to determine the complexity of algorithms applied to binary trees.''<br/>

To clarify this, we will use the tree of Figure 1 and specify its characteristics and measurements. For this we will call this tree '''B''' and will retain the numbering of the nodes, which gives:

{| border="1" cellpadding="10" align="center"
| align="left" | 
- '''1''' is the root of '''B''', '''2''' is its left child and '''3''' its right child<br>
- siblings are : ('''2''','''3'''), ('''4''','''5'''), ('''6''','''7'''), ('''9''','''10'''), ('''12''','''13''')<br>
- '''1''', '''2''', '''3''', '''5''' et '''7''' are "double" internal nodes of '''B'''<br>
- '''4''' is a "left single" internal node of '''B'''<br>
- '''6''', '''8''' and '''9''' are "right single" internal nodes of '''B'''<br>
- <span style="color:#FFD700;">'''10''', '''11''', '''12''', '''13''', '''14''' and '''15'''</span> are leaves of '''B'''<br>
- ('''1''', '''2''', '''4''', '''8''') and ('''1''', '''3''', '''7''', '''13''') are the left and right edges of '''B'''<br>
- ('''1''', '''2''', '''4''', '''8''', '''14'''), '''1''', '''2''', '''5''', '''9''', '''15'''), ('''1''', '''2''', '''5''', '''10'''), ('''1''', '''3''', '''6''', '''11'''), ('''1''', '''3''', '''7''', '''12''') and ('''1''', '''3''', '''7''', '''13''') are branchs of '''B'''<br>
|-
| align="center" |[[Image:drawing_binary_tree_measures.png|500px| ''Representation of some measures of a binary tree'']]
|-
| align="left" | 
- the nodes' depth of '''B''' are :<br>
0 for node '''1''', 1 for nodes '''2''' and '''3''', 2 for nodes '''4''', '''5''', '''6''' and '''7''', 3 for nodes '''8''', '''9''', '''10''', '''11''', '''12''' and '''13''',<br>
4 for nodes '''14''' and '''15'''<br>
- the height of '''B''' is H(B)='''4'''<br>
- the size of '''B''' is S(B)='''15'''<br>
- the sums of path length and average depths of '''B''' are :<br>
PL(B)=36, <span style="color:#0000FF;">AD(B)=36/15 <math>\simeq</math> 2,4</span>, IPL(B)=16, <span style="color:#00FF00;">IAD(B)=16/9 <math>\simeq</math>  1,78</span>, EPL(B)=20, <span style="color:#FF0000;">EAD(B)=20/6 <math>\simeq</math>  3,33</span><br>
|+ '''Figure 2. Some measures of the Figure 1 binary tree.'''
|}

<br/>
<br/>

====Particular binary trees====

There are particular forms of binary trees. Knowing their specificities allow us to improve the algorithms on these trees using specific algorithms for their structure.

These trees are shown in figure 3 :

<br/>

{| border="0" cellpadding="3" align="center"
| align="center" colspan="4" | '''''Figure 3. Particular binary trees.'''''
|-
| align="center" | Perfect [[Image:drawing_binary_tree_perfect.png|250px| ''Perfect binary tree'']] 
| align="center" | Complete [[Image:drawing_binary_tree_complete.png|232px| ''Complete binary tree'']] 
|-
| align="center" | Full or proper [[Image:drawing_binary_tree_fullorproper.png|220px| ''Full or proper binary tree'']] 
| align="center" | Degenerate or filiform [[Image:drawing_binary_tree_degenerateorfiliform.png|80px| ''Degenerate of filiform tree'']] 
|}

<br/>

*  A '''degenerate (''filiform'') tree ''' is a tree in which for each parent node, there is only one associated child node. This means that in a performance measurement, the tree will behave like a linked list data structure.
* A '''perfect binary tree''' is a ''full binary tree'' in which all ''leaves'' are at the same ''depth'' or same ''level'', and in which every parent has two children.(''This is ambiguously also called a '''complete binary tree'''.'')
* A '''complete binary tree''' is a binary tree in which every level, except possibly the last, is completely filled. At the deepest level, the ''height'' of the tree, all nodes are as far left as possible.
* A '''full (''proper binary'') binary tree''' is a tree in which every node has zero (''the leaves'') or two children. Sometimes a full tree is ambiguously defined as a perfect tree. There exist particular ''full binary trees'' which are called '''right (''left'') comb''' in which all ''left (right) child'' are leaves.

<br/>

''<u>Note:</u> This terminology often varies in the litterature, especially with the meaning of "complete" and "full".''

<br/>

====Occurrence and hierarchical numbering====

Another way to describe a binary tree is to attribute to each node a word constructed with "0" and "1". This word is named '''occurrence'''. By definition the root node is "E" and if a node has for occurrence "m", its left and right children have respectively  the occurrences "m0" and "m1".

For the figure 1 tree called '''B''', we would have:

'''''B={E, 0, 1, 00, 01, 10, 11, 000, 010, 011, 101, 110, 111, 0001, 0101}'''''

Binary trees can also be represented in breadth-first order. In this arrangement which is called '''hierarchical numbering''', if a node is numbered <math>i</math>, its children are numbered <math>2*i</math> (for the left child) and <math>2*i+1</math> (for the right), while its parent is (if any) numbered <math>i/2</math> (assuming the root is numbered <math>one</math>).

For the example of figure 1 this would give : 

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:drawing_binary_tree_occurrence.png|300px| ''Occurrence representation of a binary tree'']]
| [[Image:drawing_binary_tree_hierarchical.png|300px| ''Hierarchical numbering of a binary tree'']]
|+ '''Figure 4. Occurrence and hierarchical numbering representations of the binary tree of the figure 1.'''
|}

<br/>

<u>''Note:</u> We will see later that the ''hierarchical numbering'' is very interesting on particular binary trees for an ''array implementation''.''

<br/>

===Implementations of binary trees===

Like the elementary structures, we have the possibility to implement in memory the trees  using dynamic or static representation. The latter may be used to simulate the former.


==== pointer-based implementation ====

This representation is virtually a layer of a binary tree. Each node contains an element (label) and two links: one to the left child and the other to the right child. It gives:


 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...                <span style="color:#00FF00;">/* Definition of element type */</span>
    t_tree = <math>\uparrow</math>t_node               <span style="color:#00FF00;">/* Definition of t_tree type (pointer on t_node) */</span>
    t_node = '''record'''                <span style="color:#00FF00;">/* Definition of t_node type */</span>
       t_element elt
       t_tree   lc, rc
    '''end record''' t_node<br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_tree tree

This will give the following structure:

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:binary_tree_type_pointerbased.png|500px| ''Pointer-based implementation of the binary tree in figure 1'']]
|+ '''Figure 5. Pointer-based implementation of the binary tree in figure 1.'''
|}

<br/>

In this kind of implementation, the correspondences between the abstract operations and the pointer-based implementation (''on a '''B''' binary tree'') are the following:

<br/>

{| border="0" cellpadding="5" align="center"
| align="right" | '''<u>Abstract type</u>'''
| align="center" | ⇔
| align="left" | '''<u>Pointer-based implementation</u>'''
|-
| align="right" | B=emptytree 
|
| align="left" | B=nul
|-
| align="right" | B <math>\leftarrow</math> < _, _, _> 
|
| align="left" | Alloc(B)
|-
| align="right" | root(B) 
|
| align="left" | B<math>\uparrow</math>
|-
| align="right" | l(B) 
|
| align="left" | B<math>\uparrow</math>.lc
|-
| align="right" | r(B) 
|
| align="left" | B<math>\uparrow</math>.rc
|-
| align="right" | Content(root(B)) 
|
| align="left" | B<math>\uparrow</math>.elt
|}

<br/>

====Array implementation====

In this representation, the tree will be contained in a vector (one-dimensional array) of records, each with three fields: the element and two integers (one for the left child and the other for the right child). 
The latter (both integers) referencing the vector index of the child concerned (am I clear enough?).
The first index of the vector is 1, then we can use 0 as null pointer reference (the empty tree). We also need the position of the root given by an integer.

<u>''Note :</u> When coded in C, it will then use -1, the base being 0.''

Here is the declaration of such an algorithmic structure:<br/>

 <span style="color:#0000FF;">'''Constants'''</span><br/>
    MaxNb = ''21''<br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...                     <span style="color:#00FF00;">/* Definition of element type */</span>
    t_node = '''record'''                     <span style="color:#00FF00;">/* Definition of t_node type */</span>
       t_element elt
       integer lc, rc
    '''end record''' t_node<br/>
    t_vectMaxNbnode = MaxNb t_node      <span style="color:#00FF00;">/* Definition of t_node vector */</span>
    t_tree = '''record'''                     <span style="color:#00FF00;">/* Definition of t_tree type */</span>
       t_vectMaxNbnode nodes
       integer         root
    '''end record''' t_tree<br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_tree tree
	
In this kind of implementation, the correspondences between the abstract operations and the array implementation (on a B binary tree) are the following:

<br/>

{| border="0" cellpadding="5" align="center"
| align="right" | '''<u>Abstract type</u>'''
| align="center" | ⇔
| align="left" | '''<u>Array implementation</u>'''
|-
| align="right" | B=emptytree 
|
| align="left" | B.root=0
|-
| align="right" | root(B) 
|
| align="left" | B.root
|-
| align="right" | l(B) 
|
| align="left" | B.nodes[B.root].lc
|-
| align="right" | r(B) 
|
| align="left" | B.nodes[B.root].rc
|-
| align="right" | Content(root(B)) 
|
| align="left" | B.nodes[B.root].elt
|}

<br/>

Adapted to the tree of Figure 1, we would have the table in '''Figure 6 (a).''' In fact, with this kind of tree, the root may be located in any index. So we can represent several trees at the same time in the same array, a forest for example. We just have to know for each tree where its root is.

<br/>

{| border="0" cellpadding="5" align="center"
|+ '''Figure 6. Array implementation of a binary tree'''
| 
{| border="1" cellpadding="5" align="center"
! !! elt !! fg !! fd
|-
| '''1''' 
| 1 
| 2 
| 3
|-
| '''2''' 
| 2 
| 4 
| 5
|-
| '''3''' 
| 3 
| 6 
| 7
|-
| '''4''' 
| 4 
| 8 
| 0
|-
| '''5''' 
| 5 
| 9 
| 10
|-
| '''6''' 
| 6 
| 0 
| 1
|-
| '''7''' 
| 7 
| 12 
| 13
|-
| '''8''' 
| 8 
| 0 
| 14
|-
| '''9''' 
| 9 
| 0 
| 15
|-
| '''10''' 
| 10 
| 0 
| 0
|-
| '''11''' 
| 11 
| 0 
| 0
|-
| '''12''' 
| 12 
| 0 
| 0
|-
| '''13''' 
| 13 
| 0 
| 0
|-
| '''14''' 
| 14 
| 0 
| 0
|-
| '''15''' 
| 15 
| 0 
| 0
|-
| '''16''' 
|  
|  
| 
|-
| '''17''' 
|  
|  
| 
|-
| '''18''' 
|  
|  
| 
|-
| '''19''' 
|  
|  
| 
|-
| '''20''' 
|  
|  
| 
|-
| '''21'''
|  
|  
| 
|}
| width="15" |
|
{| border="1" cellpadding="5" align="center"
! !! elt !! fg !! fd
|-
| '''1''' 
| 1 
| 2 
| 3
|-
| '''2''' 
| 2 
| 4 
| 5
|-
| '''3''' 
| 3 
| 6 
| 7
|-
| '''4''' 
| 4 
| 8 
| 0
|-
| '''5''' 
| 5 
| 10 
| 11
|-
| '''6''' 
| 6 
| 0 
| 13
|-
| '''7''' 
| 7 
| 14 
| 15
|-
| '''8''' 
| 8 
| 0 
| 17
|-
| '''9''' 
|  
|  
| 
|-
| '''10''' 
| 9 
| 0 
| 19
|-
| '''11''' 
| 10
| 0 
| 0
|-
| '''12''' 
|  
|  
| 
|-
| '''13''' 
| 11 
| 0 
| 0
|-
| '''14''' 
| 12 
| 0 
| 0
|-
| '''15''' 
| 13 
| 0 
| 0
|-
| '''16''' 
|  
|  
| 
|-
| '''17''' 
| 14 
| 0
| 0
|-
| '''18''' 
|  
|  
| 
|-
| '''19''' 
| 
| 
| 
|-
| '''20''' 
|  
|  
| 
|-
| '''21'''
| 15
| 0
| 0
|}
| width="15" |
|
{| border="1" cellpadding="5" align="center"
! !! elt 
|-
| '''1''' 
| 1 
|-
| '''2''' 
| 2 
|-
| '''3''' 
| 3 
|-
| '''4''' 
| 4 
|-
| '''5''' 
| 5 
|-
| '''6''' 
| 6 
|-
| '''7''' 
| 7 
|-
| '''8''' 
| 8 
|-
| '''9''' 
|  
|-
| '''10''' 
| 9 
|-
| '''11''' 
| 10
|-
| '''12''' 
|  
|-
| '''13''' 
| 11 
|-
| '''14''' 
| 12 
|-
| '''15''' 
| 13 
|-
| '''16''' 
|  
|-
| '''17''' 
| 14 
|-
| '''18''' 
|  
|-
| '''19''' 
| 
|-
| '''20''' 
| 
|-
| '''21'''
| 15
|}
|-
| align="center" | '''(a)'''
|
| align="center" | '''(b)'''
|
| align="center" | '''(c)'''
|}

<br/>

If we had used for the same tree, a hierarchical numbering nodes (not labels), we would have obtained this table '''Figure 6 (b).'''

<u>''This numbering has two major flaws:''</u>
* ''It forces us to fix the root of a non-empty tree to 1''
* ''It generates holes in the table and therefore a relatively low occupancy rate.''

<br/>

That said, it is ideal for complete or perfect trees because all their levels, except the last, are filled, so no holes (Golfers of the World, Sorry). 

In addition, the left child of a node '''n''i''''' is a node '''n''2i''''' and the right child is a node '''n''2i+1''''', therefore we no longer need to reference the left and right children. This allows us to represent the tree using a simple vector of elements as shown in '''Figure 6 (c).'''

<u>''Remarks :''</u> 
* ''We must find a way using the element to reference an empty tree (one possibility is to put the root at the 0 value).''
* ''This representation allows us to know the father of a node without having to memorize it. ''For a node '''ni''' when '''i>1''', this is the node '''n div 2'''.''
*'' For a non-empty tree, the root must always be equal to 1.''
<br/>

For this representation ('''figure 6(c)'''), the algorithmic declaration would become:<br/>

 <span style="color:#0000FF;">'''Constants'''</span><br/>
    MaxNb = ''21''<br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...                     <span style="color:#00FF00;">/* Definition of element type */</span>
    t_vectMaxNbnode = MaxNb t_element   <span style="color:#00FF00;">/* Definition of t_node vector */</span>
    t_tree = '''record'''                     <span style="color:#00FF00;">/* Definition of type t_tree */</span>
       t_vectMaxNbnode node
       integer         root
    '''end record''' t_arbre<br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_tree tree

In this case, the correspondences between the abstract operations and the array implementation would be the following:

<br/>

{| border="0" cellpadding="5" align="center"
| align="right" | '''<u>Abstract type</u>'''
| align="center" | ⇔
| align="left" | '''<u>Array implementation (hierarchical numbering)</u>'''
|-
| align="right" | B=emptylist
|
| align="left" | B.root=0
|-
| align="right" | root(B) 
|
| align="left" | B.root
|-
| align="right" | l(B) 
|
| align="left" | B.nodes[2*B.root]
|-
| align="right" | r(B) 
|
| align="left" | B.nodes[2*B.root+1]
|-
| align="right" | Content(root(B)) 
|
| align="left" | B.nodes[B.root]
|}

<br/>

===Traversals of a binary tree===

A traversal of a tree is a systematic way of accessing, or "''visiting''," all the nodes of a tree. 

There exist several ways to traverse a binary tree (you should be familiar with them): 
* the depth-first traversal (Ooohh…).
* the breadth-first (''level-order'') traversal (aaaahh…)

The first examines the nodes as far down as possible in the tree (until a node has no children node) and the second processes all nodes of a tree by depth: first the root, then the children of the root, etc.

For the purpose of illustration, it is assumed that left nodes always have priority over right nodes. This ordering can be reversed as long as the same ordering is assumed for all traversal methods.

====Depth-first traversal==== 

This traversal is '''recursive by nature''', it is used in maze solving algorithms (the "recursive backtracker" algorithm for example). Very simple: if you're at a wall (or an area you've already plotted), return failure, else if you're at the finish, return success, else recursively try moving in the four directions. Plot a line when you try a new direction, and erase a line when you return failure, and a single solution will be marked out when you hit success. When backtracking, it's best to mark the space with a special visited value, so you don't visit it again from a different direction. In Computer Science terms, this is basically a depth first search. This method will always find a solution if one exists, but it won't necessarily be the shortest solution. In French we call that kind of traversal '''le parcours profondeur main gauche'''.

<br/>

{| align="center" border="1" cellpadding="10"
| [[Image:binary_tree_traversal.png|400px| ''Depth-first Traversal of a binary tree'']]
|+ '''Figure 8. Depth-first Traversal of a binary tree'''
|}

<br/>

On the traversal of Figure 8, we have not accounted for the empty subtrees but they must be taken into account if one wants to admit that each node (including leaves) are met several times during the course. There are 3 orders induced by the depth-first traversal (see Figure 9) and are called:

<br/>

* (1)  '''Preorder''' visit each node before its children,
* (2)  '''Inorder''' visit left subtree, node, right subtree,
* (3)  '''Postorder''' visit each node after its children.

<br/>

{| align="center" border="1" cellpadding="10"
| [[Image:binary_tree_traversal_orders.png|400px| ''PreOrder, InOrder and PostOrder'']]
|+ '''Figure 9. Orders induced by a Depth-first traversal of a binary tree'''
|}

<br/>

=====Depth-First traversal Algorithm=====

During this traversal, each node is met three times. We can assign to each of them a special processing. Furthermore, if we include the empty trees, we can also specify a special processing for them. It gives the following '''abstract''' algorithm that traverses a binary tree recursively:

 '''Algorithm procedure''' depth-first_parse
 '''Local parameters'''
    binarytree b
 '''Begin'''
    '''if''' b=emptytree '''then'''
       <span style="color:#00FF00;">/* end processing */</span>
    '''else'''
       <span style="color:#00FF00;">/* Preorder processing */</span>
       depth-first_parse(l(b))
       <span style="color:#00FF00;">/* Inorder processing */</span>
       depth-first_parse(r(b))
       <span style="color:#00FF00;">/* Postorder processing */</span>
    '''endif'''
 '''End algorithm procedure''' depth-first_parse

		
To clearly highlight the differences between the three orders induced by this traversal, we will replace them each time by the following display of the node:

 Write(content(root(b))

If for each order we leave the other processes empty and then we apply this algorithm to the binary tree in Figure 8, we would obtain each time:

<br/>
* (1) '''Preorder :''' 1, 2, 4, 8, 14, 5, 9, 15, 10, 3, 6, 11, 7, 12, 13

* (2) '''Inorder :''' 8, 14, 4, 2, 9, 15, 5, 10, 1, 6, 11, 3, 12, 7, 13

* (3) '''Postorder :''' 14, 8, 4, 15, 9, 10, 5, 2, 11, 6, 12, 13, 7, 3, 1

<br/>

We note that depending on the type of traversal, the order of nodes differs.
 
<br/>
<u>''Remarks :''</u>
* The hierarchical order, (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) for this example, is not visible because it corresponds to a breadth-first (level-order) traversal of the tree.
* All processes can be used at the same time to eventually achieve different things in a different order, or else because these processes are complementary. Thereafter, we will see the need to use several of these processes.

<br/>

=====Depth-first traversal of a tree representing an arithmetical expression=====

We can use a binary tree to represent an arithmetical expression. In this case, the internal nodes store operators and the external nodes store operands. For the arithmetical expression '''( a + ( ( b * 4 ) / 3 ) )''', we can have the '''binary labeled tree''' of figure 10 :

<br/>

{| align="center" border="1" cellpadding="10"
| [[Image:binary_tree_traversal_expression.png|400px| ''arithmetical expression represented by a binary tree'']]
|+ '''Figure 10. arithmetical expression (a+((b*4)/3)'''
|}

<br/>

<u>''Remark:</u>  This expression uses only binary operators (with two operands), so it is a '''full (proper) binary tree'''.''

For the tree of figure 10, the depth-first traversal, depending on orders, gives :

<br/>
* (1) '''preorder :''' + a / * b 4 3
* (2) '''inorder  :''' a + b * 4 / 3
* (3) '''postorder:''' a b 4 * 3 / + 

<br/>

We note that the preorder and postorder are unambiguous. The first corresponding to the '''Polish notation''' and the second to the '''reverse Polish notation (rpn)'''. This is unfortunately not the case for the inorder. Indeed, this series could correspond to different trees as shown in Figure 11.

<br/>

{| align="center" border="1" cellpadding="10"
| [[Image:binary_tree__ambiguous_expression.png|500px| ''Arithmetical expressions representing by binary trees'']]
|+ '''Figure 11. Arithmetical expressions (a+((b*4)/3) et ((a+(b*4))/3)'''
|}

<br/>

Indeed the Polish or reverse Polish notations are preceded or followed by operators of their operands. However for the inorder notation, we don't know if ''a + b * 4/3'' corresponds to ''a + ((b * 4) / 3'' or ''(a + (b * 4)) / 3''. Actually this ambiguity can be easily resolved using parentheses to force the priority of operators.

It suffices to modify the depth-first traversal algorithm previously given as follows:

 '''Algorithm procedure''' depth-first_inorder_parse
 '''Local Parameters'''
    binarytree b
 '''Begin'''
    '''if''' l(b)=emptytree '''and''' r(b)=emptytree '''then'''   <span style="color:#00FF00;">/* b is a leaf */</span>
       <span style="color:#FFA500;">write(content(root(b)))</span>                  <span style="color:#00FF00;">/* End processing */</span>
    '''else'''
       <span style="color:#FFA500;">write('(')</span>                               <span style="color:#00FF00;">/* Preorder processing */</span>
       depth-first_inorder_parse(l(b))
       <span style="color:#FFA500;">write(content(root(b)))</span>                  <span style="color:#00FF00;">/* Inorder processing */</span>
       depth-first_inorder_parse(r(b))
       <span style="color:#FFA500;">write(')')</span>                               <span style="color:#00FF00;">/* Postorder processing */</span>
    '''endif'''
 '''End algorithm procedure''' depth-first_inorder_parse


That gives for trees given in Figure 11 the two following unambiguous series :

<br/>
* '''Figure 11(A) :''' ( a + ( ( b * 4 ) / 3 ) )
* '''Figure 11(B) :''' ( ( a + ( b * 4 ) ) / 3 )

<br/>
<u>''Remark :</u> In the previous algorithm, we could change the test that checks whether the node where we are is a leaf. To do this, it suffices to create an extension to the Binary tree abstract type creating a new operation as follows:''

 '''operations'''<br/>
    leaf : binarytree <math>\rightarrow</math> boolean<br/>
 '''axioms'''<br/>
    b<math>\neq</math>emptytree & l(b)=emptytree & r(b)=emptytree <math>\Rightarrow</math> leaf(b)=true 

<br/>
Then the beginning of the algorithm will be :

 '''Algorithm procedure''' depth-first_inorder_parse
 '''Local Parameters'''
    binarytree b
 '''Begin'''
    '''if''' leaf(b) '''then'''   <span style="color:#00FF00;">/* b is a leaf */</span>
<br/>

====Breadth-first (level-order) traversal====
The traversal begins at a root node and inspects all the children nodes. Then for each of those children nodes in turn, it inspects their children nodes, and so on.

<u>''Remark :</u> This traversal, also called '''level-order''', is iterative by nature.''

The Breadth-first traversal uses a '''Queue''' to memorize the two children of each node visited. That allows, at the next level, to retrieve them in the meet order.
It gives the following algorithm :

 '''Algorithm procedure''' breadth-first_parse
 '''Local parameters'''
    binarytree b
 '''Variables'''
    integer i
    queue q                              <span style="color:#00FF00;">/* f memorizes the trees */</span>
 '''Begin'''
    q <math>\leftarrow</math> emptyqueue
    q <math>\leftarrow</math> enqueue(b,q)                    <span style="color:#00FF00;">/* push of the b tree */</span>
    '''while''' not(isempty(q)) '''do'''
       b <math>\leftarrow</math> first(q)                     <span style="color:#00FF00;">/* recover the 1st tree memorized */</span>
       q <math>\leftarrow</math> dequeue(q)                   <span style="color:#00FF00;">/* remove this tree of the queue */</span>
       <span style="color:#FFA500;">write(content(root(b)))</span>           <span style="color:#00FF00;">/* display the root node of the recovered tree */</span>
       '''if''' l(b))<>emptytree '''then'''
          q <math>\leftarrow</math> enqueue(l(b),q)           <span style="color:#00FF00;">/* push of the left subtree of b */</span>
       '''endif'''
       '''if''' r(b))<>emptytree '''then'''
          q <math>\leftarrow</math> enqueue(r(b),q)           <span style="color:#00FF00;">/* push of the right subtree of b */</span>
       '''endif'''
    '''endwhile'''
 '''End Algorithm procedure''' breadth-first_parse

If we apply this algorithm to the binary tree in Figure 8, we would obtain:

 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

<u>''Remarks :</u>''
* ''This algorithm performs the breadth-first traversal of any '''non-empty''' binary tree.''
* ''Complexity is the same as the depth-first traversal.''
<br/>

== General trees ==

A tree or general tree is a tree structure where the number of children is not limited to two. The recursive definition of a general tree is '''<math>A=< o, A_1, ..., A_n></math>''' where '''<math>o</math>''' is the root of '''<math>A</math>''' and '''<math>A_1, ..., A_n</math>''' is a finite list, possibly empty (if n = 0), of disjointed trees. This list is called a forest. We obtain a tree by adding a root to a forest.

<br/>
{| align="center" border="1" cellpadding="10"
| [[Image:drawing_general_tree_example.png|650px| ''Graphical representation of a tree'']]
|+ '''Figure 12. Graphical example of a tree.'''
|}

<br/>

===''General tree'' Algebraic Abstract Type===

 '''types'''<br/>
    tree, forest<br/>
 '''use'''<br/>
    node, integer, <span style="color:#0000FF;">element</span><br/><br/>
 '''operations'''<br/>
          cons : node x forest <math>\rightarrow</math> tree
          root : tree <math>\rightarrow</math> node
      treelist : tree <math>\rightarrow</math> forest
   emptyforest : <math>\rightarrow</math> forest
        insert : forest x integer x tree <math>\rightarrow</math> forest
        delete : forest x integer <math>\rightarrow</math> forest
           nth : forest x integer <math>\rightarrow</math> tree
       nbtrees : forest <math>\rightarrow</math> integer
      <span style="color:#0000FF;">content : node <math>\rightarrow</math> element</span><br/>
 '''preconditions'''<br/>
    insert(''f,i,t'') is-defined-iaoi ''1'' ≤ ''i'' ≤ ''1'' + nbtrees(''f'')
    delete(''f,i'') is-defined-iaoi ''f'' ≠ emptyforest & ''1'' ≤ ''i'' ≤ nbtrees(''f'')
    nth(''f,i'') is-defined-iaoi ''f'' ≠ emptyforest & ''1'' ≤ ''i'' ≤ nbtrees(''f'')<br/>
 '''axioms'''<br/>
    root(cons(''o,f''))=''o''
    treelist(cons(''o,f''))=''f''
    nbtrees(emptyforest)=''0''
    nbtrees(insert(''f,i,t''))=nbtrees(''f'') + 1
    nbtrees(delete(''f,i''))=nbtrees(''f'') - 1
    1 ≤ i < k <math>\Rightarrow</math> nth(insert(''f,k,t''),''i'') = nth(''f,i'')
    k = i <math>\Rightarrow</math> nth(insert(''f,k,t''),''i'') = ''t''
    k < i ≤ nbtrees(''f'')+''1'' <math>\Rightarrow</math> nth(insert(''f,k,t''),''i'') = nth(''f,i-1'')
    1 ≤ i < k <math>\Rightarrow</math> nth(delete(''f,k''),''i'') = nth(''f,i'')
    k ≤ i ≤ nbtrees(''f'')-1 <math>\Rightarrow</math> nth(delete(''f,k''),''i'') = nth(''f,i+1'')<br/>
 '''with'''
    node ''o''
    tree ''t''
    forest ''f''
    integer ''i,k''

<U>''Remarks :</u>'' 
* ''The "left-right" notion necessary to the binary tree disappears. That said, the vocabulary used for the general trees remains the same except for everything that uses this notion (of generality). For instance we no longer talk about a left or a right child, but about first child, second child and so on and a last child.''
* ''The measurements on the trees are retained (height, path length, size, etc).''
<br/>

===Implementations of general trees===

There are several kinds of representations of general trees. The most intuitive are the linked-list and the n-tuple representations. Another one, very used, is the leftmost child-right sibling representation (''a binary tree'').

====Vector-based (''Array'') implementation of general trees====

In this case, the set of nodes is represented in a one-dimensional array (vector), oversized to allow us to add nodes if necessary. Each element is a record that contains the label of the node plus a pointer to its children list. The children list consists of records containing two fields : a pointer to a table element and another pointer to the next record (as for graph lists of adjacency). In this case, the algorithmic description would be:

 <span style="color:#0000FF;">'''Constants'''</span><br/>
    MaxNb = ''27''<br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...                <span style="color:#00FF00;">/* Definition of element type */</span>
    t_pchild = <math>\uparrow</math>t_child            <span style="color:#00FF00;">/* Definition of child node pointer (list) */</span><br/>
    t_node = '''record'''                <span style="color:#00FF00;">/* Definition of type t_node */</span>
       t_element  elt
       t_pchild   firstchild
    '''end record''' t_node<br/>
    t_child = '''record'''               <span style="color:#00FF00;">/* Definition of type t_child */</span>
       integer    childnodenumber
       t_pchild   nextchild
    '''end record''' t_child<br/>
    t_tree = MaxNb t_node         <span style="color:#00FF00;">/* Definition of type y_tree (array) */</span><br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_tree tree

For the tree of figure 12, this would give :

<br/>
{| align="center" border="1" cellpadding="10"
| align=center | '''Figure 13. Vector-based implementation of the general tree of figure 12.'''
|-
| [[Image:static-dynamic_tree_type.png‎|450px| Vector-based implementation of a general tree'']]
|}

<br/>

====Linked-list (''pointer'') implementation of general trees====

<u>''Remark :</u> One possibility is to transform this representation to a full dynamic one replacing the vector by a linked list. In this case, nodes are interconnected by a dynamic link (pointer), and thereby in the record '''''t_child''''' the integer '''''childnodenumber''''' (index of the node in the table) is replaced by a pointer to the node address. 

That gives the following algorithmic declaration :

 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...                      <span style="color:#00FF00;">/* Definition of element type */</span>
    t_pnode = <math>\uparrow</math>t_node                    <span style="color:#00FF00;">/* Definition of t_pnode (pointer to t_node)*/</span>
    t_pchild = <math>\uparrow</math>t_child                  <span style="color:#00FF00;">/* Definition of t_pchild (pointer to t_child) */</span><br/>
    t_node = '''record'''                      <span style="color:#00FF00;">/* Definition of t_node */</span>
       t_element elt
       t_pnode   nextnode, prevnode
       t_pchild  firstchild
    '''end record''' t_node<br/>
    t_child = '''record'''                     <span style="color:#00FF00;">/* Definition of t_child */</span>
       t_pnode   childnode               <span style="color:#00FF00;">/* pointer to childnode */</span>
       t_pchild  nextchild               <span style="color:#00FF00;">/* pointer to next childnode */</span>
    '''end record''' t_child<br/>
    t_tree = t_pnode                     <span style="color:#00FF00;">/* Definition of t_tree (pointer to node) */</span><br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_tree tree

''To visualize this structure, it is sufficient to see the adjacency list representation of graphs with a dynamic set of vertices.''

====Binary trees implementation (''left most child-right sibling representation'')====

The way of representing general trees as binary trees is to use the left link as the left most child and the right link as the next sibling. This representation has several advantages:

* This is a bijective representation : One node in the general tree, one node in the binary tree.
* We can use the algorithms on binary trees (traversal, insertion of node, etc.), that are very simple to implement.

<u>''Remark :</u> It seems obvious that this is [[Epita:Algo:Course:Info-Sup:Trees_Structures#pointer-based_implementation | the pointer-based implementation of a binary tree]] that is chosen.''

The algorithmic description would be:

 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...                <span style="color:#00FF00;">/* Definition of element type */</span>
    t_tree = <math>\uparrow</math>t_node               <span style="color:#00FF00;">/* Definition of t_tree (pointer to t_node) */</span>
    t_node = '''record'''                <span style="color:#00FF00;">/* Definition of t_node */</span>
       t_element elt
       t_tree    leftmostchild, rightsibling
    '''end record''' t_node<br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_tree tree

For the tree of figure 12, this would give :

<br/>
{| align="center" border="1" cellpadding="10"
| align="center | '''Figure 15. ''left most child-right sibling representation'' of the tree of figure 12.'''
|-
| [[Image:leftmostchild_rightsibling_tree_type.png|600px| ''left most child-right sibling representation'' of the tree of figure 12.]]
|}

<br/>

Working with this tree is very simple. For example to find the child of a node (in the general tree), it is sufficient from its right child (in the binary tree) to traverse the right edge (always in the binary tree). Similarly, calculating the height of the tree can easily be done in the binary tree by considering only the height of the left child (the first child in the general tree) and not the right siblings  (which are located at the same height).

<u>''Remarks :</u>''
* ''The corresponding binary tree is not balanced at all.''
* ''The preorder and inorder traversals of the corresponding binary tree will give the same encountering order of nodes as those given by the respectively preorder and postorder traversals of the implemented general tree.''

<br/>

====N-tuple representation====

If you know the maximum number of children that can have a node, it is possible to represent the tree as '''N-tuple'''. This representation is an extension of the dynamic representation of binary trees. Here, the number of children is not two, but one that we have specified (''using a constant''). Assuming there are five maximum children, the algorithmic declaration would be the following:

 <span style="color:#0000FF;">'''Constants'''</span><br/>
    MaxChildrenNb = 5                     <span style="color:#00FF00;">/* Maximum number of children */</span><br/>
 <span style="color:#0000FF;">'''Types'''</span><br/>
    t_element = ...                       <span style="color:#00FF00;">/* Definition of element type */</span>
    t_tree = <math>\uparrow</math>t_node                      <span style="color:#00FF00;">/* Definition of t_tree  (pointer to t_node) */</span>
    t_childrentab = MaxChildrenNb t_tree  <span style="color:#00FF00;">/* Definition of children vector */</span><br/>
    t_node = '''record'''                       <span style="color:#00FF00;">/* Definition of t_node */</span>
       t_element     elt
       t_childrentab children
    '''end record''' t_node<br/>
 <span style="color:#0000FF;">'''Variables'''</span><br/>
    t_tree tree

For the tree of figure 12, this would give :

<br/>
{| align="center" border="1" cellpadding="10"
| align="center" | '''Figure 16. ''n-tuple'' tree representation of the tree of figure 12.'''
|-
| [[Image:n-tuple_tree_type.png|700px| ''n-tuple tree representation of the tree of figure 12'']]
|}

<br/>

===Traversals of a general tree===

As for a binary tree the traversal of a tree is a systematic way of accessing, or "''visiting''," all the nodes of the tree. 

There exist several ways to traverse a tree (you should be familiar with them): 
* the depth-first traversal (Ooohh…).
* the breadth-first (''level-order'') traversal (aaaahh…)

The first (''recursive by nature'') examines the nodes as far down as possible in the tree (until a node has a no children node) and the second (''iterative by nature'') processes all nodes of a tree by depth: first the root, then the children of the root, etc.

====Depth-first traversal==== 

To traverse a general tree, we can use the same principle as the depth-first traversal of binary trees. The difference lies in the fact that there only two induced orders : there is no '''inorder traversal''', but an intermediate process at each passage of one child to another. 
In other words, a node is met one time more than its number of children: once before visiting its first child (''preorder''), once between each child and its right sibling and once when returning from the last child (''postorder'').

The algorithm used for this traversal is that of the binary tree "slightly modified". Indeed, processes have to be placed inside a loop whose number of iterations depends on the subtree number of the tree that we have to traverse.

To illustrate this, assume a general tree '''A = <o, A1, A2, A3, A4>''', we get the path of Figure 17 (resembling nothing so much as an x-ray of the hand of Mickey ''highlighting the presence of an exo-skeleton :D''):

<br/>
{| align="center" border="1" cellpadding="10"
| align="center" | '''Figure 17. Depth-first traversal of a general tree.'''
|-
| [[Image:general_tree_traversal.png|500px| ''Depth-first traversal of a general tree'']]
|}

<br/>

More seriously, it can be seen on this traversal that the root node is visited five times, once when descending toward '''''A1''''' (''preorder process''), three times from '''''A1''''' to '''''A2''''', '''''A2''''' to '''''A3''''' and '''''A3''''' to '''''A4''''' (''intermediate processes''), and finally when returning from '''''A4''''' (''postorder process'').

It gives the following '''abstract''' depth-first traversal of a tree:

 '''Algorithm procedure''' depth-first_parse
 '''Local parameters'''
    tree t
 '''Variables'''
    integer i, childnb
 '''Begin'''
    childnb <math>\leftarrow</math> nbtrees(treelist(t)) 
    '''if''' leaf(t) '''then'''    <span style="color:#00FF00;">                /* t is a leaf (childnb=0) */</span>
       <span style="color:#FFA500;">/* End processing */</span>
    '''else'''
       <span style="color:#FFA500;">/* Preorder processing */</span>
       '''for''' i <math>\leftarrow</math> 1 '''to''' childnb-1 '''do'''
          depth-first_parse(nth(treelist(t),i))
          <span style="color:#FFA500;">/* Intermediate processing */</span>
       '''endfor'''
       depth-first_parse(nth(treelist(t),childnb))
       <span style="color:#FFA500;">/* Postorder processing */</span>
    '''endif'''
 '''End algorithm procedure''' depth-first_parse

<u>''Remarks :</u>''
* ''We use an additional operation presented with the '''binary tree abstract data type''' that is the '''leaf'''. This operation should of course be defined as an additional operation of the '''general tree abstract data type'''.''
* ''The number of possible treatments of a node is not limited to three, but may actually be equal to the number of children plus one. Indeed, the number of  intermediate processes depends on the value of the loop index and therefore allows for a particular treatment each time.''

For example, using the general tree of Figure 12, we can list the nodes as follows:

 (A(B(E(L)(M)(N)(O))(F))(C(G(P)(Q)(R)))(D(H(S))(I(T)(U)(V)(W))(J)(K(X)(Y)(Z))))

using the following algorithm :

 '''Algorithm procedure''' depth-first_parse_lisp
 '''Local parameters'''
    tree t
 '''Variables'''
    integer i, childnb
 '''Begin'''
    childnb <math>\leftarrow</math> nbtrees(treelist(t)) 
    '''if''' leaf(t) '''then'''                        <span style="color:#00FF00;">/* t is a leaf (childnb=0) */</span>
       <span style="color:#FFA500;">write('(',content(root(t)),')')</span>
    '''else'''
       <span style="color:#FFA500;">write('(',content(root(t)))</span>
       '''for''' i <math>\leftarrow</math> 1 '''to''' childnb-1 '''do'''
          depth-first_parse_lisp(nth(treelist(t),i))
       '''endfor'''
       depth-first_parse_lisp(nth(treelist(t),childnb))
       <span style="color:#FFA500;">write(')')</span>
    '''endif'''
 '''End algorithm procedure''' depth-first_parse_lisp

that could be optimized in the following way :

 '''Algorithm procedure''' depth-first_parse_lisp
 '''Local parameters'''
    tree t
 '''Variables'''
    integer i, childnb
 '''Begin'''
    childnb <math>\leftarrow</math> nbtrees(treelist(t)) 
    <span style="color:#FF0000;">write('(',content(root(t)))</span>
    '''if''' not(leaf(t)) '''then'''                        <span style="color:#00FF00;">/* t is not a leaf (childnb>0) */</span>
       '''for''' i <math>\leftarrow</math> 1 '''to''' childnb-1 '''do'''
          depth-first_parse_lisp(nth(treelist(t),i))
       '''endfor'''
       depth-first_parse_lisp(nth(treelist(t),childnb))
    '''endif'''
    <span style="color:#FF0000;">write(')')</span>
 '''End algorithm procedure''' depth-first_parse_lisp

====Breadth-first traversal====

The traversal begins at a root node and inspects all the children nodes. Then for each of those children nodes in turn, it inspects their children nodes, and so on.

Actually the traversal is done  by distance (''level'', ''depth'' or ''height'' in this case), that is to say that we first scan all the nodes at a distance of 1 from the root, then all those that are located at a distance of  2 and so on ...

<u>''Remark :</u> This traversal, also called level-order, is iterative by nature.''

The '''Breadth-first traversal''' uses a Queue to memorize all the children of each node visited. That allows, at the next level, to retrieve them in the meet order. It gives the following algorithm :

 '''Algorithm procedure''' breadth-first_parse
 '''Local parameters'''
    tree t
 '''Variables'''
    integer i
    queue q                                        <span style="color:#00FF00;">/* f stocke les arbres */</span>
 '''Begin'''
    q <math>\leftarrow</math> emptyqueue
    q <math>\leftarrow</math> enqueue(q,t)                              <span style="color:#00FF00;">/* storage of the tree */</span>
    '''while''' not(isempty(q)) '''do'''
       t <math>\leftarrow</math> first(f)                                <span style="color:#00FF00;">/* recovery of the first tree stored */</span>
       q <math>\leftarrow</math> dequeue(q)                             <span style="color:#00FF00;">/* release the tree of the queue */</span>
       <span style="color:#FFA500;">write(content(root(t)))</span>                     <span style="color:#00FF00;">/* displaying the content of the root node of the recovered tree*/</span>
       '''for''' i <math>\leftarrow</math> 1 '''to''' nbtrees(treelist(t)) '''do'''
          q <math>\leftarrow</math> enqueue(q,nth(treelist(t),i)))      <span style="color:#00FF00;">/* storage of the ith subtree of t */</span>
       '''endfor'''
    '''endwhile'''
 '''End algorithm procedure''' breadth-first_parse

Using the general tree of Figure 12, we can list the nodes as follow: 

 A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z

<u>''Remark :</u> Complexity is the same as the depth-first traversal.''

----
<small>''(Christophe "krisboul" Boullay)''</small>