in

Árbol binario | Conjunto 1 (Introducción)

gfg 200x200 min

Árboles: A diferencia de las matrices, las listas vinculadas, la pila y las colas, que son estructuras de datos lineales, los árboles son estructuras de datos jerárquicas.
Vocabulario de árboles: El nodo superior se llama raíz del árbol. Los elementos que están directamente debajo de un elemento se denominan hijos. El elemento directamente encima de algo se llama padre. Por ejemplo, ‘a’ es un hijo de ‘f’ y ‘f’ es el padre de ‘a’. Finalmente, los elementos sin hijos se llaman hojas.

      tree
      ----
       j    <-- root
     /   
    f      k  
  /         
 a     h      z    <-- leaves

¿Por qué árboles?
1. Una razón para usar árboles puede ser porque desea almacenar información que naturalmente forma una jerarquía. Por ejemplo, el sistema de archivos en una computadora:

file system
-----------
     /    <-- root
  /      
...       home
      /          
   ugrad        course
    /       /      |     
  ...      cs101  cs112  cs113

2. Los árboles (con algún orden, por ejemplo, BST) proporcionan acceso / búsqueda moderados (más rápido que Linked List y más lento que los arreglos).
3. Los árboles proporcionan una inserción / eliminación moderada (más rápido que las matrices y más lento que las listas enlazadas desordenadas).
4. Al igual que las listas vinculadas y, a diferencia de las matrices, los árboles no tienen un límite superior en el número de nodos, ya que los nodos están vinculados mediante punteros.
Las principales aplicaciones de los árboles incluyen:
1. Manipular datos jerárquicos.
2. Facilite la búsqueda de información (consulte el recorrido de árbol).
3. Manipule listas ordenadas de datos.
4. Como flujo de trabajo para la composición de imágenes digitales para efectos visuales.
5. Algoritmos de enrutador
6. Forma de toma de decisiones en varias etapas (ver ajedrez empresarial).
Árbol binario: Un árbol cuyos elementos tienen como máximo 2 hijos se llama árbol binario. Dado que cada elemento en un árbol binario puede tener solo 2 hijos, normalmente los llamamos hijo izquierdo y derecho.
Representación de árbol binario en C: Un árbol está representado por un puntero al nodo superior del árbol. Si el árbol está vacío, el valor de la raíz es NULL.
Un nodo de árbol contiene las siguientes partes.
1. Datos
2. Puntero al niño izquierdo
3. Puntero al niño derecho
En C, podemos representar un nodo de árbol usando estructuras. A continuación se muestra un ejemplo de un nodo de árbol con datos enteros.

C ++

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

Pitón

class Node:

    def __init__(self,key):

        self.left = None

        self.right = None

        self.val = key

Java

   

class Node

{

    int key;

    Node left, right;

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}

C#

class Node

{

    int key;

    Node left, right;

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}

Javascript

<script>

   

class Node

{

    constructor(item)

    {

        this.key = item;

        this.left = this.right = null;

    }

}

</script>

Primer árbol simple en C
Creemos un árbol simple con 4 nodos en C. El árbol creado sería el siguiente.

      tree
      ----
       1    <-- root
     /   
    2     3  
   /   
  4

C ++

#include <bits/stdc++.h>

using namespace std;

struct Node {

    int data;

    struct Node* left;

    struct Node* right;

    

    

    Node(int val)

    {

        data = val;

        

        

        left = NULL;

        right = NULL;

    }

};

int main()

{

    

    struct Node* root = new Node(1);

    

             

            

          

    

    root->left = new Node(2);

    root->right = new Node(3);

    

                    

                  

                 

               

            

    

    root->left->left = new Node(4);

    

               

            

           

          

         

        

     

    

    return 0;

}

C

#include <stdio.h>

#include <stdlib.h>

struct node {

    int data;

    struct node* left;

    struct node* right;

};

struct node* newNode(int data)

{

    

    struct node* node

        = (struct node*)malloc(sizeof(struct node));

    

    node->data = data;

    

    

    node->left = NULL;

    node->right = NULL;

    return (node);

}

int main()

{

    

    struct node* root = newNode(1);

    

         

        

      

    

    root->left = newNode(2);

    root->right = newNode(3);

    

            

         

        

      

   

    

    root->left->left = newNode(4);

    

             

         

        

      

     

    

 

    

    getchar();

    return 0;

}

Pitón

class Node:

    def __init__(self,key):

        self.left = None

        self.right = None

        self.val = key

root = Node(1)

        

      

     

root.left      = Node(2);

root.right     = Node(3);

  

           

         

        

     

   

root.left.left  = Node(4);

           

       

      

    

   

  

Java

   

class Node

{

    int key;

    Node left, right;

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}

class BinaryTree

{

    

    Node root;

    

    BinaryTree(int key)

    {

        root = new Node(key);

    }

    BinaryTree()

    {

        root = null;

    }

    public static void main(String[] args)

    {

        BinaryTree tree = new BinaryTree();

        

        tree.root = new Node(1);

        

              

            

          

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        

               

            

          

        

      

        tree.root.left.left = new Node(4);

        

                    

                

               

             

            

           

          

         

    }

}

C#

using System;

public class Node

{

    public int key;

    public Node left, right;

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}

public class BinaryTree

{

    

    Node root;

    

    BinaryTree(int key)

    {

        root = new Node(key);

    }

    BinaryTree()

    {

        root = null;

    }

    

    public static void Main(String[] args)

    {

        BinaryTree tree = new BinaryTree();

        

        tree.root = new Node(1);

        

             

            

         

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        

                

             

           

         

       

        tree.root.left.left = new Node(4);

        

        

                

             

           

         

         

        

     

        

    }

}

Resumen: El árbol es una estructura de datos jerárquica. Los principales usos de los árboles incluyen el mantenimiento de datos jerárquicos, el acceso moderado y las operaciones de inserción / eliminación. Los árboles binarios son casos especiales de árbol donde cada nodo tiene como máximo dos hijos.
https://youtu.be/W6aZKAJcNJA
A continuación se muestran los conjuntos 2 y 3 de esta publicación.
Propiedades del árbol binario
Tipos de árbol binario
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema discutido anteriormente.

¡Atención lector! No dejes de aprender ahora. Obtenga todos los conceptos importantes de DSA con el Curso autodidacta de DSA a un precio asequible para los estudiantes y prepárese para la industria. Para completar su preparación desde el aprendizaje de un idioma hasta DS Algo y muchos más, consulte Curso completo de preparación para entrevistas.

En caso de que desee asistir clases en vivo con expertos, consulte Clases en vivo de DSA para profesionales que trabajan y Programación competitiva en vivo para estudiantes.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

apple touch icon@2

css – Cómo alinear a en el medio (horizontalmente / ancho) de la página

250px dream

Mente subconsciente vs inconsciente: diferencia y comparación