Arbre Binaire Insérer Algorithme

J'ai récemment terminé la mise en œuvre d'un arbre de recherche Binaire pour un projet sur lequel je travaillais. Ça s'est bien passé et j'ai beaucoup appris. Cependant, maintenant, j'ai besoin de mettre en œuvre régulière d'un Arbre Binaire... ce qui m'a déconcerté.

Je suis à la recherche d'un moyen de faire de mon InsertNode fonction..

normalement, dans un BST que vous venez de vérifier si les données < racine puis insérez la gauche et vice-versa. Cependant, Dans un arbre Binaire, c'est juste rempli de gauche à droite, d'un niveau à un moment..

quelqu'un pourrait-il m'aider à mettre en œuvre une fonction qui ajoute un nouveau Nœud de l'arbre Binaire de gauche à droite dans aucun ordre particulier?

Voici mon Insert pour un BST:

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

Un arbre de recherche binaire est un arbre binaire dans lequel les données dans les nœuds est commandé d'une manière particulière. Donc, si vous avez mis en place un BST, vous avez peu de choses à faire...
La droite. C'est là que je suis bloqué, si, je ne vois pas le moyen de le faire simplement...
dois-je viens de changer la < > vérification pour voir si ils sont Nuls?
A ma réponse vous aider avec le problème? Est-il autre chose que tu aimerais m'étendre sur?

OriginalL'auteur Taylor | 2013-05-19

binary-search-tree binary-tree c++insert tree

Je suis conscient du fait que c'est une question posté il y a quelques temps, mais je voulais quand même partager mes pensées sur elle.

Ce que je voudrais faire (puisque ce n'est en effet pas très bien documenté) est l'utilisation d'un large éventail de la Première Recherche (à l'aide d'une file d'attente) et insérer l'enfant dans la première null je rencontre. Cela permettra d'assurer que votre arbre va se remplir d'abord avant qu'il ne passe à un autre niveau. Avec le bon nombre de nœuds, il sera toujours complet.

Je n'ai pas travaillé beaucoup avec le c++, donc, pour être sûr que c'était correct, je l'ai fait en Java, mais vous voyez l'idée:

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

OriginalL'auteur bknopper

Javascript mise en œuvre (copier-coller prêt pour votre console web):

ES6 mise en œuvre (plus récente javscript syntaxe avec mot-clé class)

  class BinaryTree {
      constructor(value){
          this.root = value;
          this.left = null;
          this.right = null;
      }

      insert(value){
          var queue = [];
          queue.push(this); //push the root
          while(true){
              var node = queue.pop();
              if(node.left === null){
                  node.left = new BinaryTree(value);
                  return;
              } else {
                  queue.unshift(node.left)
              }

              if(node.right === null){
                node.right = new BinaryTree(value);
                return;
              } else {
                queue.unshift(node.right)
              }
          }
      }
  }

  var myBinaryTree = new BinaryTree(5);
  myBinaryTree.insert(4);
  myBinaryTree.insert(3);
  myBinaryTree.insert(2);
  myBinaryTree.insert(1);

     5
   /   \
  4     3
 / \   (next insertions here)
 2  1

Pseudoclassical modèle de mise en œuvre

  var BinaryTree = function(value){
    this.root = value;
    this.left = null;
    this.right = null;
  }

  BinaryTree.prototype.insert = function(value){
    //same logic as before
  }

OriginalL'auteur cacoder

J'ai pris bknopper code, modifié un peu traduits et C++. Comme il l'a dit, de façon surprenante, ce n'est pas bien documentée.

Ici est le nœud de la structure et de la fonction insérer:

struct nodo
{
    nodo(): izd(NULL), der(NULL) {};
    int val;
    struct nodo* izd;
    struct nodo* der;
};

void inserta(struct nodo** raiz, int num)
{

if( !(*raiz) )
{
    *raiz = new struct nodo;
    (*raiz)->val = num;
}
else
{

    std::deque<struct nodo*>  cola;
    cola.push_back(  *raiz  );

    while(true)
    {
        struct nodo *n = cola.front();
        cola.pop_front();

        if( !n->izd ) {
            n->izd = new struct nodo;
            n->izd->val = num;
            break;
        } else {
            cola.push_back(n->izd);
        }

        if( !n->der ) {
            n->der = new struct nodo;
            n->der->val = num;
            break;
        } else {
            cola.push_back(n->der);
        }
    }
  }
}

Vous appelez cela de cette façon:
inserta(&root, val);

Être root un pointeur vers le nœud struct et val la valeur de l'entier que vous souhaitez insérer.

Espère que cela aide quelqu'un.

Je ne sais pas C++ assez bien pour le faire moi-même, donc auriez-vous l'esprit en ajoutant une traduction en anglais (si possible)?

OriginalL'auteur 0aps

Avec quelques modifications de votre code, j'espère que cela permettra :

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

Par conséquent , cette fonction renvoie le nœud racine de la mise à jour du BST.

OriginalL'auteur Pratik Nagelia

-1

Vous devez essayer d'utiliser une approche récursive tels 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 quelques pseudo-code 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      
}

J'ai fait un tutoriel concernant la mise en œuvre d'un BST en C++, ici

OriginalL'auteur devjeetroy

Vous devez vous connecter pour publier un commentaire.