Skip to content

NSI - Terminale - projet arbre binaire

Interface avec Tkinter

Exemple de solution (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()
↑ Retour en haut