TechCodeview

Arbre binaire est une structure de données non linéaire de type arborescent qui est principalement utilisée pour le tri et la recherche car elle stocke les données sous forme hiérarchique. Dans cette section, nous apprendrons le implémentation d'une structure de données arborescente binaire en Java . Fournit également une brève description de la structure des données de l’arborescence binaire.

bash si condition

Arbre binaire

Un arbre dans lequel chaque nœud (parent) a au plus deux nœuds enfants (gauche et droit) est appelé arbre binaire. Le nœud le plus haut est appelé nœud racine. Dans un arbre binaire, un nœud contient les données et le pointeur (adresse) du nœud enfant gauche et droit.

Le hauteur d'un arbre binaire est le nombre d'arêtes entre la racine de l'arbre et sa feuille la plus éloignée (la plus profonde). Si l'arbre est vide , la hauteur est 0 . La hauteur du nœud est notée h .

La hauteur de l’arbre binaire ci-dessus est de 2.

Nous pouvons calculer le nombre de feuilles et de nœuds en utilisant la formule suivante.

• Le nombre maximum de nœuds feuilles est un arbre binaire : 2^h
• Le nombre maximum de nœuds est un arbre binaire : 2^h+1-1

Où h est la hauteur de l’arbre binaire.

Exemple d'arbre binaire

Types d'arbre binaire

Il existe les types d'arbre binaire suivants dans la structure de données :

1. Arbre complet/strictement binaire
2. Arbre binaire complet
3. Arbre binaire parfait
4. Arbre binaire d’équilibre
5. Arbre binaire enraciné
6. Arbre binaire dégénéré/pathologique
7. Arbre binaire étendu
8. Arbre binaire asymétrique
   1. Arbre binaire incliné à gauche
   2. Arbre binaire asymétrique à droite
9. Arbre binaire fileté
   1. Arbre binaire à thread unique
   2. Arbre binaire à double filetage

Implémentation d'un arbre binaire en Java

Il existe de nombreuses façons d’implémenter un arbre binaire. Dans cette section, nous implémenterons un arbre binaire en utilisant la structure de données LinkedList. Parallèlement, nous implémenterons également les ordres de parcours, recherchant un nœud et insérant un nœud dans un arbre binaire.

Implémentation d'un arbre binaire à l'aide de LinkedList

Algorithme

Définissez la classe Node qui contient trois attributs à savoir : les données gauche et droite. Ici, left représente l'enfant gauche du nœud et right représente l'enfant droit du nœud.

• Lorsqu'un nœud est créé, les données seront transmises à l'attribut data du nœud et la gauche et la droite seront définies sur null.
• Définissez une autre classe possédant un attribut racine.
• Root représente le nœud racine de l'arborescence et l'initialise à null.

insérer()ajoutera un nouveau nœud à l'arborescence :
• Il vérifie si la racine est nulle, ce qui signifie que l'arborescence est vide. Il ajoutera le nouveau nœud en tant que root.
• Sinon, cela ajoutera root à la file d'attente.
• Le nœud variable représente le nœud actuel.
• Tout d’abord, il vérifie si un nœud a un enfant gauche et droit. Si oui, les deux nœuds seront ajoutés à la file d'attente.
• Si l'enfant de gauche n'est pas présent, il ajoutera le nouveau nœud en tant qu'enfant de gauche.
• Si la gauche est présente, alors il ajoutera le nouveau nœud en tant qu'enfant de droite.
en ordre()affichera les nœuds de l’arborescence dans l’ordre.
• Il parcourt toute l'arborescence puis imprime l'enfant de gauche suivi de la racine puis suivi de l'enfant de droite.

BinarySearchTree.java

