--------------------------------------------------------------------------
--             TD sur les arbres binaires - 06/11/02                    --
--             Fichier disponible sur ~benoit/TDAlgo/arbres.adb         --
--------------------------------------------------------------------------


with Ada.Text_IO, Ada.Integer_Text_IO;
use  Ada.Text_IO, Ada.Integer_Text_IO;

procedure Arbres is

  ------- Definition du type Arbre Binaire a l'aide de pointeurs  -------- 
  type Element is new Integer; -- A changer suivant le type d'arbre
                               -- que l'on desire utiliser.
  type Noeud;
  type Arbre is access Noeud;
  type Noeud is record 
    Val: Element;
    Gauche, Droit: Arbre;
  end record;
  

  ------------------------------------------------------------------------
  -- 1. Prise de contact avec les arbres binaires :                     --
  --     - dessiner des arbres binaires d'entiers                       --
  --             - quelconques                                          --
  --             - de hauteur maximum                                   --
  --             - de hauteur minimum                                   --
  --     - rappeler les relations entre la hauteur h et la taille n     --
  --     - definir ces arbres en Ada                                    --  
  ------------------------------------------------------------------------
  AbV: Arbre := null; -- l'arbre vide
  Ab1: Arbre := new Noeud'(1,null,null); -- arbre feuille 1


  ------------------------------------------------------------------------
  -- 2. Hauteur d'un arbre                                              --
  ------------------------------------------------------------------------
  function Hauteur(A: Arbre) return Integer is
  begin
    return -1;
  end;


  ------------------------------------------------------------------------
  -- 3. Recherche dans un arbre :                                       --
  --    Recherche(E,A) renvoie vrai ssi l'element E est                 --
  --    present dans l'arbre                                            --
  ------------------------------------------------------------------------
  function Recherche(E: Element; A: Arbre) return Boolean is
  begin
    return False;
  end;


  ------------------------------------------------------------------------
  -- 4. Arbres symetriques :                                            --
  --    Le symetrique d'un arbre binaire A est un arbre binaire B       --
  --    deduit de A en faisant correspondre un sous-arbre droit a tout  --
  --    sous-arbre gauche et vice-versa : tout se passe comme si B      --
  --    etait l'image de A dans un miroir.                              --
  --    Exemple :                                                       --
  --          A                                A                        --
  --         / \                              / \                       --
  --        B   C    a pour symetrique       C   B                      --
  --       /   / \                          / \   \                     --
  --      D   E   F                        F   E   D                    --
  --           \                              /                         --
  --            G                            G                          --
  --                                                                    --
  --   - Fonction EstSym: deux arbres sont-ils symetriques?             --
  --   - Fonction LeSym : construction de l'arbre symetrique d'un arbre --
  ------------------------------------------------------------------------
  function EstSym (A1,A2: Arbre) return Boolean is
  begin
    return False;
  end;


  function LeSym (A: Arbre) return Arbre is
  begin
    return null;
  end;


  ------------------------------------------------------------------------
  -- 5. Egalite des elements d'un arbre :                               --
  --    TousEgaux(A) renvoie vrai ssi tous les elements de A sont       --
  --    egaux entre eux.                                                --
  --    On pourra introduire une fonction intermediaire determinant si  --
  --    les elements d'un arbre sont tous egaux a un element donne.     --
  ------------------------------------------------------------------------
  function TousEgaux(A: Arbre) return Boolean is
  begin
    return False;
  end;


  ------------------------------------------------------------------------
  -- 6. Affichage d'un arbre : pour les tests                           --
  ------------------------------------------------------------------------
  procedure Indent(N: in Natural) is
  begin
    for I in 1..N loop Put(' '); end loop;
  end;
  procedure Affiche(A: in Arbre) is
    procedure Aux(A: in Arbre; N: in Natural; S: in String) is
    begin 
      if A/=null then
        Indent(N); Put(S); Put_Line(Element'Image(A.Val));
        Aux(A.Gauche, N+3, "Gauche: ");
        Aux(A.Droit,  N+3, "Droit : ");
      end if;
    end;
  begin
    Aux(A,0,"Racine: ");
  end;


-------------------------------------------------------------------------
begin
  Put_Line("Manipulations sur les arbres");

  Put_Line("Affichage de l'arbre vide :");
  Affiche(AbV);

  Put_Line("Affichage de l'arbre feuille 1 :");
  Affiche(Ab1);

end;