TechCodeview

Árbol binario es una estructura de datos no lineal de tipo árbol que se utiliza principalmente para ordenar y buscar porque almacena datos en forma jerárquica. En esta sección aprenderemos los implementación de la estructura de datos de árbol binario en Java . Además, proporciona una breve descripción de la estructura de datos del árbol binario.

Árbol binario

Un árbol en el que cada nodo (padre) tiene como máximo dos nodos secundarios (izquierdo y derecho) se denomina árbol binario. El nodo superior se llama nodo raíz. En un árbol binario, un nodo contiene los datos y el puntero (dirección) de los nodos secundarios izquierdo y derecho.

El altura de un árbol binario es el número de aristas entre la raíz del árbol y su hoja más lejana (más profunda). Si el árbol es vacío , la altura es 0 . La altura del nodo se denota por h .

La altura del árbol binario anterior es 2.

Podemos calcular el número de hojas y nodos utilizando la siguiente fórmula.

• El número máximo de nodos hoja es un árbol binario: 2^h
• El número máximo de nodos es un árbol binario: 2^h+1-1

Donde h es la altura del árbol binario.

Ejemplo de árbol binario

Tipos de árbol binario

Existen los siguientes tipos de árbol binario en la estructura de datos:

1. Árbol completo/estrictamente binario
2. Árbol binario completo
3. Árbol binario perfecto
4. Equilibrio del árbol binario
5. Árbol binario enraizado
6. Árbol binario degenerado/patológico
7. Árbol binario extendido
8. Árbol binario sesgado
   1. Árbol binario sesgado a la izquierda
   2. Árbol binario sesgado a la derecha
9. Árbol binario roscado
   1. Árbol binario de un solo subproceso
   2. Árbol binario de doble subproceso

Implementación del árbol binario en Java

Hay muchas formas de implementar un árbol binario. En esta sección, implementaremos un árbol binario usando la estructura de datos LinkedList. Junto a ello, también implementaremos las órdenes transversales, buscando un nodo e insertando un nodo en un árbol binario.

Implementación de árbol binario usando LinkedList

Algoritmo

Defina la clase de nodo que contiene tres atributos, a saber: datos izquierdo y derecho. Aquí, la izquierda representa el hijo izquierdo del nodo y la derecha representa el hijo derecho del nodo.

• Cuando se crea un nodo, los datos pasarán al atributo de datos del nodo y tanto el lado izquierdo como el derecho se establecerán en nulo.
• Defina otra clase que tenga un atributo raíz.
• Root representa el nodo raíz del árbol y lo inicializa a nulo.

insertar()agregará un nuevo nodo al árbol:
• Comprueba si la raíz es nula, lo que significa que el árbol está vacío. Agregará el nuevo nodo como raíz.
• De lo contrario, agregará raíz a la cola.
• El nodo variable representa el nodo actual.
• Primero, verifica si un nodo tiene un hijo izquierdo y derecho. En caso afirmativo, agregará ambos nodos a la cola.
• Si el hijo izquierdo no está presente, agregará el nuevo nodo como hijo izquierdo.
• Si el izquierdo está presente, agregará el nuevo nodo como hijo derecho.
en orden()mostrará los nodos del árbol en orden.
• Atraviesa todo el árbol y luego imprime el hijo izquierdo seguido de la raíz y luego el hijo derecho.

BinarySearchTree.java

 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)); } } 

Producción:

 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 

Operaciones de árbol binario

Se pueden realizar las siguientes operaciones en un árbol binario:

ratón y tipos de ratón

• Inserción
• Supresión
• Buscar
• El recorrido

Programa Java para insertar un nodo en un árbol binario

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); } } } } 

Producción:

 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 

Programa Java para eliminar un nodo en Java

Algoritmo

1. Comenzando en la raíz, busque el nodo más profundo y más a la derecha en el árbol binario y el nodo que queremos eliminar.
2. Reemplace los datos del nodo más profundo a la derecha con el nodo que se va a eliminar.
3. Luego elimine el nodo más profundo de la derecha.

Considere la siguiente figura.

DeleteNode.java

 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); } } 

Producción:

recorrido de pedido por correo del árbol binario

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

Programa Java para buscar un nodo en un árbol binario

Algoritmo

