L'insertion d'un élément dans l'Arbre Binaire

Essayé d'explorer beaucoup de choses sur le net, mais il pourrait obtenir de l'aide,
Partout sa comme l'ajout d'un nœud de l'arbre de Recherche Binaire.

Question: pour Demander de l'algorithme et de l'extrait de code pour l'ajout d'un nœud à l' arbre Binaire. ( ou point de moi de corriger l'URL )

Hypothèse:
Selon ma compréhension, Arbre Binaire et Binaires de Recherche Arbres est-il différent? Corrigez-moi si je me trompe.

( demande: si vous écrivez sur votre extrait de code, veuillez utiliser un nom de variable, qui permet de comprendre )

Par Exemple: Arbre Binaire

5 7 3 x1 x2 x3

                 5

          7               3

   x1       x2       x3

Arbre De Recherche Binaire 5 7 3 2 4 6

                   5
          3               7

   2          4       6       





insert(int key, struct node **root)
{
    if( NULL == *root )`
    {
        *root = (struct node*) malloc( sizeof( struct node ) );`
        (*root)->data = key;
        (*root)->left = NULL;    
        (*root)->right = NULL;  
    }
    else if(key < (*root)->data)
    {
        insert( key, &(*root)->left );
    }
    else if(key > (*root)->data)
    {
        insert( key, &(*root)->right );
    }
}
Si vous parlez d'arbre de recherche binaire et si vous essayez de faire quelques instertion, peut-être que cela pourrait aider?: en.wikipedia.org/wiki/Binary_search_tree#Insertion
Mauvais arbre de recherche binaire
Dites moi ce sera le bon ordre de la STB.
insertHelper() dans le lien donné vérifie également pour la valeur < node->key , où comme arbre Binaire ne devrait pas déranger si la valeur est inférieure ou supérieure. il faut aller de l'avant et placez le prochain nœud à gauche, s'il est disponible ou bien à droite. J'espère que vous comprenez quelle est la différence entre un arbre Binaire et Binaire de Recherche est un Arbre? selon que pensez-vous de sa bonne.
BTW: l'exemple de la question ressemble à un binaire recherche arbre à moi.

OriginalL'auteur Raa | 2013-04-30

  1. 6

    La différence entre un Arbre Binaire et Binaire de Recherche est un Arbre que s'ils ont des restrictions que chaque nœud peut avoir au plus 2 nœuds enfants, un Arbre de Recherche Binaire (BST) doit aussi avoir sa gauche l'enfant être de valeur égale ou moindre et le droit de l'enfant doit être de valeur égale ou supérieure. C'est pourquoi il est appelé une "Recherche" de l'arbre, parce que tout est en ordre numérique et il a un O(logn) temps d'exécution pour la recherche.

    Car il n'y a pas l'obligation d'être un BST, un Arbre Binaire peut être stocké dans un vecteur (tableau). Comme vous l'insérez dans le vecteur construire l'Arbre Binaire dans un niveau de l'ordre de la mode. Le code est ci-dessous:

    //typedef the node struct to NODE
//nodeVector similar to STL's vector class
insert(int key, NODE** nodeVector)
{
    NODE *newNode = (NODE*) malloc( sizeof( NODE ) );
    newNode->data = key;
    newNode->left = NULL;    
    newNode->right = NULL;

    //add newNode to end of vector
    int size = nodeVector->size();
    nodeVector->push_back(newNode);

    //if newNode is not root node
    if(nodeVector->size() > 1)
    {
        //set parent's child values
        Node* parent = (size/2)-1; //take advantage of integer division instead of using floor()
        if (parent->left == NULL)
        {
            parent->left = newNode;
        }
        else
        {
            parent->right = newNode;
        }
    }
}
    Merci pour ces précisions @bagel. J'ai mis à jour mon BST code pour l'insertion, pouvez-vous s'il vous plaît suggérer quels changements dois-je intégrer à faire de ce BST à arbre Binaire
    poste le code que vous utilisez actuellement et je vais voir ce que je peux faire.
    juste posé dans la question, comme j'étais un peu mal à l'obtenir formaté. s'il vous plaît ignorer".
    que dois-je de gauche quand je suis à l'appel de l'insert() en fonction de mon principal ?
    vous êtes correct. Pour être juste, un Arbre Binaire (ou BST) n'a pas d'exigences sur le fait d'être équilibrée de façon techniquement, ce n'est pas incorrect. Si c'est une exigence supplémentaire que vous voulez dans votre BST alors jetez un oeil à AVL arbres. Cela étant dit, vous êtes totalement dans le droit d'avoir des problèmes avec mon code parce que c'est presque identique à une liste liée. Alors maintenant, avec un autre de 2 ans de l'éducation sous ma ceinture, je vais essayer de donner plus de solution. 🙂

    OriginalL'auteur sbru

  2. 2

    Une File d'attente de la structure de données peut être utilisé pour insérer un élément dans un Arbre Binaire, puisque dans l'Arbre Binaire de l'ordre de nœuds n'est pas maintenu nous allons donc insérer le nœud dès que nous trouvons nulle.
    À l'aide de la File d'attente nous allons de la traversée de l'Arbre Binaire dans l'Ordre de Niveau de la Traversée.

    struct Treenode* temp;

Q = CreateQueue();
EnQueue(Q,root);

while(!IsEmptyQueue(Q))
{
    temp = DeQueue(Q);
    if(temp->left)
        EnQueue(Q,temp->left);
    else
    {
        temp->left=newNode;
        DeleteQueue(Q);
        return;
     }
     if(temp->right)
        EnQueue(Q,temp->right);
    else
    {
        temp->right=newNode;
        DeleteQueue(Q);
        return;
     }
}

    OriginalL'auteur 9codie05

  3. 0

    Depuis, je ne peux pas commenter, je suis en train d'écrire.

    La réponse ci-dessus pour arbre binaire insérer une fonction qui est faux.

    Supposons que, pour 0, 1, 2 , 3, 4 , 5 passé dans la séquence à insérer une fonction,

    sa génération arbre comme 

           0
      /
     1
      \ 
       2
      /
     3
      \
       4
      /
     5`<br/>

    de qui afinde traversée sera 1 3 5 4 2 0

    alors que la réponse devrait être

                         0
                   /  \
                  1    2 
                 / \  /  
                3   4 5

    qui afinde traversée sera 3 1 4 0 5 2.

    Vous avez raison, au moment de revenir à cette réponse de 1,5 ans à travers mon diplôme, je vois mon erreur :). Je vais tenter de résoudre le problème. Merci
    Ok, j'ai fait quelques changements, quelles sont vos pensées sur elle maintenant?
    J'ai toujours des problèmes avec votre code. Je suis en commentant sous votre message directement.

    OriginalL'auteur codeFreak

  4. 0

    Depuis que j'ai aussi le même problème, je suis venu avec la solution sur le net :-

    Vous pouvez utiliser une file d'attente pour stocker le nœud actuel où nous voulons placer le nouveau nœud comme nous le faisons dans l'ordre de niveau de la traversée, puis nous insérons les nœuds de niveau par niveau.

    Lien suivant peut vous aider à :-

    http://www.geeksforgeeks.org/linked-complete-binary-tree-its-creation/

    OriginalL'auteur anonymous

  5. 0

    Je suis de poster cette réponse parce que je n'ai pas le nécessaire réputation pour poster un commentaire. Sauf pour bagelboy tous les autres ont mal compris l'arbre Binaire de Recherche de l'Arbre ou Arbre Binaire Complet. La question est simple Arbre Binaire et Bagelboy la réponse semble correct.

    OriginalL'auteur takesavy