Insérer un élément dans un arbre binary

J’ai essayé d’explorer beaucoup de choses sur le net, mais je pouvais obtenir de l’aide. Partout, cela revient à append un nœud à l’arbre de recherche binary.

Question: Demande d’algorithme et d’extrait de code pour l’ajout d’un nœud à l’ arborescence binary . (ou pointez-moi pour corriger l’URL)

Hypothèse: selon ma compréhension, l’ arbre binary et l’ arbre de recherche binary sont-ils différents? Corrigez-moi si je me trompe.

(demande: si vous écrivez votre extrait de code, veuillez utiliser le nom de variable approprié, ce qui facilite la compréhension)

Par exemple: arbre binary

5 7 3 x1 x2 x3

5 7 3 x1 x2 x3 

Arbre de recherche binary 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 data) { insert( key, &(*root)->left ); } else if(key > (*root)->data) { insert( key, &(*root)->right ); } } 

La différence entre un arbre binary et un arbre de recherche binary réside dans le fait que, bien qu’ils aient tous deux des ressortingctions selon lesquelles chaque nœud peut avoir au plus 2 nœuds enfants, un arbre de recherche binary (BST) doit également avoir son enfant gauche de valeur égale son enfant juste doit être de valeur supérieure ou égale. C’est pourquoi il s’appelle une arborescence “Recherche” car tout est ordonné numériquement et qu’il a une durée d’exécution de O (logn) pour la recherche.

Comme il n’est pas nécessaire d’être un BST, un arbre binary peut être stocké dans un vecteur (tableau). Lorsque vous insérez dans le vecteur, vous construisez l’arbre binary en ordre de niveau. 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; } } } 

Une structure de données Queue peut être utilisée pour insérer un élément dans un arbre binary, étant donné que l’ordre des noeuds n’est pas maintenu dans l’arbre binary. Nous allons donc insérer le noeud dès que nous trouverons une valeur null. À l’aide de File d’attente, nous allons parcourir l’arbre binary lors de la traversée des ordres.

 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; } } 

Depuis, je ne peux pas commenter, j’écris ceci.
La réponse ci-dessus pour la fonction d’insertion d’arborescence binary est incorrecte.
Supposons que 0, 1, 2, 3, 4, 5 passent en séquence pour insérer une fonction,
son arbre générateur comme

  0 / 1 \ 2 / 3 \ 4 / 5`

dont traversée en ordre sera 1 3 5 4 2 0
alors que la réponse devrait être

  0 / \ 1 2 / \ / 3 4 5 

dont traversée en ordre sera 3 1 4 0 5 2.

Puisque je suis également confronté au même problème, je suis venu avec la solution suivante sur le net: –

Vous pouvez utiliser une queue pour stocker le nœud actuel sur lequel nous voulons placer le nouveau nœud, comme nous le faisons lors du parcours ordre par niveau, puis nous insérons les nœuds niveau par niveau.

Le lien suivant peut vous aider: –

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

Je poste ceci comme réponse parce que je n’ai pas la réputation nécessaire pour poster un commentaire. À l’exception de bagelboy, tous les autres ont mal interprété l’arbre comme étant un arbre de recherche binary ou un arbre binary complet. La question est simple. La réponse de Binary Tree et Bagelboy semble correcte.