• Defina la clase de nodo que tiene tres atributos, a saber: datos izquierdo y derecho. Aquí, la izquierda representa el hijo izquierdo del nodo y la derecha representa el hijo derecho del nodo.
• Cuando se crea un nodo, los datos pasarán al atributo de datos del nodo y tanto el lado izquierdo como el derecho se establecerán en nulo.
• Defina otra clase que tenga dos atributos raíz y bandera.
  1. Root representa el nodo raíz del árbol y lo inicializa a nulo.
  2. La bandera se utilizará para comprobar si el nodo dado está presente en el árbol o no. Inicialmente, se establecerá en falso.

nododebúsqueda()buscará un nodo particular en el árbol binario:
• Comprueba si la raíz es nula, lo que significa que el árbol está vacío.
• Si el árbol no está vacío, comparará los datos temporales con el valor. Si son iguales, establecerá la bandera en verdadero y regresará.
• Atraviese el subárbol izquierdo llamando a searchNode() de forma recursiva y compruebe si el valor está presente en el subárbol izquierdo.
• Atraviese el subárbol derecho llamando a searchNode() de forma recursiva y compruebe si el valor está presente en el subárbol derecho.

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.'); } } 

Producción:

 Element is present in the binary tree. 

Recorrido del árbol binario

Nota: Excepto los tres recorridos anteriores, existe otro orden de recorrido que se denomina recorrido de límites.

Programa Java para recorrer el recorrido en orden, preorden y postorden

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(); } } 

Producción:

 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 

Además de las operaciones anteriores, también podemos realizar operaciones como nodo grande, nodo más pequeño y suma de todos los nodos.

Programa Java para encontrar el nodo más grande en un árbol binario

LargestNode.java

 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)); } } 

Producción:

 Largest element in the binary tree: 99 

Programa Java para encontrar el nodo más pequeño en un árbol binario

Algoritmo

1. Defina la clase Nodo que tiene tres atributos, a saber: datos, izquierda y derecha. Aquí, la izquierda representa el hijo izquierdo del nodo y la derecha representa el hijo derecho del nodo.
2. Cuando se crea un nodo, los datos pasarán al atributo de datos del nodo y tanto la izquierda como la derecha se establecerán en nulo.
3. Defina otra clase que tenga un atributo raíz.
   RaízRepresenta el nodo raíz del árbol e inicialízalo a nulo.

elemento más pequeño()encontrará el nodo más pequeño en el árbol binario:
1. Comprueba si la raíz es nula , lo que significa que el árbol está vacío.
2. Si el árbol no está vacío, defina una variable min que almacenará los datos temporales.
3. Descubra el nodo mínimo en el subárbol izquierdo llamando al elemento más pequeño() de forma recursiva. Guarde ese valor en leftMin. Compare el valor de min con leftMin y almacene el mínimo de dos en min.
4. Descubra el nodo mínimo en el subárbol derecho llamando al elemento más pequeño () de forma recursiva. Guarde ese valor en rightMin. Compare el valor de min con rightMin y almacene el máximo de dos en min.
5. Al final, min contendrá el nodo más pequeño del árbol binario.

SmallestNode.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)); } } 

Producción:

 Smallest element in the binary tree: 1 

Programa Java para encontrar el ancho máximo de un árbol binario

Algoritmo

1. Defina la clase de nodo que tiene tres atributos, a saber: datos izquierdo y derecho. Aquí, la izquierda representa el hijo izquierdo del nodo y la derecha representa el hijo derecho del nodo.
2. Cuando se crea un nodo, los datos pasarán al atributo de datos del nodo y tanto el lado izquierdo como el derecho se establecerán en nulo.
3. Defina otra clase que tenga un atributo raíz.
   Raízrepresenta el nodo raíz del árbol y lo inicializa a nulo.

1. La variable maxWidth almacenará el número máximo de nodos presentes en cualquier nivel.
2. La cola se utiliza para atravesar el árbol binario a nivel.
3. Comprueba si la raíz es nula, lo que significa que el árbol está vacío.
4. De lo contrario, agregue el nodo raíz a la cola. La variable nodesInLevel realiza un seguimiento del número de nodos en cada nivel.
5. Si nodesInLevel > 0, elimine el nodo del frente de la cola y agregue sus hijos izquierdo y derecho a la cola. Para la primera iteración, se eliminará el nodo 1 y sus nodos secundarios 2 y 3 se agregarán a la cola. En la segunda iteración, se eliminará el nodo 2, sus hijos 4 y 5 se agregarán a la cola y así sucesivamente.
6. MaxWidth almacenará max(maxWidth, nodesInLevel). Entonces, en cualquier momento dado, representará el número máximo de nodos.
7. Esto continuará hasta que se atraviesen todos los niveles del árbol.

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()); } } 

Producción:

 Maximum width of the binary tree: 4