Zoom sur le code

Les bases

Ce code est orienté objet, c'est-à-dire que j'utilise des class qui correspondent à un objet (ex: une table). Chaque objet a des propriétés et un comportement (ex: la table a 4 pieds un plateau et peut se plier).

Une class peut être instanciée, à ce moment là l'objet n'est plus conceptuel mais devient réel. Nous pouvons l'utiliser. Nous pouvons instancier autant de fois que l'on veut le même objet.

Pour illustrer ça la table dans le catalogue ikea serait une class mais une fois qu'on l'achète (instancie) nous pouvons l'utiliser comme bon nous semble. Nous pouvons aussi en acheter plusieurs pour en faire ce que l'on veut mais dans le catalogue la table n'apparaîtra toujours qu'une seule fois. C'est exactement comme cela que fonctionne un objet dans du code.

Résumons

• La table dans le catalogue est une class
• La (Les) table(s) qu'on achète sont des objets instanciés

Les classes que nous allons utiliser

Class Node

Rappelles-toi des nœuds et des lettres dans l'arbre ! Je t'avais dit que les lettres (qu'on peut appeler feuilles pour être plus générique) seraient considérées comme des nœuds.

C'est ici que nous allons décrire l'objet nœud qui peut être en réalité un nœud ou une feuille.

Nous allons donc utiliser 2 constructeurs (qui permettent d'instancier, de donner vie à l'objet). Le premier pour créer un véritable nœud et le second pour créer un nœud sans branche, donc une feuille.

• Les nœuds possèdent deux branches (droite et gauche) et un poids.

• Les feuilles possèdent une lettre et un poids.

• La signature sera utile plus tard, nous y stockeront le code binaire de chaque lettre.

internal class Node
{
    public Node Right { get; } // branche de droite
    public Node Left { get; } // branche de gauche

    public char Letter { get; } // Si feuille

    public string Signature { get; set; } // Code binaire selon Huffman
    public int Weight { get; } // poids du noeud

    // Constructeur noeud
    public Node(Node right, Node left, int weight)
    {
        Right = right;
        Left = left;
        Weight = weight;
    }

    // Constructeur feuille
    public Node(char letter, int weight)
    {
        Letter = letter;
        Weight = weight;
    }
}

Class BinaryTree

Cette classe sert à contenir l'arbre binaire. Ses propriétés sont:

• AddressMappingTable - Contient la table de correspondance entre les lettres et le code binaire.
• Nodes - Liste contenant tous les nœuds, n'en contiendra plus qu'un au final (celui d'en haut).

Dans cette classe il y a aussi une méthode qui permet de trouver les 2 minimums de la liste. Mais nous n'en parleront pas.

En revanche, il y une méthode très importante qui permet de parcourir l'arbre de manière itérative. Je vous invite à consulter sa documentation dans la rubrique Itératif / Récursif.

internal class BinaryTree
    {
        public static Dictionary<string, char> AddressMappingTable = new Dictionary<string, char>(); // Tableau de correspondance

        public List<Node> Nodes; // Liste de noeuds
        
        // Trouve les deux minimums
        public void FindTwoMinimums()
        {
            var min1 = Nodes[0];
            var min2 = Nodes[1];
            
            foreach (var node in Nodes)
            {
                if (node.Weight < Nodes[0].Weight)
                {
                    min1 = node;
                } 
                else if (node.Weight < Nodes[1].Weight)
                {
                    min2 = node;
                }
            }
            
            Nodes.Insert(0, min1);
            Nodes.Remove(min1);
            
            Nodes.Insert(1, min2);
            Nodes.Remove(min2);
        }

        // Parcourt l'arbre de manière itérative
        public void IterativeReading()
        {
            // Voir dans la rubrique appropriée...
        }
    }