<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
Step7:  Arbres binaires
Le but de ce TP est d'implanter les fonctions usuelles telles que la génération exhaustive (fabriquer tous les éléments de l'ensemble), rank et unrank sur l'ensemble des arbres binaires.  
Pour représenter les arbres binaires en python, on utilisera la structure suivante.
Exécutez les cellules suivantes et observez les exemples.
Step8:  Il y a 5 arbres binaires de taille 3. L'un deux est celui que nous venons de construire. 
Construisez explicitement les 4 autres
Step19:  Le but de ce TP est d'implanter les fonctions de la classe BinaryTrees ci-dessous (avec un "s" à la fin) qui représente l'ensemble des arbres binaires d'une taille donnée. La structure de la classe vous est donnée ainsi que les méthodes de base.
Complétez les méthodes manquantes puis exécutez les exemples ci-dessous.
Step20:  La suite de tests que nous avions définies sur les permutations peut aussi s'appliquer sur les arbres binaires. 
Exécutez la cellule suivante puis vérifiez que les tests passent sur les exemples.
Step23:  Voici une fonction qui calcule un arbre binaire aléatoire. On se demande si chaque arbre est obenu avec une probabilité uniforme.
Exécutez les cellules ci-dessous puis déterminez expérimentalment si la distribution de probabilité est uniforme.
Step24:  La hauteur d'un arbre se calcule récursivement 
<ASSISTANT_TASK:>
Python Code:
class BinaryTree():
    
    def __init__(self, children = None):
        
        A binary tree is either a leaf or a node with two subtrees.
        
        INPUT:
            
            - children, either None (for a leaf), or a list of size excatly 2 
            of either two binary trees or 2 objects that can be made into binary trees
        
        self._isleaf = (children is None)
        if not self._isleaf:
            if len(children) != 2:
                raise ValueError("A binary tree needs exactly two children")
            self._children = tuple(c if isinstance(c,BinaryTree) else BinaryTree(c) for c in children)
        self._size = None
        
    def __repr__(self):
        if self.is_leaf():
            return "leaf"
        return str(self._children)
    
    def __eq__(self, other):
        
        Return true if other represents the same binary tree as self
        
        if not isinstance(other, BinaryTree):
            return False
        if self.is_leaf():
            return other.is_leaf()
        return self.left() == other.left() and self.right() == other.right()
    
    
    def left(self):
        
        Return the left subtree of self
        
        return self._children[0]
    
    def right(self):
        
        Return the right subtree of self
        
        return self._children[1]
    
    def is_leaf(self):
        
        Return true is self is a leaf
        
        return self._isleaf
    
    def _compute_size(self):
        
        Recursively computes the size of self
        
        if self.is_leaf():
            self._size = 0
        else:
            self._size = self.left().size() + self.right().size() + 1
    
    def size(self):
        
        Return the number of non leaf nodes in the binary tree
        
        if self._size is None:
            self._compute_size()
        return self._size
    
leaf = BinaryTree()
        
t = BinaryTree()
t
t.size()
t = BinaryTree([[leaf,leaf], leaf]) # a tree of size 2
t
t.size()
t = BinaryTree([leaf, [leaf,leaf]]) # a different tree of size 2
t
t.size()
t = BinaryTree([[leaf, leaf], [leaf, leaf]]) # a tree of size 3
t
t.size()
Explanation: Arbres binaires
Le but de ce TP est d'implanter les fonctions usuelles telles que la génération exhaustive (fabriquer tous les éléments de l'ensemble), rank et unrank sur l'ensemble des arbres binaires.  
Pour représenter les arbres binaires en python, on utilisera la structure suivante.
Exécutez les cellules suivantes et observez les exemples.
End of explanation
# t1 = BinaryTree(...)
# t2 = BinaryTree(...)
# t3 = BinaryTree(...)
# t4 = BinaryTree(...)
Explanation: Il y a 5 arbres binaires de taille 3. L'un deux est celui que nous venons de construire. 
Construisez explicitement les 4 autres
End of explanation
import math
import random
class BinaryTrees():
    
    def __init__(self, size):
        
        The combinatorial set of binary trees of size `size`
        
        INPUT:
        
            - size a non negative integers
        
        self._size = size
        
    def size(self):
        
        Return the size of the binary trees of the set
        
        return self._size
    
    def __repr__(self):
        
        Default string repr of ``self``
        
        return "Binary Trees of size " + str(self._size)
    
    def cardinality(self):
        
        Return the cardinality of the set
        
        # This is given to you
        n = self._size
        f = math.factorial(n)
        return math.factorial(2*n)/(f*f*(n+1))
    
    def __iter__(self):
        
        Iterator on the elements of the set
        
        # write code here
                    
    def first(self):
        
        Return the first element of the set 
        
        for t in self:
            return t
                    
    def rank(self,t):
        
        Return the rank of the binary tree t in the generation order of the set (starting at 0)
        
        INPUT:
        
            - t, a binary tree
        
        # write code here
    
    def unrank(self,i):
        
        Return the binary tree corresponding to the rank ``i`` 
        
        INPUT:
        
            - i, a integer between 0 and the cardinality minus 1
        
        # write code here
        
    def next(self,t):
        
        Return the next element following t in self
        
        INPUT :
        
            - t a binary tree
            
        OUPUT :
        
        The next binary tree or None if t is the last permutation of self
        
        # write code here
        
    
    def random_element(self):
        
        Return a random element of ``self`` with uniform probability
        
        # write code here
