danielhagnoul

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#! python3
# coding: utf-8
 
binary_tree = {'r': ['a', 'b'], 'a': ['c', 'd'], 'b': ['e', 'f'],
               'c': ['', 'h'], 'd': ['i', 'j'], 'e': ['k', ''], 'f': ['', ''],
               'h': ['', ''], 'i': ['', ''], 'j': ['m', ''], 'k': ['', ''], 'm': ['', '']}
 
 
def binary_tree_parcours_prefixe(root_str, T):
    """ Parcours prefixe de l'arbre binaire T """
    parcours = []
    key = root_str
    lst = T.get(key, '')
 
    def parcours_arbre_T(key, lst):
        parcours.append(key)
        node_gauche = lst[0]
        if node_gauche:
            lst_gauche = T.get(node_gauche, '')
            parcours_arbre_T(node_gauche, lst_gauche)
        node_droit = lst[1]
        if node_droit:
            lst_droit = T.get(node_droit, '')
            parcours_arbre_T(node_droit, lst_droit)
 
    parcours_arbre_T(key, lst)
    return parcours
 
 
parcours = binary_tree_parcours_prefixe('r', binary_tree)
 
print(parcours)  # [r', 'a', 'c', 'h', 'd', 'i', 'j', 'm', 'b', 'e', 'k', 'f']
 
 
def binary_tree_parcours_infixe(root_str, T):
    """ Parcours infixe de l'arbre binaire T """
    parcours = []
 
    def parcours_arbre_T(key, lst):
        parcours.append(key)
        node_gauche = lst[0]
        if node_gauche:
            lst_gauche = T.get(node_gauche, '')
            parcours_arbre_T(node_gauche, lst_gauche)
        node_droit = lst[1]
        if node_droit:
            lst_droit = T.get(node_droit, '')
            parcours_arbre_T(node_droit, lst_droit)
 
    # arbre gauche
    key = T.get(root_str, '')[0]
    lst = T.get(key, '')
    parcours_arbre_T(key, lst)
 
    # racine
    parcours.append(root_str)
 
    # arbre droit
    key = T.get(root_str, '')[1]
    lst = T.get(key, '')
    parcours_arbre_T(key, lst)
 
    return parcours
 
 
parcours = binary_tree_parcours_infixe('r', binary_tree)
 
print(parcours)  # ['a', 'c', 'h', 'd', 'i', 'j', 'm', 'r', 'b', 'e', 'k', 'f']
 
 
def binary_tree_parcours_postfixe(root_str, T):
    """ Parcours postfixe de l'arbre binaire T """
    parcours = []
 
    def parcours_arbre_T(key, lst):
        parcours.append(key)
        node_gauche = lst[0]
        if node_gauche:
            lst_gauche = T.get(node_gauche, '')
            parcours_arbre_T(node_gauche, lst_gauche)
        node_droit = lst[1]
        if node_droit:
            lst_droit = T.get(node_droit, '')
            parcours_arbre_T(node_droit, lst_droit)
 
    # arbre gauche
    key = T.get(root_str, '')[0]
    lst = T.get(key, '')
    parcours_arbre_T(key, lst)
 
    # arbre droit
    key = T.get(root_str, '')[1]
    lst = T.get(key, '')
    parcours_arbre_T(key, lst)
 
    # racine
    parcours.append(root_str)
 
    return parcours
 
 
parcours = binary_tree_parcours_postfixe('r', binary_tree)
 
print(parcours)  # ['a', 'c', 'h', 'd', 'i', 'j', 'm', 'b', 'e', 'k', 'f', 'r']

Licence Creative Commons Attribution 2.0 Belgique