Arbre binaire complet

Dans ce didacticiel, vous découvrirez un arbre binaire complet et ses différents types. Vous trouverez également des exemples fonctionnels d'un arbre binaire complet en C, C ++, Java et Python.

Un arbre binaire complet est un arbre binaire dans lequel tous les niveaux sont complètement remplis sauf peut-être le plus bas, qui est rempli à partir de la gauche.

Un arbre binaire complet est comme un arbre binaire complet, mais avec deux différences majeures

  1. Tous les éléments de la feuille doivent pencher vers la gauche.
  2. Le dernier élément feuille peut ne pas avoir de frère droit, c'est-à-dire qu'un arbre binaire complet n'a pas besoin d'être un arbre binaire complet.
Arbre binaire complet

Arbre binaire complet vs arbre binaire complet

Comparaison entre l'arbre binaire complet et l'arbre binaire complet Comparaison entre l'arbre binaire complet et l'arbre binaire complet Comparaison entre l'arbre binaire complet et l'arbre binaire complet Comparaison entre l'arbre binaire complet et l'arbre binaire complet

Comment un arbre binaire complet est-il créé?

  1. Sélectionnez le premier élément de la liste comme nœud racine. (nombre d'éléments au niveau I: 1) Sélectionnez le premier élément comme racine
  2. Mettez le deuxième élément en tant qu'enfant gauche du nœud racine et le troisième élément en tant qu'enfant droit. (nombre d'éléments au niveau II: 2) 12 en tant qu'enfant de gauche et 9 en tant qu'enfant de droite
  3. Mettez les deux éléments suivants comme enfants du nœud gauche du deuxième niveau. Encore une fois, mettez les deux éléments suivants comme enfants du nœud droit du deuxième niveau (nombre d'éléments sur le niveau III: 4) éléments).
  4. Continuez à répéter jusqu'à ce que vous atteigniez le dernier élément. 5 en tant qu'enfant de gauche et 6 en tant qu'enfant de droite

Exemples Python, Java et 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"; )

Relation entre les index de tableau et l'élément d'arbre

Un arbre binaire complet a une propriété intéressante que nous pouvons utiliser pour trouver les enfants et les parents de n'importe quel nœud.

Si l'index d'un élément du tableau est i, l'élément de l'index 2i+1deviendra l'enfant de gauche et l'élément de l' 2i+2index deviendra l'enfant de droite. De plus, le parent de tout élément à l'index i est donné par la borne inférieure de (i-1)/2.

Testons-le,

 Enfant gauche de 1 (index 0) = élément dans (2 * 0 + 1) index = élément dans 1 index = 12 Enfant droit de 1 = élément dans (2 * 0 + 2) index = élément dans 2 index = 9 De même, Enfant gauche de 12 (index 1) = élément dans (2 * 1 + 1) index = élément dans 3 index = 5 Enfant droit de 12 = élément dans (2 * 1 + 2) index = élément dans 4 index = 6

Confirmons également que les règles sont valables pour trouver le parent de n'importe quel nœud

 Parent de 9 (position 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Parent de 12 (position 1) = (1-1) / 2 = 0 index = 1

Comprendre ce mappage des index de tableau aux positions de l'arborescence est essentiel pour comprendre le fonctionnement de la structure de données du tas et comment elle est utilisée pour implémenter le tri du tas.

Applications complètes d'arbre binaire

  • Structures de données basées sur le tas
  • Tri de tas

Articles intéressants...