recorrido - ejercicios resueltos de arboles binarios en c++

Insertar un elemento en el árbol binario

Question

Intenté explorar mucho en la red, pero podría obtener ayuda. En todas partes es como agregar un nodo al árbol de búsqueda binaria.

Pregunta: solicitud de algoritmo y fragmento de código para agregar un nodo al árbol binario . (o dirígeme a la URL correcta)

Asunción: Según mi entendimiento, ¿el árbol binario y el árbol de búsqueda binaria son diferentes? Corrígeme si estoy equivocado.

(solicitud: si está escribiendo su fragmento de código, utilice el nombre de la variable adecuada, que ayude a comprenderlo)

Ej: Árbol binario

5 7 3 x1 x2 x3

                 5

          7               3

   x1       x2       x3       

Árbol de búsqueda binaria 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 );
    }
}

Answer 1

Dado que, no puedo comentar, estoy escribiendo esto.
La respuesta anterior para la función de inserción de árbol binario es incorrecta.
Supongamos que 0, 1, 2, 3, 4, 5 pasan en secuencia para insertar la función,
su árbol generando como

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

de los cuales el recorrido interno será 1 3 5 4 2 0
mientras que la respuesta debería ser

                     0
                   /  /
                  1    2 
                 / /  /  
                3   4 5

de los cuales el recorrido interno será 3 1 4 0 5 2.

Answer 2

Como también enfrento el mismo problema, se me ocurrió la siguiente solución en la red:

Puede usar una cola para almacenar el nodo actual donde queremos colocar el nuevo nodo como lo hacemos en el recorrido de nivel de nivel y luego insertamos los nodos nivel por nivel.

El siguiente enlace puede ayudarte:

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

Answer 3

Estoy publicando esto como respuesta porque no tengo la reputación necesaria para publicar un comentario. Excepto por bagelboy, todos los demás han malentendido el árbol como árbol de búsqueda binaria o árbol binario completo. La pregunta es simple Binary Tree y la respuesta de Bagelboy parece correcta.

Answer 4

Se puede utilizar una estructura de datos de cola para insertar elementos en un árbol binario, ya que en el árbol binario el orden de los nodos no se mantiene, por lo que insertaremos el nodo en cuanto encontremos algún nulo. Usando Queue atravesaremos el árbol binario en el recorrido de orden de nivel.

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

Answer 5

La diferencia entre un árbol binario y un árbol de búsqueda binaria es que aunque ambos tienen restricciones de que cada nodo puede tener como máximo 2 nodos secundarios, un árbol de búsqueda binaria (BST) también debe tener su hijo izquierdo de igual o menor valor y el su hijo correcto debe ser de mayor o igual valor. Esta es la razón por la que se llama árbol de búsqueda porque todo está ordenado numéricamente y tiene un tiempo de ejecución O (logn) para la búsqueda.

Debido a que no existe el requisito de ser una BST, un árbol binario se puede almacenar en un vector (matriz). A medida que insertas en el vector, construyes el árbol binario en orden de nivel. El código está abajo:

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