Albero binario completo

In questo tutorial imparerai a conoscere un albero binario completo e i suoi diversi tipi. Inoltre, troverai esempi funzionanti di un albero binario completo in C, C ++, Java e Python.

Un albero binario completo è un albero binario in cui tutti i livelli sono completamente riempiti tranne forse quello più basso, che viene riempito da sinistra.

Un albero binario completo è proprio come un albero binario completo, ma con due differenze principali

  1. Tutti gli elementi dell'anta devono essere inclinati verso sinistra.
  2. L'ultimo elemento foglia potrebbe non avere un fratello destro, cioè un albero binario completo non deve essere un albero binario completo.
Albero binario completo

Albero binario completo vs albero binario completo

Confronto tra albero binario completo e albero binario completo Confronto tra albero binario completo e albero binario completo Confronto tra albero binario completo e albero binario completo Confronto tra albero binario completo e albero binario completo

Come viene creato un albero binario completo?

  1. Seleziona il primo elemento dell'elenco come nodo radice. (numero di elementi al livello I: 1) Seleziona il primo elemento come radice
  2. Metti il ​​secondo elemento come figlio sinistro del nodo radice e il terzo elemento come figlio destro. (numero di elementi al livello II: 2) 12 come bambino sinistro e 9 come bambino destro
  3. Metti i due elementi successivi come figli del nodo sinistro del secondo livello. Di nuovo, metti i due elementi successivi come figli del nodo destro del secondo livello (numero di elementi al livello III: 4) elementi).
  4. Continua a ripetere fino a raggiungere l'ultimo elemento. 5 come bambino sinistro e 6 come bambino destro

Esempi di 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"; )

Relazione tra gli indici degli array e l'elemento dell'albero

Un albero binario completo ha una proprietà interessante che possiamo usare per trovare i figli e i genitori di qualsiasi nodo.

Se l'indice di qualsiasi elemento nell'array è i, l'elemento nell'indice 2i+1diventerà il figlio sinistro e l'elemento 2i+2nell'indice diventerà il figlio destro. Inoltre, il genitore di qualsiasi elemento all'indice i è dato dal limite inferiore di (i-1)/2.

Proviamolo

 Figlio sinistro di 1 (indice 0) = elemento in (2 * 0 + 1) indice = elemento in 1 indice = 12 Figlio destro di 1 = elemento in (2 * 0 + 2) indice = elemento in 2 indice = 9 Allo stesso modo, Figlio a sinistra di 12 (indice 1) = elemento in (2 * 1 + 1) indice = elemento in 3 indice = 5 Figlio a destra di 12 = elemento in (2 * 1 + 2) indice = elemento in 4 indice = 6

Confermiamo anche che le regole valgono per trovare il genitore di qualsiasi nodo

 Genitore di 9 (posizione 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indice = 1 Genitore di 12 (posizione 1) = (1-1) / 2 = 0 indice = 1

Comprendere questa mappatura degli indici degli array alle posizioni degli alberi è fondamentale per comprendere come funziona la struttura dei dati dell'heap e come viene utilizzata per implementare l'ordinamento dell'heap.

Applicazioni complete per alberi binari

  • Strutture dati basate su heap
  • Ordinamento mucchio

Articoli interessanti...