Ressources Projet 1
Utilisation de Tkinter pour dessiner des interfaces graphiques: cliquer ici
Dimensionnement et le positionnement avec Tkinter: cliquer ici
Exemple de solution du projet ( version complexe)
import tkinter as tk
from tkinter import ttk, messagebox
# =========================
# Utilitaires de dessin
# =========================
class TreeCanvas:
def __init__(self, canvas: tk.Canvas, node_radius=18, x_margin=30, y_margin=30, level_gap=80):
self.canvas = canvas
self.node_radius = node_radius
self.x_margin = x_margin
self.y_margin = y_margin
self.level_gap = level_gap
def clear(self):
self.canvas.delete("all")
def draw_nodes_edges(self, levels):
"""
levels: list of lists representing levels of the tree.
Each level is a list of node values or None. Uses centered spacing.
"""
self.clear()
width = int(self.canvas.cget("width"))
height = int(self.canvas.cget("height"))
n_levels = len(levels)
if n_levels == 0:
return
positions = {} # map (level,index_in_level) -> (x,y)
# Compute positions
for lvl, nodes in enumerate(levels):
count = len(nodes)
if count == 0:
continue
# Horizontal spacing: split width into count+1 segments to center nodes
gap = width / (count + 1)
y = self.y_margin + lvl * self.level_gap
for i, val in enumerate(nodes):
x = gap * (i + 1)
positions[(lvl, i)] = (x, y)
# Draw edges (parent to children) for binary layout
for lvl in range(n_levels - 1):
curr = levels[lvl]
nxt = levels[lvl + 1]
for i, val in enumerate(curr):
if val is None:
continue
# For perfect/array-indexed binary tree: children at indices 2*i and 2*i+1
left_idx = 2 * i
right_idx = 2 * i + 1
if left_idx < len(nxt) and nxt[left_idx] is not None:
x1, y1 = positions[(lvl, i)]
x2, y2 = positions[(lvl + 1, left_idx)]
self.canvas.create_line(x1, y1, x2, y2, width=2)
if right_idx < len(nxt) and nxt[right_idx] is not None:
x1, y1 = positions[(lvl, i)]
x2, y2 = positions[(lvl + 1, right_idx)]
self.canvas.create_line(x1, y1, x2, y2, width=2)
# Draw nodes
for key, (x, y) in positions.items():
lvl, i = key
val = levels[lvl][i]
if val is None:
continue
r = self.node_radius
self.canvas.create_oval(x - r, y - r, x + r, y + r, fill="#e6f2ff", outline="#004a99", width=2)
self.canvas.create_text(x, y, text=str(val), font=("Segoe UI", 10, "bold"))
# =========================
# Modèles d'arbres et parcours
# =========================
def build_perfect_tree_values(h, values):
"""
h: hauteur (niveau 0 à h)
values: list length must be 2^(h+1)-1
Returns levels as list of lists representing complete perfect tree.
"""
n = 2 ** (h + 1) - 1
if len(values) != n:
raise ValueError(f"Nombre de valeurs attendu: {n}, reçu: {len(values)}")
levels = []
idx = 0
for lvl in range(h + 1):
width = 2 ** lvl
level_vals = values[idx:idx + width]
levels.append(level_vals)
idx += width
return levels
def build_arbitrary_tree_from_level_order(tokens):
"""
tokens: list of strings; 'None' or '' denotes missing node.
Interprets as level-order array for binary tree; children by 2*i and 2*i+1.
Trims trailing None nodes per level.
Returns levels list of lists.
"""
# Normalize None-like tokens
arr = []
for t in tokens:
if t is None:
arr.append(None)
else:
s = str(t).strip()
if s.lower() == "none" or s == "":
arr.append(None)
else:
arr.append(s)
# Compute max height by array length
n = len(arr)
levels = []
idx = 0
lvl = 0
while idx < n:
width = 2 ** lvl
level_vals = arr[idx:idx + width]
# Pad to full width if needed
if len(level_vals) < width:
level_vals = level_vals + [None] * (width - len(level_vals))
levels.append(level_vals)
idx += width
lvl += 1
# Trim trailing levels that are fully None
while levels and all(v is None for v in levels[-1]):
levels.pop()
return levels
# =========================
# ABR (BST) modèle et dessin
# =========================
class BSTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def bst_insert(root, key):
if root is None:
return BSTNode(key)
if key < root.key:
root.left = bst_insert(root.left, key)
else:
root.right = bst_insert(root.right, key)
return root
def bst_build_from_keys(keys):
root = None
for k in keys:
root = bst_insert(root, k)
return root
def bst_levels(root):
"""Return list of lists (levels) for drawing, but positions computed differently for BST."""
if not root:
return []
levels = []
queue = [(root, 0)]
current_level = 0
level_nodes = []
while queue:
node, lvl = queue.pop(0)
if lvl != current_level:
levels.append(level_nodes)
level_nodes = []
current_level = lvl
level_nodes.append(node)
if node.left:
queue.append((node.left, lvl + 1))
if node.right:
queue.append((node.right, lvl + 1))
levels.append(level_nodes)
return levels
class BSTCanvas(TreeCanvas):
def draw_bst(self, root):
self.clear()
if root is None:
return
width = int(self.canvas.cget("width"))
# Compute x-positions by in-order traversal for tidy layout
order = []
def inorder_pos(node):
if not node:
return
inorder_pos(node.left)
order.append(node)
inorder_pos(node.right)
inorder_pos(root)
# Map each node to an x position based on in-order index
x_positions = {}
count = len(order)
gap = width / (count + 1) if count > 0 else width / 2
for i, node in enumerate(order):
x_positions[node] = gap * (i + 1)
# Compute y by depth
def depth(node, d=0):
if not node:
return
node._depth = d
depth(node.left, d + 1)
depth(node.right, d + 1)
depth(root)
# Draw edges first
def draw_edges(node):
if not node:
return
if node.left:
self.canvas.create_line(
x_positions[node], self.y_margin + node._depth * self.level_gap,
x_positions[node.left], self.y_margin + node.left._depth * self.level_gap,
width=2
)
if node.right:
self.canvas.create_line(
x_positions[node], self.y_margin + node._depth * self.level_gap,
x_positions[node.right], self.y_margin + node.right._depth * self.level_gap,
width=2
)
draw_edges(node.left)
draw_edges(node.right)
draw_edges(root)
# Draw nodes
def draw_nodes(node):
if not node:
return
x = x_positions[node]
y = self.y_margin + node._depth * self.level_gap
r = self.node_radius
self.canvas.create_oval(x - r, y - r, x + r, y + r, fill="#fff3e6", outline="#cc6a00", width=2)
self.canvas.create_text(x, y, text=str(node.key), font=("Segoe UI", 10, "bold"))
draw_nodes(node.left)
draw_nodes(node.right)
draw_nodes(root)
def array_inorder(arr):
res = []
def visit(i):
if i >= len(arr) or arr[i] is None:
return
left = 2 * i + 1
right = 2 * i + 2
visit(left)
res.append(arr[i])
visit(right)
visit(0)
return res
def array_preorder(arr):
res = []
def visit(i):
if i >= len(arr) or arr[i] is None:
return
left = 2 * i + 1
right = 2 * i + 2
res.append(arr[i])
visit(left)
visit(right)
visit(0)
return res
def array_postorder(arr):
res = []
def visit(i):
if i >= len(arr) or arr[i] is None:
return
left = 2 * i + 1
right = 2 * i + 2
visit(left)
visit(right)
res.append(arr[i])
visit(0)
return res
def array_breadth(arr):
# Parcours en largeur sur la représentation par niveaux déjà fournie
return [x for x in arr if x is not None]
# =========================
# Interface utilisateur
# =========================
class App(tk.Tk):
def __init__(self):
super().__init__()
self.title("Arbres binaires et ABR - Tkinter")
self.geometry("1000x700")
notebook = ttk.Notebook(self)
notebook.pack(fill="both", expand=True)
# Tab A: Arbre binaire
self.tab_a = ttk.Frame(notebook)
notebook.add(self.tab_a, text="Partie A - Arbre binaire")
self.build_tab_a(self.tab_a)
# Tab B: ABR
self.tab_b = ttk.Frame(notebook)
notebook.add(self.tab_b, text="Partie B - ABR")
self.build_tab_b(self.tab_b)
# ------------- Partie A -------------
def build_tab_a(self, parent):
frm = ttk.Frame(parent, padding=10)
frm.pack(fill="both", expand=True)
# Controls
controls = ttk.LabelFrame(frm, text="Paramètres et données")
controls.pack(side="top", fill="x", padx=5, pady=5)
# Perfect tree controls
self.h_var = tk.StringVar(value="3")
ttk.Label(controls, text="Hauteur h (parfait):").grid(row=0, column=0, sticky="w", padx=5, pady=5)
ttk.Entry(controls, textvariable=self.h_var, width=8).grid(row=0, column=1, sticky="w", padx=5)
ttk.Label(controls, text="Valeurs (parfait, parcours en niveau):").grid(row=1, column=0, sticky="w", padx=5, pady=5)
self.values_perfect_var = tk.StringVar(value="A,B,C,D,E,F,G,H,I,J,K,L,M,N,O")
ttk.Entry(controls, textvariable=self.values_perfect_var, width=70).grid(row=1, column=1, columnspan=3, sticky="w", padx=5)
ttk.Button(controls, text="Dessiner arbre parfait", command=self.draw_perfect_tree).grid(row=0, column=2, padx=5, pady=5)
# Arbitrary tree controls
ttk.Label(controls, text="Valeurs (arbre quelconque, niveau avec 'None')").grid(row=2, column=0, sticky="w", padx=5, pady=5)
self.values_any_var = tk.StringVar(value="A,B,C,D,None,None,E,F")
ttk.Entry(controls, textvariable=self.values_any_var, width=70).grid(row=2, column=1, columnspan=3, sticky="w", padx=5)
ttk.Button(controls, text="Dessiner arbre quelconque", command=self.draw_any_tree).grid(row=2, column=4, padx=5, pady=5)
# Traversal controls
traversal_frame = ttk.LabelFrame(frm, text="Parcours")
traversal_frame.pack(side="top", fill="x", padx=5, pady=5)
self.traversal_target_var = tk.StringVar(value="parfait")
ttk.Radiobutton(traversal_frame, text="Utiliser arbre parfait", variable=self.traversal_target_var, value="parfait").grid(row=0, column=0, padx=5, pady=5)
ttk.Radiobutton(traversal_frame, text="Utiliser arbre quelconque", variable=self.traversal_target_var, value="any").grid(row=0, column=1, padx=5, pady=5)
ttk.Label(traversal_frame, text="Type de parcours:").grid(row=0, column=2, padx=5, pady=5)
self.traversal_type_var = tk.StringVar(value="infixe")
ttk.Combobox(traversal_frame, textvariable=self.traversal_type_var, values=["infixe", "prefixe", "postfixe", "largeur"], width=12, state="readonly").grid(row=0, column=3, padx=5, pady=5)
ttk.Button(traversal_frame, text="Afficher parcours", command=self.run_traversal).grid(row=0, column=4, padx=5, pady=5)
# Output traversal
self.traversal_output = tk.Text(frm, height=4)
self.traversal_output.pack(fill="x", padx=10, pady=5)
# Canvas
canvas_frame = ttk.Frame(frm)
canvas_frame.pack(fill="both", expand=True, padx=5, pady=5)
self.canvas_a = tk.Canvas(canvas_frame, bg="white", width=960, height=420)
self.canvas_a.pack(fill="both", expand=True)
self.tree_canvas_a = TreeCanvas(self.canvas_a)
# Internal storage of last arrays
self.last_perfect_array = []
self.last_any_array = []
def parse_csv(self, s):
return [x.strip() for x in s.split(",") if x.strip() != ""]
def draw_perfect_tree(self):
try:
h = int(self.h_var.get())
vals = self.parse_csv(self.values_perfect_var.get())
levels = build_perfect_tree_values(h, vals)
self.tree_canvas_a.draw_nodes_edges(levels)
# Store flat array for traversals (level-order)
self.last_perfect_array = vals[:] # already level-order
except Exception as e:
messagebox.showerror("Erreur", str(e))
def draw_any_tree(self):
try:
tokens = [t.strip() for t in self.values_any_var.get().split(",")]
levels = build_arbitrary_tree_from_level_order(tokens)
self.tree_canvas_a.draw_nodes_edges(levels)
# Store flat array (level-order) for traversals
# Flatten levels back to array with appropriate width
arr = []
for lvl, nodes in enumerate(levels):
# ensure len is 2**lvl
needed = 2 ** lvl
padded = nodes + [None] * (needed - len(nodes)) if len(nodes) < needed else nodes
arr.extend(padded)
self.last_any_array = arr
except Exception as e:
messagebox.showerror("Erreur", str(e))
def run_traversal(self):
target = self.traversal_target_var.get()
arr = self.last_perfect_array if target == "parfait" else self.last_any_array
if not arr:
messagebox.showwarning("Attention", "Aucun arbre chargé pour ce mode.")
return
t = self.traversal_type_var.get()
if t == "infixe":
res = array_inorder(arr)
elif t == "prefixe":
res = array_preorder(arr)
elif t == "postfixe":
res = array_postorder(arr)
else:
res = array_breadth(arr)
self.traversal_output.delete("1.0", "end")
self.traversal_output.insert("end", "Parcours (" + t + "): " + " ".join(map(str, res)))
# ------------- Partie B -------------
def build_tab_b(self, parent):
frm = ttk.Frame(parent, padding=10)
frm.pack(fill="both", expand=True)
controls = ttk.LabelFrame(frm, text="Construction ABR")
controls.pack(side="top", fill="x", padx=5, pady=5)
ttk.Label(controls, text="Clés initiales (séparées par des virgules):").grid(row=0, column=0, sticky="w", padx=5, pady=5)
self.bst_keys_var = tk.StringVar(value="50,30,70,20,40,60,80")
ttk.Entry(controls, textvariable=self.bst_keys_var, width=50).grid(row=0, column=1, sticky="w", padx=5)
ttk.Button(controls, text="Construire ABR", command=self.build_bst).grid(row=0, column=2, padx=5, pady=5)
insert_frame = ttk.LabelFrame(frm, text="Insertion")
insert_frame.pack(side="top", fill="x", padx=5, pady=5)
ttk.Label(insert_frame, text="Insérer clé:").grid(row=0, column=0, padx=5, pady=5)
self.bst_insert_var = tk.StringVar(value="65")
ttk.Entry(insert_frame, textvariable=self.bst_insert_var, width=10).grid(row=0, column=1, padx=5, pady=5)
ttk.Button(insert_frame, text="Insérer", command=self.insert_bst_key).grid(row=0, column=2, padx=5, pady=5)
traversal_frame = ttk.LabelFrame(frm, text="Parcours ABR")
traversal_frame.pack(side="top", fill="x", padx=5, pady=5)
ttk.Button(traversal_frame, text="Afficher parcours infixe (ordonné)", command=self.bst_show_inorder).grid(row=0, column=0, padx=5, pady=5)
self.bst_output = tk.Text(frm, height=4)
self.bst_output.pack(fill="x", padx=10, pady=5)
canvas_frame = ttk.Frame(frm)
canvas_frame.pack(fill="both", expand=True, padx=5, pady=5)
self.canvas_b = tk.Canvas(canvas_frame, bg="white", width=960, height=420)
self.canvas_b.pack(fill="both", expand=True)
self.bst_canvas = BSTCanvas(self.canvas_b)
self.bst_root = None
def build_bst(self):
try:
keys = [self.parse_number(k) for k in self.parse_csv(self.bst_keys_var.get())]
self.bst_root = bst_build_from_keys(keys)
self.bst_canvas.draw_bst(self.bst_root)
except Exception as e:
messagebox.showerror("Erreur", str(e))
def insert_bst_key(self):
try:
key = self.parse_number(self.bst_insert_var.get())
if self.bst_root is None:
self.bst_root = BSTNode(key)
else:
self.bst_root = bst_insert(self.bst_root, key)
self.bst_canvas.draw_bst(self.bst_root)
except Exception as e:
messagebox.showerror("Erreur", str(e))
def bst_show_inorder(self):
def inorder(node):
return inorder(node.left) + [node.key] + inorder(node.right) if node else []
res = inorder(self.bst_root)
self.bst_output.delete("1.0", "end")
self.bst_output.insert("end", "Infixe (trié): " + " ".join(map(str, res)))
@staticmethod
def parse_number(s):
s = str(s).strip()
# Accept integers or floats; prefer int if possible
try:
return int(s)
except ValueError:
return float(s)
# =========================
# Lancement
# =========================
if __name__ == "__main__":
app = App()
app.mainloop()
Créé avec HelpNDoc Personal Edition: Écrire des livres électroniques ePub pour l'iPad