Restaurer l'arbre binaire avec PreOrder et InOrder - Javascript

Quelqu'un pourrait-il m'apprendre comment restaurer un arbre binaire en utilisant des tableaux Prorder et Inorder. J'ai vu quelques exemples (aucun en JavaScript) et ils ont un sens, mais l'appel récursif ne renvoie jamais un arbre complet quand j'essaie d'écrire. J'adorerais voir des explications aussi. Voici un code pour commencer:Restaurer l'arbre binaire avec PreOrder et InOrder - Javascript

Création d'un nœud d'arborescence utilise ceci:

function Tree(x) { 
    this.value = x; 
    this.left = null; 
    this.right = null; 
}

Création de l'arbre utilise ceci:

function retoreBinaryTree(inorder, preorder) { 

}

Certains entrée de l'échantillon:

inorder = [4,2,1,5,3] 
preorder = [1,2,4,3,5,6] 

inorder = [4,11,8,7,9,2,1,5,3,6] 
preorder = [1,2,4,11,7,8,9,3,5,6]

EDIT Je travaillais là-dessus depuis des jours et j'étais incapable de me lever Avec une solution personnelle, j'ai cherché un peu (la plupart ont été écrits en Java). J'ai essayé d'imiter this solution mais en vain.

Source

2017-07-30 Stephen Agwu

belle, qu'avez-vous essayé? –

J'ai essayé de créer une fonction récursive appelée arbre de construction qui prenait la liste de précommande et d'inorder ainsi que les variables qui représentaient des nombres tels que start et end. La fonction crée un noeud, ajuste le début et la fin en fonction de l'indice de la valeur de ce noeud. Trouvez les noeuds gauche et droit s'ils existent, puis renvoyez le noeud. Le problème est qu'il n'a jamais retourné un arbre complet. Ici, je posterai où j'ai eu cette solution. –

Ceci est une solution en C++ que je pense que vous pouvez traduire sans problème:

/* keys are between l_p and r_p in the preorder array 

    keys are between l_i and r_i in the inorder array 
*/ 
Node * build_tree(int preorder[], long l_p, long r_p, 
      int inorder[], long l_i, long r_i) 
{ 
    if (l_p > r_p) 
    return nullptr; // arrays sections are empty 

    Node * root = new Node(preorder[l_p]); // root is first key in preorder 
    if (r_p == l_p) 
    return root; // the array section has only a node 

    // search in the inorder array the position of the root 
    int i = 0; 
    for (int j = l_i; j <= r_i; ++j) 
    if (inorder[j] == preorder[l_p]) 
     { 
     i = j - l_i; 
     break; 
     } 

    root->left = build_tree(preorder, l_p + 1, l_p + i, 
       inorder, l_i, l_i + (i - 1)); 
    root->right = build_tree(preorder, l_p + i + 1, r_p, 
       inorder, l_i + i + 1, r_i); 

    return root; 
}

Source

2017-07-30 22:49:48 lrleon

Restaurer l'arbre binaire avec PreOrder et InOrder - Javascript

Répondre

Questions connexes