tri en tas et en tas

 public class BinarySearchTree { //Represent the node of binary tree public static class Node{ int data; Node left; Node right; public Node(int data){ //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public BinarySearchTree(){ root = null; } //factorial() will calculate the factorial of given number public int factorial(int num) { int fact = 1; if(num == 0) return 1; else { while(num > 1) { fact = fact * num; num--; } return fact; } } //numOfBST() will calculate the total number of possible BST by calculating Catalan Number for given key public int numOfBST(int key) { int catalanNumber = factorial(2 * key)/(factorial(key + 1) * factorial(key)); return catalanNumber; } public static void main(String[] args) { BinarySearchTree bt = new BinarySearchTree(); //Display total number of possible binary search tree with key 5 System.out.println('Total number of possible Binary Search Trees with given key: ' + bt.numOfBST(5)); } } 

Sortir:

 Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7 

Opérations sur l'arbre binaire

Les opérations suivantes peuvent être effectuées sur un arbre binaire :

• Insertion
• Effacement
• Recherche
• Traversée

Programme Java pour insérer un nœud dans l'arborescence binaire

BinaryTreeInsert.java

 public class BinaryTreeInsert { public static void main(String[] args) { new BinaryTreeInsert().run(); } static class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } } public void run() { Node rootnode = new Node(25); System.out.println('Building tree with root value ' + rootnode.value); System.out.println('================================='); insert(rootnode, 11); insert(rootnode, 15); insert(rootnode, 16); insert(rootnode, 23); insert(rootnode, 79); } public void insert(Node node, int value) { if (value node.value) { if (node.right != null) { insert(node.right, value); } else { System.out.println(' Inserted ' + value + ' to right of Node ' + node.value); node.right = new Node(value); } } } } 

Sortir:

 Building tree with root value 25 ================================= Inserted 11 to left of Node 25 Inserted 15 to right of Node 11 Inserted 16 to right of Node 15 Inserted 23 to right of Node 16 Inserted 79 to right of Node 25 

Programme Java pour supprimer un nœud en Java

Algorithme

1. En commençant par la racine, recherchez le nœud le plus profond et le plus à droite de l'arborescence binaire et le nœud que nous souhaitons supprimer.
2. Remplacez les données du nœud le plus à droite par le nœud à supprimer.
3. Supprimez ensuite le nœud le plus profond à droite.

Considérez la figure suivante.

SupprimerNode.java

