// Structure des donnees : arbre binaire avec mliste
funcprot(0)
function A = leaftree(el) 
    A = list(el)    // construit simplement une liste d'un element
endfunction

function Bool = leaftree?(A)  // renvoie true ou false
    Bool = (length(A)==1)
endfunction

function A = growtree(r,Ag,Ad)
    A = list(r,Ag,Ad)
endfunction

function r = rootnode(A)
    r = A(1)
endfunction

function Ag = left(A)
    Ag = A(2)
endfunction

function Ag = right(A)
    Ag = A(3)
endfunction

//-----------------------------------
// Quelques fonction sur l'arbre
//-----------------------------------

// nombre de noeuds d'un arbre
function n = numbernodes(A)
    if (leaftree?(A)) then
        n = 1
    else  //!!! 2 appels recursifs !!!
        n = 1+numbernodes(left (A))+numbernodes(right (A)) //!!! appel recursif !!!
    end
endfunction

// Hauteur d'un arbre ; max est une fonction de scilab
// qui renvoie le plus grand des deux arguments

function h = height(A)
    if (leaftree?(A)) then
        h = 0
    else //!!! 2 appels recursifs !!!
        h = 1+max(height(left (A)),height(right (A)))
    end 
endfunction

// recherche de la presence d'un element (key) dans un ABR (A)
// renvoie True ou False
function bool = present?(A,key)
    if (leaftree?(A)) then
        bool =(key == rootnode(A)) // bool prend la valeur resultante (true ou false) du test d'egalite
    elseif (key == rootnode(A))
        bool = %t                  // %t ou %T = variable booleenne de valeur true et %f = false
    elseif (key < rootnode(A))
        bool = present?(left(A),key)   //!!! appel recursif !!!
    else
        bool = present?(right(A),key)  //!!! appel recursif !!!      
    end
endfunction

// ordlist retourne le vecteur ordonne des c les 
// d'un arbre binaire de recherche c'est donc un tri sur
// les branches gauches puis droites de l'arbre.

// A noter : lstcat est une fonction de scilab qui concatene les listes
// passees en arguments en une liste unique.

function l = ordlist(A)
    if (leaftree?(A)) then
        l = A
    else
        r  = rootnode(A)
        lg = ordlist(left(A)) // on explore d'abord à gauche 
        lr = ordlist(right(A)) // puis à droite. !!! appels recursifs !!!
        lr(0)=r
        l  = lstcat(lg,lr)
    end
endfunction

// Minimum de l'ABR
function m = minBST(A)
    if (leaftree?(A)) then
        m = rootnode(A)
    else
        m = minBST(left(A))     //!!! appel recursif !!!
    end
endfunction

// Maximum de l'ABR
function m = maxBST(A)
    if (leaftree?(A)) then
        m = rootnode(A)
    else
        m = maxBST(right(A))     //!!! appel recursif !!!
    end
endfunction

//----------------------------------------------------------------------------//