Árbol binario

En este tutorial, aprenderá sobre el árbol binario y sus diferentes tipos. Además, encontrará ejemplos de trabajo de árbol binario en C, C ++, Java y Python.

Un árbol binario es una estructura de datos de árbol en la que cada nodo padre puede tener como máximo dos hijos. Por ejemplo,

Árbol binario

Tipos de árbol binario

Árbol binario completo

Un árbol binario completo es un tipo especial de árbol binario en el que cada nodo padre / nodo interno tiene dos hijos o ninguno.

Árbol binario completo

Para obtener más información, visite el árbol binario completo.

Árbol binario perfecto

Un árbol binario perfecto es un tipo de árbol binario en el que cada nodo interno tiene exactamente dos nodos secundarios y todos los nodos hoja están en el mismo nivel.

Árbol binario perfecto

Para obtener más información, visite el árbol binario perfecto.

Árbol binario completo

Un árbol binario completo es como un árbol binario completo, pero con dos diferencias principales

  1. Cada nivel debe estar completamente lleno
  2. Todos los elementos de la hoja deben inclinarse hacia la izquierda.
  3. Es posible que el último elemento de la hoja no tenga un hermano correcto, es decir, un árbol binario completo no tiene que ser un árbol binario completo.
Árbol binario completo

Para obtener más información, visite el árbol binario completo.

Árbol degenerado o patológico

Un árbol degenerado o patológico es el árbol que tiene un solo hijo a la izquierda o a la derecha.

Árbol binario degenerado

Árbol binario sesgado

Un árbol binario sesgado es un árbol patológico / degenerado en el que el árbol está dominado por los nodos izquierdos o los nodos derechos. Por lo tanto, hay dos tipos de árbol binario sesgada: árbol binario de izquierda sesgada y árbol binario derecho asimétricos .

Árbol binario sesgado

Árbol binario equilibrado

Es un tipo de árbol binario en el que la diferencia entre el subárbol izquierdo y derecho para cada nodo es 0 o 1.

Árbol binario equilibrado

Para obtener más información, visite árbol binario equilibrado.

Representación de árbol binario

Un nodo de un árbol binario está representado por una estructura que contiene una parte de datos y dos punteros a otras estructuras del mismo tipo.

 struct node ( int data; struct node *left; struct node *right; );
Representación de árbol binario

Ejemplos de Python, Java y C / C ++

Python Java C C + 
 # Binary Tree in Python class Node: def __init__(self, key): self.left = None self.right = None self.val = key # Traverse preorder def traversePreOrder(self): print(self.val, end=' ') if self.left: self.left.traversePreOrder() if self.right: self.right.traversePreOrder() # Traverse inorder def traverseInOrder(self): if self.left: self.left.traverseInOrder() print(self.val, end=' ') if self.right: self.right.traverseInOrder() # Traverse postorder def traversePostOrder(self): if self.left: self.left.traversePostOrder() if self.right: self.right.traversePostOrder() print(self.val, end=' ') root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) print("Pre order Traversal: ", end="") root.traversePreOrder() print("In order Traversal: ", end="") root.traverseInOrder() print("Post order Traversal: ", end="") root.traversePostOrder()
 // Binary Tree in Java // Node creation 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; ) // Traverse Inorder public void traverseInOrder(Node node) ( if (node != null) ( traverseInOrder(node.left); System.out.print(" " + node.key); traverseInOrder(node.right); ) ) // Traverse Postorder public void traversePostOrder(Node node) ( if (node != null) ( traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.key); ) ) // Traverse Preorder public void traversePreOrder(Node node) ( if (node != null) ( System.out.print(" " + node.key); traversePreOrder(node.left); traversePreOrder(node.right); ) ) 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); System.out.print("Pre order Traversal: "); tree.traversePreOrder(tree.root); System.out.print("In order Traversal: "); tree.traverseInOrder(tree.root); System.out.print("Post order Traversal: "); tree.traversePostOrder(tree.root); ) )
 // Tree traversal in C #include #include struct node ( int item; struct node* left; struct node* right; ); // Inorder traversal void inorderTraversal(struct node* root) ( if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); ) // Preorder traversal void preorderTraversal(struct node* root) ( if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); ) // Postorder traversal void postorderTraversal(struct node* root) ( if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); ) // Create a new Node struct node* createNode(value) ( struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; ) // Insert on the left of the node struct node* insertLeft(struct node* root, int value) ( root->left = createNode(value); return root->left; ) // Insert on the right of the node struct node* insertRight(struct node* root, int value) ( root->right = createNode(value); return root->right; ) int main() ( struct node* root = createNode(1); insertLeft(root, 2); insertRight(root, 3); insertLeft(root->left, 4); printf("Inorder traversal "); inorderTraversal(root); printf("Preorder traversal "); preorderTraversal(root); printf("Postorder traversal "); postorderTraversal(root); )
 // Binary Tree in C++ #include #include using namespace std; struct node ( int data; struct node *left; struct node *right; ); // New node creation 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); ) // Traverse Preorder void traversePreOrder(struct node *temp) ( if (temp != NULL) ( cout << " "  left); traversePreOrder(temp->right); ) ) // Traverse Inorder void traverseInOrder(struct node *temp) ( if (temp != NULL) ( traverseInOrder(temp->left); cout << " "  right); ) ) // Traverse Postorder void traversePostOrder(struct node *temp) ( if (temp != NULL) ( traversePostOrder(temp->left); traversePostOrder(temp->right); cout << " "  left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); cout << "preorder traversal: "; traversePreOrder(root); cout << "Inorder traversal: "; traverseInOrder(root); cout << "Postorder traversal: "; traversePostOrder(root); )

Aplicaciones de árbol binario

  • Para un acceso fácil y rápido a los datos
  • En algoritmos de enrutador
  • Para implementar la estructura de datos del montón
  • Árbol de sintaxis

Articulos interesantes...