BinaryTrees(0)
list(BinaryTrees(0))
BinaryTrees(1)
list(BinaryTrees(1))
BinaryTrees(2)
list(BinaryTrees(2))
BT3 = BinaryTrees(3)
BT3
list(BT3)
t = BinaryTree(((leaf, leaf), (leaf, leaf)))
BT3.rank(t)
BT3.unrank(2)
BT3.next(t)
BT3.random_element()
Explanation: Le but de ce TP est d'implanter les fonctions de la classe BinaryTrees ci-dessous (avec un "s" à la fin) qui représente l'ensemble des arbres binaires d'une taille donnée. La structure de la classe vous est donnée ainsi que les méthodes de base.
Complétez les méthodes manquantes puis exécutez les exemples ci-dessous.
End of explanation
def test_cardinality_iter(S):
    assert(len(list(S)) == S.cardinality())
def test_rank(S):
    assert([S.rank(p) for p in S] == range(S.cardinality()))
    
def test_unrank(S):
    assert(list(S) == [S.unrank(i) for i in xrange(S.cardinality())])
    
def test_next(S):
    L = [S.first()]
    while True:
        p = S.next(L[-1])
        if p == None:
            break
        L.append(p)
    assert(L == list(S))
            
    
def all_tests(S):
    tests = {"Cardinality / iter": test_cardinality_iter, "Rank": test_rank, "Unrank": test_unrank, "Next": test_next}
    for k in tests:
        print "Testsing: "+ k
        try:
            tests[k](S)
            print "Passed"
        except AssertionError:
            print "Not passed"
all_tests(BinaryTrees(3))
all_tests(BinaryTrees(4))
all_tests(BinaryTrees(5))
all_tests(BinaryTrees(6))
Explanation: La suite de tests que nous avions définies sur les permutations peut aussi s'appliquer sur les arbres binaires. 
Exécutez la cellule suivante puis vérifiez que les tests passent sur les exemples.
End of explanation
import random
def random_grow(t):
    
    Randomly grows a binary tree 
    
    INPUT:
    
        - t, a binary tree of size n
        
    OUTPUT: a binary tree of size n+1
    
    if t.is_leaf():
        return BinaryTree([leaf,leaf])
    c = [t.left(),t.right()]
    i = random.randint(0,1)
    c[i] = random_grow(c[i])
    return BinaryTree(c)
def random_binary_tree(n):
    
    Return a random binary tree of size n
    
    t = leaf
    for i in xrange(n):
        t = random_grow(t)
    return t
random_binary_tree(10)
Explanation: Voici une fonction qui calcule un arbre binaire aléatoire. On se demande si chaque arbre est obenu avec une probabilité uniforme.
Exécutez les cellules ci-dessous puis déterminez expérimentalment si la distribution de probabilité est uniforme.
End of explanation
assert BinaryTree([[leaf,leaf], leaf]).height() == 2
assert BinaryTree([leaf,[leaf, leaf]]).height() == 2
assert BinaryTree([[leaf,leaf], [leaf,leaf]]).height() == 2
assert BinaryTree([[leaf,[leaf,leaf]], [leaf,leaf]]).height() == 3
Explanation: La hauteur d'un arbre se calcule récursivement : pour une feuille, la hauteur est 0, sinon c'est le max de la hauteur des fils +1. 
Rajoutez une méthode height à la classe des arbres binaires et vérifiez son fonctionnement avec les tests suivants.
End of explanation
<END_TASK>