Créer un arbre binaire de taille fixe

Question

J'essaye de créer un arbre binaire. La seule chose que l'on me donne est le nombre de nœuds dans l'arbre. La première chose qui m'est venue à l'esprit est d'utiliser un index (BFS order) pour garder la trace du nombre total de nœuds, puis utiliser une définition récursive. Voici mon pseudo-code pour le faire.

N = 10   //binary tree total node count 
i = 0   //global integer 
function() 
    if i > N 
     return True 

    create node i 
    i = i + 1 
    function(i) //left 
    i = i + 1 
    function(i) //right 

-je utiliser une variable globale dans cette définition qui me fait me sentir comme peut-être je viole les règles de récursion. Y at-il une meilleure façon de faire ce que je fais, si c'est le cas, peut-elle être améliorée?

Note: Je pose des questions sur la méthode théorique, pas sur le code.

Modifier: Je viens de réaliser que cette méthode échoue. Je suis ouvert aux suggestions. L'exigence pour cet arbre n'est pas d'ajouter un élément à une profondeur, si la profondeur précédente n'est pas remplie de nœuds (tous les nœuds ont 2 enfants), excusez-moi de ne pas le mentionner auparavant, comme pour la pile que j'ai mentionnée dans les commentaires, cela n'a rien à voir avec la question, juste la façon régulière de parcourir les arbres de façon itérative.

Answer 1

Un arbre se compose de trois éléments si elle est définie de manière récursive:

• un noeud racine
• un sous-arbre gauche, qui est un arbre lui-même
• un sous-arbre droit, qui est un arbre lui-même

tous ces éléments peuvent être NULL.

Maintenant, nous pouvons distribuer les nombres dans une plage [a, b] dans un arbre de la manière suivante:

• racine contient (a + b)/2
• sous-arbre gauche est construit de la gamme [a, (a + b)/2 - 1] récursive
• sous-arbre droit est construit la plage [(a + b)/2 + 1, b] récursivement

Une plage avec un début plus élevé que la fin peut être consi défini comme vide et aboutit à un noeud NULL. Cette distribution garantit que les sous-arbres gauche et droit diffèrent au maximum d'une taille et que chaque niveau est entièrement rempli, avant qu'un autre niveau ne soit rempli.

.: par exemple

N = 6 
            [0, 5] 

       [0, 1]    2     [3, 5] 

     [0]  1  []    [3]   4   [5] 

[]  0  []      []  3  []  [] 5 [] 

En plus cet algorithme construit un BST (en fait ce essentiellement le « inverse » d'une recherche binaire).Maintenant, pour l'algorithme lui-même:

function(a, b): 
    if b < a: return NULL 

    n = create node (a + b)/2 
    n.left = function(a, (a + b)/2 - 1) 
    n.right = function((a + b)/2 + 1, b) 

    return n 

L'arbre peut être généré en appelant:

function(1, N) 

Sinon tous les autres paramètres a et b devrait fonctionner, où a + N - 1 = b détient. Les deux paramètres représentent la plage (les deux inclus) qui devrait être tenue par l'arbre.