Tableau résumé des algorithmes classiques sur un arbre binaire

Catégorie	Algorithme	But / Explication	Exemple C# minimal
Parcours DFS	In-order	Visite : gauche → racine → droite	csharp void InOrder(Node root){ if(root==null) return; InOrder(root.left); Console.Write(root.val+" "); InOrder(root.right); }
	Pre-order	Visite : racine → gauche → droite	csharp void PreOrder(Node root){ if(root==null) return; Console.Write(root.val+" "); PreOrder(root.left); PreOrder(root.right); }
	Post-order	Visite : gauche → droite → racine	csharp void PostOrder(Node root){ if(root==null) return; PostOrder(root.left); PostOrder(root.right); Console.Write(root.val+" "); }
Parcours BFS	Level-order	Visite niveau par niveau	csharp void LevelOrder(Node root){ if(root==null) return; Queue<Node> q=new Queue<Node>(); q.Enqueue(root); while(q.Count>0){ var n=q.Dequeue(); Console.Write(n.val+" "); if(n.left!=null) q.Enqueue(n.left); if(n.right!=null) q.Enqueue(n.right); } }
Recherche	Chercher un nœud	Trouver un nœud avec valeur donnée	```bool Search(Node root,int x){ if(root==null) return false; if(root.val==x) return true; return Search(root.left,x)
Insertion	BST Insertion	Insérer dans un arbre binaire de recherche	Node Insert(Node root,int x){ if(root==null) return new Node(x); if(x<root.val) root.left=Insert(root.left,x); else root.right=Insert(root.right,x); return root; }
Suppression	BST Deletion	Supprimer un nœud d’un BST	Node Delete(Node root,int x){ if(root==null) return null; if(x<root.val) root.left=Delete(root.left,x); else if(x>root.val) root.right=Delete(root.right,x); else{ if(root.left==null) return root.right; if(root.right==null) return root.left; Node temp=root.right; while(temp.left!=null) temp=temp.left; root.val=temp.val; root.right=Delete(root.right,temp.val); } return root; }
Hauteur	Height	Hauteur / profondeur de l’arbre	int Height(Node root){ if(root==null) return 0; return 1+Math.Max(Height(root.left),Height(root.right)); }
Nombre de nœuds	CountNodes	Compter tous les nœuds	int CountNodes(Node root){ if(root==null) return 0; return 1+CountNodes(root.left)+CountNodes(root.right); }
Nombre de feuilles	CountLeaves	Compter les feuilles	int CountLeaves(Node root){ if(root==null) return 0; if(root.left==null&&root.right==null) return 1; return CountLeaves(root.left)+CountLeaves(root.right); }
Vérification BST	IsBST	Vérifier si arbre est BST	```bool IsBST(Node root,int min=int.MinValue,int max=int.MaxValue){ if(root==null) return true; if(root.val<=min
Lowest Common Ancestor	LCA	Trouver l’ancêtre commun le plus bas	```Node LCA(Node root,int n1,int n2){ if(root==null) return null; if(root.val==n1
Inversion	Mirror	Inverser arbre gauche-droite	void Mirror(Node root){ if(root==null) return; Node temp=root.left; root.left=root.right; root.right=temp; Mirror(root.left); Mirror(root.right); }
Serialization / Deserialization	Serialize / Deserialize	Convertir arbre en string et inverse	void Serialize(Node root,StringBuilder sb){ if(root==null){ sb.Append("#,"); return; } sb.Append(root.val+","); Serialize(root.left,sb); Serialize(root.right,sb); }

---

=======================================

Exemple complet en C# avec une classe Node :

using System;
using System.Collections.Generic;
using System.Text;

namespace BinaryTreeExample
{
    // Classe de base pour le nœud
    public class Node
    {
        public int val;
        public Node left;
        public Node right;

        public Node(int val)
        {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }

    public class BinaryTree
    {
        public Node root;

        public BinaryTree()
        {
            root = null;
        }

        // --------- Parcours DFS ----------
        public void InOrder(Node node)
        {
            if (node == null) return;
            InOrder(node.left);
            Console.Write(node.val + " ");
            InOrder(node.right);
        }

        public void PreOrder(Node node)
        {
            if (node == null) return;
            Console.Write(node.val + " ");
            PreOrder(node.left);
            PreOrder(node.right);
        }

        public void PostOrder(Node node)
        {
            if (node == null) return;
            PostOrder(node.left);
            PostOrder(node.right);
            Console.Write(node.val + " ");
        }

        // --------- Parcours BFS ----------
        public void LevelOrder(Node node)
        {
            if (node == null) return;
            Queue<Node> q = new Queue<Node>();
            q.Enqueue(node);
            while (q.Count > 0)
            {
                Node n = q.Dequeue();
                Console.Write(n.val + " ");
                if (n.left != null) q.Enqueue(n.left);
                if (n.right != null) q.Enqueue(n.right);
            }
        }

        // --------- Recherche ----------
        public bool Search(Node node, int x)
        {
            if (node == null) return false;
            if (node.val == x) return true;
            return Search(node.left, x) || Search(node.right, x);
        }

        // --------- Insertion BST ----------
        public Node Insert(Node node, int x)
        {
            if (node == null) return new Node(x);
            if (x < node.val) node.left = Insert(node.left, x);
            else node.right = Insert(node.right, x);
            return node;
        }

        // --------- Suppression BST ----------
        public Node Delete(Node node, int x)
        {
            if (node == null) return null;

            if (x < node.val) node.left = Delete(node.left, x);
            else if (x > node.val) node.right = Delete(node.right, x);
            else
            {
                if (node.left == null) return node.right;
                if (node.right == null) return node.left;

                Node temp = node.right;
                while (temp.left != null) temp = temp.left;

                node.val = temp.val;
                node.right = Delete(node.right, temp.val);
            }
            return node;
        }

        // --------- Hauteur ----------
        public int Height(Node node)
        {
            if (node == null) return 0;
            return 1 + Math.Max(Height(node.left), Height(node.right));
        }

        // --------- Nombre de nœuds ----------
        public int CountNodes(Node node)
        {
            if (node == null) return 0;
            return 1 + CountNodes(node.left) + CountNodes(node.right);
        }

        // --------- Nombre de feuilles ----------
        public int CountLeaves(Node node)
        {
            if (node == null) return 0;
            if (node.left == null && node.right == null) return 1;
            return CountLeaves(node.left) + CountLeaves(node.right);
        }

        // --------- Vérifier BST ----------
        public bool IsBST(Node node, int min = int.MinValue, int max = int.MaxValue)
        {
            if (node == null) return true;
            if (node.val <= min || node.val >= max) return false;
            return IsBST(node.left, min, node.val) && IsBST(node.right, node.val, max);
        }

        // --------- Lowest Common Ancestor ----------
        public Node LCA(Node node, int n1, int n2)
        {
            if (node == null) return null;
            if (node.val == n1 || node.val == n2) return node;

            Node l = LCA(node.left, n1, n2);
            Node r = LCA(node.right, n1, n2);

            if (l != null && r != null) return node;
            return l ?? r;
        }

        // --------- Inversion / Mirror ----------
        public void Mirror(Node node)
        {
            if (node == null) return;
            Node temp = node.left;
            node.left = node.right;
            node.right = temp;
            Mirror(node.left);
            Mirror(node.right);
        }

        // --------- Serialization ----------
        public void Serialize(Node node, StringBuilder sb)
        {
            if (node == null)
            {
                sb.Append("#,");
                return;
            }
            sb.Append(node.val + ",");
            Serialize(node.left, sb);
            Serialize(node.right, sb);
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            BinaryTree tree = new BinaryTree();
            tree.root = tree.Insert(tree.root, 50);
            tree.Insert(tree.root, 30);
            tree.Insert(tree.root, 70);
            tree.Insert(tree.root, 20);
            tree.Insert(tree.root, 40);
            tree.Insert(tree.root, 60);
            tree.Insert(tree.root, 80);

            Console.WriteLine("InOrder Traversal:");
            tree.InOrder(tree.root);
            Console.WriteLine("\nLevelOrder Traversal:");
            tree.LevelOrder(tree.root);

            Console.WriteLine($"\nHeight: {tree.Height(tree.root)}");
            Console.WriteLine($"Total Nodes: {tree.CountNodes(tree.root)}");
            Console.WriteLine($"Leaves: {tree.CountLeaves(tree.root)}");

            Console.WriteLine($"Is BST: {tree.IsBST(tree.root)}");

            Node lca = tree.LCA(tree.root, 20, 40);
            Console.WriteLine($"LCA of 20 and 40: {lca.val}");

            tree.Mirror(tree.root);
            Console.WriteLine("InOrder Traversal after Mirror:");
            tree.InOrder(tree.root);

            StringBuilder sb = new StringBuilder();
            tree.Serialize(tree.root, sb);
            Console.WriteLine($"\nSerialized Tree: {sb}");
        }
    }
}

---

Ce code inclut :

• DFS (in-, pre-, post-order)

• BFS / Level-order

• Recherche, Insertion, Suppression dans BST

• Hauteur, nombre de nœuds, nombre de feuilles

• Vérification BST

• Lowest Common Ancestor (LCA)

• Miroir / inversion

• Serialization

---

Return