Clasificación de árboles binarios (por estructura de almacenamiento)
Clasificación de árboles (por estructura de almacenamiento)
Almacenamiento secuencial (representado por matrices (árbol binario estático))
Almacenamiento en cadena
Algunas raíces binarias especiales:
Árbol binario completo, árbol binario balanceado (AVL), árbol binario de pistas, Tri-Fork (puntero con padre)
Árbol de búsqueda binario o árbol de búsqueda binario (BST)
El árbol binario utilizado se muestra en la siguiente figura:
Implementación de Java de árbol binario (estructura de almacenamiento de cadena)
clase treeNode {private int key = 0; Data de cadena privada = nulo; booleano privado isvisted = false; Treenode privado Leftchild = nulo; TreeNode privado Rightchild = NULL; public treeNode () {} public treeNode (int key, string data) {this.key = key; this.data = data; this.leftChild = nulo; this.rightchild = null; } public int getKey () {return Key; } public void setKey (int key) {this.key = key; } public string getData () {return data; } public void setData (string data) {this.data = data; } public treeNode getLeftChild () {return Leftchild; } public void setleftchild (treeNode Leftchild) {this.leftChild = LeftChild; } public treeNode getRightChild () {return rightchild; } public void setRightChild (treeNode rightchild) {this.rightChild = rightChild; } public boolean isvisted () {return isVisted; } public void setVisted (boolean isvisted) {this.isVisted = isVisted; }} public class BinaryTree {private treeNode root = null; public binaryTree () {root = new TreeNode (1, "rootNode (a)"); } public void createBintree (treeNode root) {// Creación manual (la estructura se muestra en la figura) treeNode newNodeB = new TreeNode (2, "b"); TreeNode newnodec = new TreeNode (3, "C"); TreeNode newnoded = new TreeNode (4, "D"); TreeNode newnodee = new TreeNode (5, "E"); TreeNode newNodeF = new TreeNode (6, "f"); root.setleftchild (newNodeB); root.setRightChild (newnodec); root.getleftchild (). setleftchild (Newnoded); root.getleftchild (). setRightChild (Newnodee); root.getRightChild (). setRightChild (newNodeF); } public boolean isEtimty () {// Determinar si el árbol binario está vacío o no return root == null; } public int Height () {// Encuentra la altura de la altura del árbol de retorno altura (raíz); } public int Hight (TreeNode Subtree) {if (subtree == null) return 0; // End recursivo: la altura del árbol vacío es 0 más {int i = altura (subtree.getleftchild ()); int j = altura (subtree.getRightChild ()); regresar (i <j)? j + 1: i + 1; }} public int size () {// Encuentra el número de nodos de retorno de tamaño (raíz); } public int size (TreeNode Subtree) {if (subtree == null) return 0; else {return 1 + size (subtree.getleftchild ()) + size (subtree.getRightChild ()); }} public treeNode Parent (elemento treeNode) {// return de retorno del nodo principal (root == null || root == elemento)? nulo: parent (raíz, elemento); } public treeNode Parent (TreeNode Subtree, TreeNode Element) {if (subTree == null) return null; if (subtree.getleftchild () == elemento || subtree.getRightChild () == elemento) // Finalizar, devuelva el subtree de retorno de la dirección del nodo principal; Treenode P; // Primero mira en el subárbol izquierdo. Si no se encuentra en el subárbol izquierdo, vaya al subárbol derecho para encontrar si ((p = parent (subtree.getleftchild (), elemento))! = Null) // busca recursivamente return p; else // busque recursivamente para retorno parent (subtree.getRightChild (), elemento); } public treeNode LeftChild (elemento treeNode) {// return el return de su subtree izquierdo (elemento! = nulo)? elemento.getleftchild (): nulo; } public treeNode RightChild (elemento treeNode) {// Devuelve el retorno de su subtree correcto (elemento! = NULL)? element.getRightChild (): nulo; } public treeNode getRoot () {// Obtener la raíz de retorno del nodo raíz; } public void Destroy (TreeNode Subtree) {// Función privada: Eliminar el subárbol con Root Subtree if (Subtree! = Null) {Destroy (subtree.getleftchild ()); // Eliminar el subárbol izquierdo destruir (subtree.getRightChild ()); // Eliminar el subárbol derecho // Eliminar substree; // Eliminar el subtree de nodo raíz = nulo; }} public void Traverse (TreeNode Subtree) {System.out.println ("Key:" + Subtree.getKey () + "--Name:" + subtree.getData ()); Traverse (subtree.getleftchild ()); Traverse (subtree.getRightChild ()); } Public void Preorder (TreeNode Subtree) {// root primero if (substree! = null) {Visted (substree); Preorden (subtree.getleftchild ()); Preorden (subtree.getRightChild ()); }} public void inOrder (treeNode substree) {// medio root if (subtree! = null) {inorder (subtree.getleftchild ()); visto (subárbol); Inorder (subtree.getRightChild ()); }} public void PostOrder (TreeNode Subtree) {// Post root if (subtree! = null) {PostOrder (subtree.getLeftChild ()); PostOrder (subtree.getRightChild ()); visto (subárbol); }} public void LevelOrder (TreeNode Subtree) {// Horily Periphery} public boolean Insert (treeNode Element) {// insertar return true; } public boolean Find (TreeNode Element) {// Buscar return true; } public void testificó (subtree treeNode) {subtree.setVisted (true); System.out.println ("Key:" + subtree.getkey () + "--name:" + subtree.getData ()); } public static void main (string [] args) {binarytree bt = new binarytree (); Bt.CreateBintree (Bt.root); System.out.println ("El tamaño del árbol es" + bt.size ()); System.out.println ("La altura del árbol es" + bt.height ()); System.out.println ("********* PREERDER (PREERDIO) [ABDECF] Transferencia ****************"); bt.preorder (bt.root); System.out.println ("********* Root medio (orden interno) [DBEACF] Transferencia ****************"); bt.inorder (bt.root); System.out.println ("********* Last Root (Post Order) [Debfca] Transferencia ****************"); bt.postorder (bt.root); }} Resultados de salida:
El tamaño del árbol es 6
La altura del árbol es 3
******* Primera raíz (preorden) [Abdecf] Traversal ******************
Clave: 1-Nombre: RootNode (a)
Clave: 2-Nombre: B
Clave: 4-Nombre: D
Clave: 5-Nombre: E
Clave: 3-Nombre: C
Clave: 6-Nombre: F
******* Root medio (Orden Medio) [DBeACF] Traversal **********************************
Clave: 4-Nombre: D
Clave: 2-Nombre: B
Clave: 5-Nombre: E
Clave: 1-Nombre: RootNode (a)
Clave: 3-Nombre: C
Clave: 6-Nombre: F
******* Last Root (Post Order) [Debfca] Traversal ********************
Clave: 4-Nombre: D
Clave: 5-Nombre: E
Clave: 2-Nombre: B
Clave: 6-Nombre: F
Clave: 3-Nombre: C
Clave: 1-Nombre: RootNode (a)
Espero que este artículo sea útil para los estudiantes que estudian la programación de Java.