Árvore Binária Completa

Neste tutorial, você aprenderá sobre uma árvore binária completa e seus diferentes tipos. Além disso, você encontrará exemplos funcionais de uma árvore binária completa em C, C ++, Java e Python.

Uma árvore binária completa é uma árvore binária na qual todos os níveis são completamente preenchidos, exceto possivelmente o mais baixo, que é preenchido a partir da esquerda.

Uma árvore binária completa é como uma árvore binária completa, mas com duas diferenças principais

  1. Todos os elementos da folha devem se inclinar para a esquerda.
  2. O último elemento folha pode não ter um irmão certo, ou seja, uma árvore binária completa não precisa ser uma árvore binária completa.
Árvore Binária Completa

Árvore binária completa vs árvore binária completa

Comparação entre árvore binária completa e árvore binária completa Comparação entre árvore binária completa e árvore binária completa Comparação entre árvore binária completa e árvore binária completa Comparação entre árvore binária completa e árvore binária completa

Como uma árvore binária completa é criada?

  1. Selecione o primeiro elemento da lista para ser o nó raiz. (nº de elementos no nível I: 1) Selecione o primeiro elemento como raiz
  2. Coloque o segundo elemento como filho esquerdo do nó raiz e o terceiro elemento como filho direito. (nº de elementos no nível II: 2) 12 como criança esquerda e 9 como criança direita
  3. Coloque os próximos dois elementos como filhos do nó esquerdo do segundo nível. Novamente, coloque os próximos dois elementos como filhos do nó direito do segundo nível (número de elementos no nível III: 4) elementos).
  4. Continue repetindo até chegar ao último elemento. 5 como criança esquerda e 6 como criança direita

Exemplos de Python, Java e 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"; )

Relação entre índices de array e elemento de árvore

Uma árvore binária completa tem uma propriedade interessante que podemos usar para encontrar os filhos e pais de qualquer nó.

Se o índice de qualquer elemento na matriz for i, o elemento no índice 2i+1se tornará o filho esquerdo e o elemento no 2i+2índice se tornará o filho direito. Além disso, o pai de qualquer elemento no índice i é dado pelo limite inferior de (i-1)/2.

Vamos testar,

 Filho esquerdo de 1 (índice 0) = elemento em (2 * 0 + 1) índice = elemento em 1 índice = 12 Filho direito de 1 = elemento em (2 * 0 + 2) índice = elemento em 2 índice = 9 Da mesma forma, Filho esquerdo de 12 (índice 1) = elemento em (2 * 1 + 1) índice = elemento em 3 índice = 5 Filho direito de 12 = elemento em (2 * 1 + 2) índice = elemento em 4 índice = 6

Vamos também confirmar que as regras são válidas para encontrar o pai de qualquer nó

 Pai de 9 (posição 2) = (2-1) / 2 = ½ = 0,5 ~ 0 índice = 1 Pai de 12 (posição 1) = (1-1) / 2 = 0 índice = 1

Entender esse mapeamento de índices de array para posições de árvore é crítico para entender como a Estrutura de Dados Heap funciona e como ela é usada para implementar Heap Sort.

Aplicativos de árvore binária completos

  • Estruturas de dados baseadas em heap
  • Classificação de pilha

Artigos interessantes...