J'ai récemment terminé la mise en œuvre d'un arbre de recherche binaire pour un projet que je travaillais. Cela s'est bien passé et j'ai beaucoup appris. Cependant, maintenant, j'ai besoin de mettre en place un arbre binaire régulier ... qui pour une raison quelconque m'a soulevé.
Je cherche un moyen de faire ma fonction d'insertion. P>
normalement dans une BST Vous venez de vérifier si des données Si quelqu'un pourrait m'aider à mettre en œuvre une fonction qui ajoute simplement un nouveau nœud à l'arbre binaire de gauche à droite en aucun ordre spécifique? p> Voici mon insert pour une BST: P> void Insert(Node *& root, int data)
{
if(root == nullptr)
{
Node * NN = new Node;
root = NN;
}
else
{
if(data < root->data)
{
Insert(root->left, data);
}
else
{
Insert(root->right, data);
}
}
}
5 Réponses :
Vous devriez essayer d'utiliser une approche récursive telle que x = nouveau (x), si vous savez ce que cela signifie. De cette façon, vous n'avez pas vraiment à vous soucier du nœud racine. Je vais écrire du pseudocode pour vous:
//public function
add(data){
root = add(data, root)
}
//private helper function
Node add(data, currentNode){
if(currentNode = 0)
return new Node(data)
if(data less than currentNode's data)
currentNode.left = add(data, currentNode.left)
if(data more than currentNode's data)
currentNode.right = add(data, currentNode.right)
return currentNode
}
Je suis conscient du fait que c'est une question postée il y a quelque temps, mais je voulais toujours partager mes pensées dessus.
Ce que je ferais (puisque cela n'est pas très bien documenté), utilise un Atteinte-première-recherche (à l'aide d'une file d'attente) et insérez l'enfant dans la première rencontre null que je rencontre. Cela garantira que votre arbre remplit d'abord les niveaux avant de passer à un autre niveau. Avec le bon nombre de nœuds, il sera toujours complet. P>
Je n'ai pas beaucoup travaillé avec C ++, alors d'être sûr qu'il était correct, je l'ai fait à Java, mais vous obtenez l'idée: p>
public void insert(Node node) {
if(root == null) {
root = node;
return;
}
/* insert using Breadth-first-search (queue to the rescue!) */
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
while(true) {
Node n = queue.remove();
if(!n.visited) System.out.println(n.data);
n.visited = true;
if(n.left == null) {
n.left = node;
break;
} else {
queue.offer(n.left);
}
if(n.right == null) {
n.right = node;
break;
} else {
queue.offer(n.right);
}
}
}
J'ai pris le code Bknopper, modifié un peu et traduit en C ++. Comme il a déclaré, étonnamment, ce n'est pas bien documenté.
Voici la structure de nœuds et la fonction d'insertion: Vous l'appelez de cette façon:
Etre root Un pointeur sur le noeud STRIT et VAL La valeur entière que vous souhaitez insérer. J'espère que cela aide quelqu'un. Insérer (& Root, Val);
Je ne sais pas assez bien C ++ pour le faire moi-même, alors voudriez-vous ajouter une traduction anglaise (si possible)?
Avec quelques modifications à votre code, j'espère que cela devrait aider:
Node * Insert(Node * root, int data)
{
if(root == nullptr)
{
Node * NN = new Node();
root = NN;
root->data = data;
root->left = root ->right = NULL;
}
else
{
if(data < root->data)
{
root->left = Insert(root->left, data);
}
else
{
root->right = Insert(root->right, data);
}
}
return root;
}
implémentation ES6 (nouvelle syntaxe JavScript avec mot-clé de classe) Mise en œuvre de modèle pseudoclassique
Un arbre de recherche binaire est un arbre binaire dans lequel les données des nœuds sont commandées d'une manière particulière. Donc, si vous avez mis en œuvre une BST, vous avez peu à faire ...
Droit. C'est là que je suis coincé cependant, je ne vois pas un moyen de faire cela simplement ...
Devrais-je simplement changer la vérification <> pour voir s'ils sont nuls?
Ma réponse a-t-elle aidé avec le problème? Y a-t-il autre chose que vous voudriez que je puisse élaborer?