dérivé partiel du latex

 import java.util.LinkedList; import java.util.Queue; public class DeleteNode { // A binary tree node has key, pointer to // left child and a pointer to right child static class Node { int key; Node left, right; // Constructor Node(int key) { this.key = key; left = null; right = null; } } static Node root; static Node temp = root; // Inorder traversal of a binary tree static void inorder(Node temp) { if (temp == null) return; inorder(temp.left); System.out.print(temp.key + ' '); inorder(temp.right); } // Function to delete deepest // element in binary tree static void deleteDeepest(Node root, Node delNode) { Queue q = new LinkedList(); q.add(root); Node temp = null; // Do level order traversal until last node while (!q.isEmpty()) { temp = q.peek(); q.remove(); if (temp == delNode) { temp = null; return; } if (temp.right!=null) { if (temp.right == delNode) { temp.right = null; return; } else q.add(temp.right); } if (temp.left != null) { if (temp.left == delNode) { temp.left = null; return; } else q.add(temp.left); } } } // Function to delete given element // in binary tree static void delete(Node root, int key) { if (root == null) return; if (root.left == null && root.right == null) { if (root.key == key) { root=null; return; } else return; } Queue q = new LinkedList(); q.add(root); Node temp = null, keyNode = null; // Do level order traversal until // we find key and last node. while (!q.isEmpty()) { temp = q.peek(); q.remove(); if (temp.key == key) keyNode = temp; if (temp.left != null) q.add(temp.left); if (temp.right != null) q.add(temp.right); } if (keyNode != null) { int x = temp.key; deleteDeepest(root, temp); keyNode.key = x; } } // Driver code public static void main(String args[]) { root = new Node(10); root.left = new Node(11); root.left.left = new Node(7); root.left.right = new Node(12); root.right = new Node(9); root.right.left = new Node(15); root.right.right = new Node(8); System.out.print('Inorder traversal before deletion: '); inorder(root); //node to delete int key = 7; delete(root, key); System.out.print('
Inorder traversal after deletion: '); inorder(root); } } 

Sortir:

 Inorder traversal before deletion: 7 11 12 10 15 9 8 Inorder traversal after deletion: 8 11 12 10 15 9 

Programme Java pour rechercher un nœud dans l'arborescence binaire

Algorithme

• Définissez la classe Node qui a trois attributs à savoir : les données gauche et droite. Ici, left représente l'enfant gauche du nœud et right représente l'enfant droit du nœud.
• Lorsqu'un nœud est créé, les données seront transmises à l'attribut data du nœud et la gauche et la droite seront définies sur null.
• Définissez une autre classe qui a deux attributs root et flag.
  1. Root représente le nœud racine de l'arborescence et l'initialise à null.
  2. Le Flag sera utilisé pour vérifier si le nœud donné est présent ou non dans l'arborescence. Initialement, il sera défini sur false.

nœud de recherche()recherchera un nœud particulier dans l'arbre binaire :
• Il vérifie si la racine est nulle, ce qui signifie que l'arborescence est vide.
• Si l'arborescence n'est pas vide, elle comparera les données de temp avec la valeur. S'ils sont égaux, il définira l'indicateur sur true et reviendra.
• Parcourez le sous-arbre gauche en appelant searchNode() de manière récursive et vérifiez si la valeur est présente dans le sous-arbre gauche.
• Parcourez le sous-arbre droit en appelant searchNode() de manière récursive et vérifiez si la valeur est présente dans le sous-arbre droit.

SearchBinaryTree.java

 public class SearchBinaryTree { //Represent a node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public static boolean flag = false; public SearchBinaryTree() { root = null; } //searchNode() will search for the particular node in the binary tree public void searchNode(Node temp, int value) { //Check whether tree is empty if(root == null) { System.out.println('Tree is empty'); } else { //If value is found in the given binary tree then, set the flag to true if(temp.data == value) { flag = true; return; } //Search in left subtree if(flag == false && temp.left != null) { searchNode(temp.left, value); } //Search in right subtree if(flag == false && temp.right != null) { searchNode(temp.right, value); } } } public static void main(String[] args) { SearchBinaryTree bt = new SearchBinaryTree(); //Add nodes to the binary tree bt.root = new Node(11); bt.root.left = new Node(8); bt.root.right = new Node(12); bt.root.left.left = new Node(78); bt.root.right.left = new Node(23); bt.root.right.right = new Node(36); //Search for node 5 in the binary tree bt.searchNode(bt.root, 23); if(flag) System.out.println('Element is present in the binary tree.'); else System.out.println('Element is not present in the binary tree.'); } } 

Sortir:

 Element is present in the binary tree. 

Traversée de l'arbre binaire

Remarque : à l'exception des trois parcours ci-dessus, il existe un autre ordre de parcours appelé parcours de frontière.

Programme Java pour parcourir l'ordre, la précommande et la post-commande

BinaryTree.java

 public class BinaryTree { // first node private Node root; BinaryTree() { root = null; } // Class representing tree nodes static class Node { int value; Node left; Node right; Node(int value) { this.value = value; left = null; right = null; } public void displayData() { System.out.print(value + ' '); } } public void insert(int i) { root = insert(root, i); } //Inserting node - recursive method public Node insert(Node node, int value) { if(node == null){ return new Node(value); } // Move to the left if passed value is // less than the current node if(value node.value) { node.right = insert(node.right, value); } return node; } // Search node in binary search tree public Node find(int searchedValue) { Node current = root; while(current.value != searchedValue) { if(searchedValue = current = current.right; if(current == null) { return null; } } return current; } // For traversing in order public void inOrder(Node node) { if(node != null) { inOrder(node.left); node.displayData(); inOrder(node.right); } } // Preorder traversal public void preOrder(Node node) { if(node != null){ node.displayData(); preOrder(node.left); preOrder(node.right); } } // Postorder traversal public void postOrder(Node node) { if(node != null) { postOrder(node.left); postOrder(node.right); node.displayData(); } } public static void main(String[] args) { BinaryTree bst = new BinaryTree(); bst.insert(34); bst.insert(56); bst.insert(12); bst.insert(89); bst.insert(67); bst.insert(90); System.out.println('Inorder traversal of binary tree'); bst.inOrder(bst.root); System.out.println(); System.out.println('Preorder traversal of binary tree'); bst.preOrder(bst.root); System.out.println(); System.out.println('Postorder traversal of binary tree'); bst.postOrder(bst.root); System.out.println(); } } 

Sortir:

 Inorder traversal of binary tree 12 34 56 67 89 90 Preorder traversal of binary tree 34 12 56 89 67 90 Postorder traversal of binary tree 12 67 90 89 56 34 

Outre les opérations ci-dessus, nous pouvons également effectuer des opérations telles que le grand nœud, le plus petit nœud et la somme de tous les nœuds.

Programme Java pour trouver le plus grand nœud dans l'arborescence binaire

LargestNode.java

ville aux États-Unis

 public class LargestNode { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public LargestNode() { root = null; } //largestElement() will find out the largest node in the binary tree public int largestElement(Node temp) { //Check whether tree is empty if(root == null) { System.out.println('Tree is empty'); return 0; } else { int leftMax, rightMax; //Max will store temp's data int max = temp.data; //It will find largest element in left subtree if(temp.left != null){ leftMax = largestElement(temp.left); //Compare max with leftMax and store greater value into max max = Math.max(max, leftMax); } //It will find largest element in right subtree if(temp.right != null){ rightMax = largestElement(temp.right); //Compare max with rightMax and store greater value into max max = Math.max(max, rightMax); } return max; } } public static void main(String[] args) { LargestNode bt = new LargestNode(); //Add nodes to the binary tree bt.root = new Node(90); bt.root.left = new Node(99); bt.root.right = new Node(23); bt.root.left.left = new Node(96); bt.root.right.left = new Node(45); bt.root.right.right = new Node(6); bt.root.right.left = new Node(13); bt.root.right.right = new Node(77); //Display largest node in the binary tree System.out.println('Largest element in the binary tree: ' + bt.largestElement(bt.root)); } } 

Sortir:

 Largest element in the binary tree: 99 

Programme Java pour trouver le plus petit nœud dans l'arborescence binaire

Algorithme

1. Définissez la classe Node qui a trois attributs à savoir : data, left et right. Ici, left représente l'enfant gauche du nœud et right représente l'enfant droit du nœud.
2. Lorsqu'un nœud est créé, les données seront transmises à l'attribut data du nœud et la gauche et la droite seront définies sur null.
3. Définissez une autre classe qui a un attribut racine.
   Racinereprésente le nœud racine de l’arborescence et initialise-le à null.

le plus petit élément()découvrira le plus petit nœud de l'arbre binaire :
1. Il vérifie si la racine est nulle , ce qui signifie que l'arbre est vide.
2. Si l'arbre n'est pas vide, définissez une variable min qui stockera les données de temp.
3. Découvrez le nœud minimum dans le sous-arbre gauche en appelant smallestElement() de manière récursive. Stockez cette valeur dans leftMin. Comparez la valeur de min avec leftMin et stockez le minimum de deux à min.
4. Découvrez le nœud minimum dans le sous-arbre droit en appelant smallestElement() de manière récursive. Stockez cette valeur dans rightMin. Comparez la valeur de min avec rightMin et stockez le maximum de deux à min.
5. À la fin, min contiendra le plus petit nœud de l'arborescence binaire.

Le plus petit nœud.java

 public class SmallestNode { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public SmallestNode() { root = null; } //smallestElement() will find out the smallest node in the binary tree public int smallestElement(Node temp) { //Check whether tree is empty if(root == null) { System.out.println('Tree is empty'); return 0; } else { int leftMin, rightMin; //Min will store temp's data int min = temp.data; //It will find smallest element in left subtree if(temp.left != null) { leftMin = smallestElement(temp.left); //If min is greater than leftMin then store the value of leftMin into min min = Math.min(min, leftMin); } //It will find smallest element in right subtree if(temp.right != null) { rightMin = smallestElement(temp.right); //If min is greater than rightMin then store the value of rightMin into min min = Math.min(min, rightMin); } return min; } } public static void main(String[] args) { SmallestNode bt = new SmallestNode(); //Add nodes to the binary tree bt.root = new Node(9); bt.root.left = new Node(5); bt.root.right = new Node(7); bt.root.left.left = new Node(1); bt.root.right.left = new Node(2); bt.root.right.right = new Node(8); bt.root.right.left = new Node(4); bt.root.right.right = new Node(3); //Display smallest node in the binary tree System.out.println('Smallest element in the binary tree: ' + bt.smallestElement(bt.root)); } } 

Sortir:

 Smallest element in the binary tree: 1 

Programme Java pour trouver la largeur maximale d'un arbre binaire

Algorithme

1. Définissez la classe Node qui a trois attributs à savoir : les données gauche et droite. Ici, left représente l'enfant gauche du nœud et right représente l'enfant droit du nœud.
2. Lorsqu'un nœud est créé, les données seront transmises à l'attribut data du nœud et la gauche et la droite seront définies sur null.
3. Définissez une autre classe qui a un attribut racine.
   Racinereprésente le nœud racine de l'arborescence et l'initialise à null.

1. La variable maxWidth stockera le nombre maximum de nœuds présents dans n'importe quel niveau.
2. La file d'attente est utilisée pour parcourir l'arbre binaire au niveau.
3. Il vérifie si la racine est nulle, ce qui signifie que l'arborescence est vide.
4. Sinon, ajoutez le nœud racine à la file d'attente. La variable nodesInLevel garde une trace du nombre de nœuds dans chaque niveau.
5. Si nodesInLevel > 0, supprimez le nœud du début de la file d’attente et ajoutez ses enfants gauche et droit à la file d’attente. Pour la première itération, le nœud 1 sera supprimé et ses nœuds enfants 2 et 3 seront ajoutés à la file d'attente. Lors de la deuxième itération, le nœud 2 sera supprimé, ses enfants 4 et 5 seront ajoutés à la file d'attente et ainsi de suite.
6. MaxWidth stockera max(maxWidth, nodesInLevel). Ainsi, à tout moment donné, cela représentera le nombre maximum de nœuds.
7. Cela continuera jusqu'à ce que tous les niveaux de l'arborescence soient parcourus.

BinaryTree.java

 import java.util.LinkedList; import java.util.Queue; public class BinaryTree { //Represent the node of binary tree public static class Node { int data; Node left; Node right; public Node(int data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public BinaryTree() { root = null; } //findMaximumWidth() will find out the maximum width of the given binary tree public int findMaximumWidth() { int maxWidth = 0; //Variable nodesInLevel keep tracks of number of nodes in each level int nodesInLevel = 0; //queue will be used to keep track of nodes of tree level-wise Queue queue = new LinkedList(); //Check if root is null, then width will be 0 if(root == null) { System.out.println('Tree is empty'); return 0; } else { //Add root node to queue as it represents the first level queue.add(root); while(queue.size() != 0) { //Variable nodesInLevel will hold the size of queue i.e. number of elements in queue nodesInLevel = queue.size(); //maxWidth will hold maximum width. //If nodesInLevel is greater than maxWidth then, maxWidth will hold the value of nodesInLevel maxWidth = Math.max(maxWidth, nodesInLevel); //If variable nodesInLevel contains more than one node //then, for each node, we'll add left and right child of the node to the queue while(nodesInLevel > 0) { Node current = queue.remove(); if(current.left != null) queue.add(current.left); if(current.right != null) queue.add(current.right); nodesInLevel--; } } } return maxWidth; } public static void main(String[] args) { BinaryTree bt = new BinaryTree(); //Add nodes to the binary tree bt.root = new Node(1); bt.root.left = new Node(2); bt.root.right = new Node(3); bt.root.left.left = new Node(4); bt.root.left.right = new Node(5); bt.root.right.left = new Node(6); bt.root.right.right = new Node(7); bt.root.left.left.left = new Node(8); //Display the maximum width of given tree System.out.println('Maximum width of the binary tree: ' + bt.findMaximumWidth()); } } 

Sortir:

 Maximum width of the binary tree: 4