Dans ce didacticiel, vous découvrirez l'arbre binaire et ses différents types. Vous trouverez également des exemples fonctionnels d'arborescence binaire en C, C ++, Java et Python.
Un arbre binaire est une structure de données arborescente dans laquelle chaque nœud parent peut avoir au plus deux enfants. Par exemple,
Arbre binaire
Types d'arbre binaire
Arbre binaire complet
Un arbre binaire complet est un type spécial d'arbre binaire dans lequel chaque nœud parent / nœud interne a deux ou pas d'enfants.
Arbre binaire complet
Pour en savoir plus, visitez l'arbre binaire complet.
Arbre binaire parfait
Un arbre binaire parfait est un type d'arbre binaire dans lequel chaque nœud interne a exactement deux nœuds enfants et tous les nœuds feuilles sont au même niveau.
Arbre binaire parfait
Pour en savoir plus, visitez l'arbre binaire parfait.
Arbre binaire complet
Un arbre binaire complet est comme un arbre binaire complet, mais avec deux différences majeures
- Chaque niveau doit être complètement rempli
- Tous les éléments de la feuille doivent pencher vers la gauche.
- 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
Pour en savoir plus, visitez l'arbre binaire complet.
Arbre dégénéré ou pathologique
Un arbre dégénéré ou pathologique est l'arbre ayant un seul enfant à gauche ou à droite.
Arbre binaire dégénéré
Arbre binaire biaisé
Un arbre binaire asymétrique est un arbre pathologique / dégénéré dans lequel l'arbre est dominé par les nœuds de gauche ou par les nœuds de droite. Ainsi, il existe deux types d'arbre binaire asymétrique: l'arbre binaire asymétrique à gauche et l' arbre binaire asymétrique à droite .
Arbre binaire biaisé
Arbre binaire équilibré
C'est un type d'arbre binaire dans lequel la différence entre le sous-arbre gauche et droit pour chaque nœud est soit 0 soit 1.
Arbre binaire équilibré
Pour en savoir plus, visitez l'arbre binaire équilibré.
Représentation d'arbre binaire
Un nœud d'un arbre binaire est représenté par une structure contenant une partie de données et deux pointeurs vers d'autres structures du même type.
struct node ( int data; struct node *left; struct node *right; ); 
Représentation d'arbre binaire
Exemples Python, Java et 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); )
Applications d'arbre binaire
- Pour un accès facile et rapide aux données
- Dans les algorithmes de routeur
- Pour implémenter la structure de données du tas
- Arbre de syntaxe
