Árbol binario completo

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

Un árbol binario completo es un árbol binario en el que todos los niveles están completamente llenos excepto posiblemente el más bajo, que se llena desde la izquierda.

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

  1. Todos los elementos de la hoja deben inclinarse hacia la izquierda.
  2. 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

Árbol binario completo vs árbol binario completo

Comparación entre árbol binario completo y árbol binario completo Comparación entre árbol binario completo y árbol binario completo Comparación entre árbol binario completo y árbol binario completo Comparación entre árbol binario completo y árbol binario completo

¿Cómo se crea un árbol binario completo?

  1. Seleccione el primer elemento de la lista para que sea el nodo raíz. (no. de elementos en el nivel I: 1) Seleccione el primer elemento como raíz
  2. Coloque el segundo elemento como hijo izquierdo del nodo raíz y el tercer elemento como hijo derecho. (número de elementos en el nivel II: 2) 12 como hijo izquierdo y 9 como hijo derecho
  3. Coloque los dos elementos siguientes como hijos del nodo izquierdo del segundo nivel. Nuevamente, coloque los dos elementos siguientes como elementos secundarios del nodo derecho del segundo nivel (no. De elementos en el nivel III: 4) elementos).
  4. Sigue repitiendo hasta llegar al último elemento. 5 como hijo izquierdo y 6 como hijo derecho

Ejemplos de Python, Java y C / C ++

Python Java C C ++ 
 # Checking if a binary tree is a complete binary tree in C class Node: def __init__(self, item): self.item = item self.left = None self.right = None # Count the number of nodes def count_nodes(root): if root is None: return 0 return (1 + count_nodes(root.left) + count_nodes(root.right)) # Check if the tree is complete binary tree def is_complete(root, index, numberNodes): # Check if the tree is empty if root is None: return True if index>= numberNodes: return False return (is_complete(root.left, 2 * index + 1, numberNodes) and is_complete(root.right, 2 * index + 2, numberNodes)) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) node_count = count_nodes(root) index = 0 if is_complete(root, index, node_count): print("The tree is a complete binary tree") else: print("The tree is not a complete binary tree") 
 // Checking if a binary tree is a complete binary tree in Java // Node creation class Node ( int data; Node left, right; Node(int item) ( data = item; left = right = null; ) ) class BinaryTree ( Node root; // Count the number of nodes int countNumNodes(Node root) ( if (root == null) return (0); return (1 + countNumNodes(root.left) + countNumNodes(root.right)); ) // Check for complete binary tree boolean checkComplete(Node root, int index, int numberNodes) ( // Check if the tree is empty if (root == null) return true; if (index>= numberNodes) return false; return (checkComplete(root.left, 2 * index + 1, numberNodes) && checkComplete(root.right, 2 * index + 2, numberNodes)); ) 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.right = new Node(5); tree.root.left.left = new Node(4); tree.root.right.left = new Node(6); int node_count = tree.countNumNodes(tree.root); int index = 0; if (tree.checkComplete(tree.root, index, node_count)) System.out.println("The tree is a complete binary tree"); else System.out.println("The tree is not a complete binary tree"); ) )
 // Checking if a binary tree is a complete binary tree in C #include #include #include struct Node ( int key; struct Node *left, *right; ); // Node creation struct Node *newNode(char k) ( struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node; ) // Count the number of nodes int countNumNodes(struct Node *root) ( if (root == NULL) return (0); return (1 + countNumNodes(root->left) + countNumNodes(root->right)); ) // Check if the tree is a complete binary tree bool checkComplete(struct Node *root, int index, int numberNodes) ( // Check if the tree is complete if (root == NULL) return true; if (index>= numberNodes) return false; return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes)); ) int main() ( struct Node *root = NULL; root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); int node_count = countNumNodes(root); int index = 0; if (checkComplete(root, index, node_count)) printf("The tree is a complete binary tree"); else printf("The tree is not a complete binary tree"); )
 // Checking if a binary tree is a complete binary tree in C++ #include using namespace std; struct Node ( int key; struct Node *left, *right; ); // Create node struct Node *newNode(char k) ( struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node; ) // Count the number of nodes int countNumNodes(struct Node *root) ( if (root == NULL) return (0); return (1 + countNumNodes(root->left) + countNumNodes(root->right)); ) // Check if the tree is a complete binary tree bool checkComplete(struct Node *root, int index, int numberNodes) ( // Check if the tree is empty if (root == NULL) return true; if (index>= numberNodes) return false; return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes)); ) int main() ( struct Node *root = NULL; root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); int node_count = countNumNodes(root); int index = 0; if (checkComplete(root, index, node_count)) cout << "The tree is a complete binary tree"; else cout << "The tree is not a complete binary tree"; )

Relación entre índices de matriz y elemento de árbol

Un árbol binario completo tiene una propiedad interesante que podemos usar para encontrar los hijos y los padres de cualquier nodo.

Si el índice de cualquier elemento en la matriz es i, el elemento en el índice 2i+1se convertirá en el hijo izquierdo y el elemento en el 2i+2índice se convertirá en el hijo derecho. Además, el padre de cualquier elemento en el índice i viene dado por el límite inferior de (i-1)/2.

Vamos a probarlo

 Hijo izquierdo de 1 (índice 0) = elemento en (2 * 0 + 1) índice = elemento en 1 índice = 12 Hijo derecho de 1 = elemento en (2 * 0 + 2) índice = elemento en 2 índice = 9 De manera similar, Hijo izquierdo de 12 (índice 1) = elemento en (2 * 1 + 1) índice = elemento en 3 índice = 5 Hijo derecho de 12 = elemento en (2 * 1 + 2) índice = elemento en 4 índice = 6

Confirmemos también que las reglas son válidas para encontrar el padre de cualquier nodo

 Padre de 9 (posición 2) = (2-1) / 2 = ½ = 0.5 ~ 0 índice = 1 Padre de 12 (posición 1) = (1-1) / 2 = 0 índice = 1

Comprender esta asignación de índices de matriz a posiciones de árbol es fundamental para comprender cómo funciona la estructura de datos de montón y cómo se utiliza para implementar la clasificación de montón.

Aplicaciones completas de árbol binario

  • Estructuras de datos basadas en montón
  • Tipo de pila

Articulos interesantes...