Y a-t-il un moyen d'insérer un nouveau nœud dans un arbre binaire (pas BST) sans comparer des valeurs essentielles? Le code suivant ne fonctionne que pour les trois premiers nœuds.
5 Réponses :
dans Vous savez bien sûr pour le Suivant sinon Le code suivant ne fonctionne que pour les trois premiers nœuds.
si les deux laissés et droite sont non nuls que vous n'entrez pas, ce temps il était nécessaire de faire l'appel récursif sur l'une des deux branches et vous envisagerez la clé (alors insérerez-la commandée) pour décider lequel. Notez que les 2 tests sur NULL que vous avez fait ne sont pas corrects si vous insérez pour avoir un arbre de tri ... root-> gauche est null alors pourquoi faire l'appel récursif?
Un élément peut être lié à deux autres éléments plutôt qu'à un.
@nawh j'ai enlevé ma remarque, montage ma réponse, vous devez considérer la clé maintenant
La comparaison des valeurs est en réalité hors de propos, la seule pensée que vous devez faire est de définir un pointeur. Puisque vous ne spécifiez aucune exigence réelle, une solution pourrait être la suivante:
Modification d'une signature Un bit, alors vous avez maintenant un pointeur sur un nœud déjà alloué: C'est évidemment une approche imparfaite (l'arbre ne sera pas équilibré au moindre), traiter presque l'arborescence comme une liste liée, mais à ma meilleure compréhension de la question , c'est un exemple de la façon dont cela peut être fait.
Merci beaucoup, je vais essayer cela dès que possible.
La signature du noeud * et de la racine pourrait être morte mal, comme une tête en tête. Si cela échoue, un pointeur sur le pointeur root serait également une solution pragmatique. De plus, cela traite essentiellement l'arbre comme une liste liée, ce n'est donc pas vraiment ce que vous recherchez.
Si vous modifiez
root->height = 1 + ((root->left->height > root->right->height) ? root->left->height : root->right->height);
Vous pouvez simplement garder une trace de la hauteur de chaque nœud et l'insérer toujours dans le côté avec moins d'enfants:
node *insert (node *root, int *key) {
if (root==NULL) {
root=newNode(root, key);
root->height = 0
}
else if (root->left == NULL) {
insert(root->left,key);
}
else if (root->right == NULL) {
insert(root->right,key);
}
else if (root->left->height <= root->right->height) {
insert(root->left,key);
} else {
insert(root->right,key);
}
root->height++
}
Comme écrit, ce que vous appelez la hauteur, la taille de l'arbre (ou sous-arbre) est en fait. Je dis cela parce que vous incrémentez toujours la valeur sur insérer . Cela fonctionnera avec la taille, mais il serait préférable d'utiliser Terminologie plus courante . Hauteur mesure combien de niveaux d'enfants il y a. Ce que vous mesurez est le nombre total de descendants.
Le conseil du tas est le plus sain. Vous n'avez pas besoin de te casser quoi que ce soit, il suffit de suivre les règles qu'un élément d'index Une autre approche, utile lorsqu'il n'y a pas de tableau, mais les nœuds sont générés à la volée, est de remplir le niveau d'arbre. Notez qu'au niveau k a des enfants à 2 * k + 1 et 2 * k + 2 . k il y a 2 ** k emplacements, indexés de manière commode par un entier K-BIT. Interpréter l'index sous forme de chemin d'accès à l'arborescence (le bit clair dit à suivre l'enfant à gauche, le bit de réglage indique de suivre une droite), le long des lignes de:
Insérez des éléments dans un tableau et effectuez un tas min / max, en utilisant des valeurs d'index. L'arbre résultant sera un arbre binaire.
Appel simple Min / Max tas.
Merci, mais ne vous laissez pas des restrictions sur la valeur racine (c'est-à-dire que cela doit être le minimum ou le maximum)?
Pour être clair, vous voulez juste que certains clés arbitraires insérés dans un arbre?
Oui, les valeurs clés sont en réalité des pointeurs plutôt que des entiers. Lorsqu'une clé est créée, elle devrait aller au premier espace disponible.
Pendant que j'ai fait une réponse, il me manque peut-être le point. Qu'est-ce que vous essayez réellement de réaliser en utilisant un arbre? À quoi essayez-vous de l'utiliser pour servir?