Les permutations possibles de l'entrée de l'arbre binaire de recherche

Question

Je reçois une chaîne de caractères, par exemple "CPHBDZ". En insérant (dans cet ordre) les lettres dans un ABR j'obtiendrai:

  C
 / \
B   P
   / \
  H   Z
 /
D

Si on change l'ordre de la chaîne en "CBPHDZ" on obtiendra le même arbre. Et je dois trouver et lister toutes les permutations de la chaîne d'entrée qui donnent le même ABR. J'ai réussi à calculer le nombre de ces permutations, mais je n'arrive pas à trouver un algorithme pour les trouver réellement.

Answer 1

En supposant que vous ne faites pas de rotations (etc.) pour équilibrer l'arbre, vous pouvez déduire une réponse de la structure de l'arbre : les nouveaux nœuds sont toujours ajoutés en tant que descendants de nœuds existants, donc tout nœud plus haut dans l'arbre doit précéder ses propres descendants, mais peut être réarrangé à volonté avec ses "pairs" (tout ce qui n'est ni son parent ni descendant).

Par exemple, puisque vous avez C comme racine de l'arbre, C doit avoir été le premier élément lu du flux. Puisque ses descendants sont B et P, le prochain élément dans l'entrée devait être l'un de ces deux. B n'a pas de descendants, mais P en a deux : H et Z, donc ils ont dû être lus après P, mais peuvent être dans n'importe quel ordre par rapport à B. De même, Z peut être dans n'importe quel ordre par rapport à H et D, mais H doit précéder D.

Modifier : Pour générer toutes ces permutations, une façon simple (mais trompeuse) serait d'utiliser Prolog. Fondamentalement, vous encodez ces dépendances en tant que "faits", et il générera toutes les permutations qui correspondent à ces faits. En fait (sans jeu de mots), c'est à peu près une description de ce qu'est/faire Prolog.

Le faire par vous-même, vous voudriez probablement faire la majeure partie du travail de manière récursive. Un ordonnancement correct est une racine suivie de toute intercalation des ordres valides de ses descendants.

En ce qui concerne l'intercalation, vous généreriez (par exemple) un ordre valide du sous-arbre gauche et un ordre valide du sous-arbre droit. Vous les mettez ensemble dans un tableau avec tous les éléments du sous-arbre gauche au début, et tous ceux du sous-arbre droit à la fin. Pour la démonstration, supposons que l'arbre contient également un A (comme descendant du B que vous montrez). Dans un tableau, nos données de nos sous-arbres ressembleraient à :

B A P H Z D

Ensuite, nous commençons par le dernier élément du sous-arbre gauche, et "marchons" chacun à travers le tableau vers la droite, générant une nouvelle permutation à chaque fois :

B P A H Z D
P B A H Z D
B P H A Z D
P B H A Z D
P H B A Z D
[ ... ]    

Pour chaque ordre valide du sous-arbre gauche, vous devez faire toutes ces intercalations avec chaque ordre valide du sous-arbre droit (et le renvoyer au parent, qui fera la même chose).

Answer 2

En Python,

arbre = {
    'C' : ['B', 'P'],
    'P' : ['H','Z'],
    'H' : ['D']}

def f(arbre, pret):
    if not pret:
        return [[]]
    else:
        rv = []
        for r in pret:
            for rest in f(arbre,
                          [n for n in pret if r != n] + arbre.get(r, [])):
               rv.append([r] + rest)
        return rv

for o in f(arbre, 'C'):
    print ''.join(o)