Explicación detallada del árbol de clasificación binaria de Java

Uno, definición de árbol de clasificación binaria
1. Definición de árbol de clasificación binaria <Br /> Árbol de clasificación binario (árbol de clasificación binario), también conocido como árbol de búsqueda binario. Se define como: un árbol de clasificación binario o un árbol vacío, o un árbol binario que cumple con las siguientes propiedades:
① Si su subárbol izquierdo no está vacío, los valores de todos los nodos en el subárbol izquierdo son más pequeños que el valor del nodo raíz;
② Si su subárbol derecho no está vacío, los valores de todos los nodos en el subárbol derecho son mayores que los valores del nodo raíz;
③El propio, los suelos de la izquierda y la derecha son un árbol de clasificación binario.
Las propiedades anteriores se denominan propiedad del árbol de clasificación binaria (propiedad BST), por lo que el árbol de clasificación binario es en realidad un árbol binario que satisface la propiedad BST.

2. Las propiedades del árbol de clasificación binario <Br /> Transfieren el árbol de clasificación binario en orden medio, y la secuencia transversal de orden intermedio resultante es una secuencia ordenada incremental.

3. Inserte el árbol de clasificación binario <Br /> Inserte un nuevo nodo en el árbol de clasificación binario, para asegurarse de que el árbol binario insertado todavía cumpla con la definición del árbol de clasificación binario.
Insertar proceso:
Si el árbol de clasificación binario está vacío, el nodo *s se insertará en el árbol vacío como el nodo raíz;
Cuando no esté vacío, compare la tecla de palabra clave S-> que se insertará con la tecla T-> Tecla T-> Tecla T-> Si s-> key = t-> key, no hay necesidad de insertarlo. Si s-> tecla <t-> tecla, se inserta en el subárbol izquierdo de la raíz. Si s-> tecla> t-> tecla, se inserta en el subárbol derecho de la raíz. El proceso de inserción en el subárbol es el mismo que el proceso de inserción en el árbol. Esto continúa hasta que el nodo *s se inserta en el árbol de clasificación binario como una hoja nueva, o hasta que el árbol tenga nodos con las mismas palabras clave.

4. Busque el árbol de clasificación binario <Br /> Suponiendo que el puntero raíz del árbol de clasificación binario es raíz y el valor de la palabra clave dado es k, el algoritmo de búsqueda puede describirse como:
① Establecer valor inicial: q = root;
② Si K = Q -> Key, la búsqueda es exitosa y el algoritmo termina;
③ de lo contrario, si la tecla K <Q －＞ y el subárbol izquierdo de Q no está vacío, el subárbol izquierdo de Q se envía a Q y luego el paso ②; De lo contrario, la búsqueda falla y el algoritmo termina;
④ de lo contrario, si K ＞ Q －＞ clave, y el subárbol derecho de Q no está vacío, el subárbol correcto de Q se envía a Q y luego el paso ②; De lo contrario, la búsqueda falla y el algoritmo termina.

5. Deletion del árbol de clasificación binario <Br /> Suponga que el nodo eliminado es *P y los padres son *F, que no se pierde en generalidad. Suponga que *P es el hijo izquierdo de *F, lo siguiente se divide en tres situaciones:
⑴ Si el nodo *P es un nodo hoja, solo necesita modificar el puntero de su nodo principal *f.
⑵ Si el nodo *P solo tiene el subárbol izquierdo PL o solo el subárbol derecho PR, simplemente haga PL o PR el subárbol izquierdo de su nodo principal.
⑶ Si los subárboles izquierdo y derecho del nodo *p no están vacíos, primero encuentre el nodo predecesor (o sucesor) de orden medio (o sucesor) *s de *p (tenga en cuenta que *s es el nodo más inferior derecho en el subrere de la izquierda de *P, y su dominio de cadena derecho *f está vacío), y luego hay dos formas: ① Subree izquierdo de *P es el enlace directo a la cadena izquierda de la noda parentada de la red de *f de * encadenado a la cadena derecha del nodo predecesor de orden medio de *P *s. ② Reemplace *P con el nodo predecesor de orden medio *s de *p (es decir, copie los datos de *s en *p) y encadene el subárbol izquierdo de *s a la cadena izquierda (o derecha) del nodo principal *q de *s.
6. Traversal de los árboles binarios <Br /> Hay tres formas de atravesar árboles binarios, de la siguiente manera:
(1) Re-orden de transferencia (DLR), primero accediendo al nodo raíz, luego atravesando el subárbol izquierdo y finalmente atravesando el subárbol derecho. Raíz abreviada - izquierda - derecha.
(2) Traversal en orden (LDR), primero atraviesa el subárbol izquierdo, luego acceda al nodo raíz y finalmente atraviesa el subárbol derecho. Nota abreviada: raíz izquierda-derecha.
(3) Traversal posterior al orden (LRD), primero atravesando el subárbol izquierdo, luego atravesando el subárbol derecho y finalmente accediendo al nodo raíz. Raíz izquierda-derecha abreviada.

2. Escribir en código
1. Definición de la clase de nodo de árbol 0

 paquete com.lin; / ** * Resumen de la función: */ public class treeNode {public Integer Data; /* Nodo principal de este nodo*/ Public treeNode Parent; /*Nodo infantil izquierdo de este nodo*/ Public TreeNode Izquierda; /*Nodo infantil correcto de este nodo*/ Public treeNode Right; public treeNode (datos enteros) {this.data = data; } @Override public string toString () {return "treeNode [data =" + data + "]"; }}

2. Definición de árbol de clasificación binaria

 paquete com.lin; /*** Resumen de la función: árbol binario sort/equilibrado*/public class Searchtree {public treeNode root; Público largo tamaño; / ** * Agregar nodo al árbol * @param data * @return La inserción boolean devuelve verdadero */ public boolean addTreeNode (integer data) {if (null == root) {root = new treeNode (data); System.out.println ("Los datos se insertaron correctamente en el árbol binario equilibrado"); devolver verdadero; } TreeNode treeNode = new TreeNode (datos); // Los datos que se insertarán a TreeNode CurrentNode = root; TreeNode ParentNode; while (true) {parentNode = currentNode; // guardar el nodo principal // Los datos insertados son más pequeños que el nodo principal if (currentNode.Data> data) {currentNode = currentNode.left; // El nodo hijo izquierdo del nodo principal actual está vacío si (null == currentNode) {parentNode.left = treeNode; treeNode.parent = parentNode; System.out.println ("Los datos se insertaron correctamente en el árbol de búsqueda binario"); tamaño ++; devolver verdadero; } // Los datos insertados son más grandes que el nodo principal} else if (currentNode.Data <data) {currentNode = currentNode.right; // El nodo infantil correcto del nodo principal actual está vacío si (null == currentNode) {parentNode.right = treeNode; treeNode.parent = parentNode; System.out.println ("Los datos se insertan correctamente en el árbol de búsqueda binario"); tamaño ++; devolver verdadero; }} else {System.out.println ("Los datos de entrada son los mismos que los datos del nodo"); devolver falso; }}} / ** * @param datos * @return treeNode * / public treeNode findTreeNode (integer data) {if (null == root) {return null; } TreeNode Current = root; while (current! = null) {if (current.data> data) {current = current.left; } else if (current.data <data) {current = current.right; } else {return actual; }} return null; }}

Aquí hay un método para agregar y buscar
3. Traversal delantero, medio y trasero

 paquete com.lin; import java.util.stack; / *** Resumen de la función:*/ public class TreeOrge {/ *** Implementación recursiva del recorrido por preorden* @author linbingwen* @SCECE 29 de agosto de 2015* @param treenode*/ public static void preordermethodone (treenode treenode) {si (null! = Treenode) {System.out.print (treenode. if (null! = treeNode.left) {preordenMethodone (treeNode.left); } if (null! = treeNode.right) {preordenMethodone (treeNode.right); }}} / *** bucle para implementar el traversal de pedido* @param treeNode* / public static void preorderMethodtwo (treeNode treeNode) {if (null! = TreeNode) {stack <reenode> stack = new stack <reeNode> (); stack.push (treeNode); while (! stack.isempty ()) {treeNode tempNode = stack.pop (); System.out.print (tempnode.data + ""); // El nodo infantil correcto no es nulo, coloque el nodo infantil correcto en if (null! = Tempnode.right) {stack.push (tempnode.right); } // Después de colocar el nodo infantil correcto, coloque el nodo infantil izquierdo y tome if (null! = Tempnode.left) {stack.push (tempnode.left); }}}} / *** Implementa recursivamente Traversal en orden* @param treeNode* / public static void medOrderMethodone (treeNode treeNode) {if (null! = TreeNode) {if (null! = TreeNode.left) {medorderMethodone (treenode.left); } System.out.print (treeNode.Data + ""); if (null! = treeNode.right) {MedOrderMethodone (treeNode.right); }}} / *** Implementación de bucle Traversal en orden* @param treeNode* / public static void medOrderMethodtwo (treeNode treeNode) {stack <reeNode> stack = new Stack <Teenode> (); TreeNode Current = treeNode; while (actual! = null || corriente = corriente.left; } if (! stack.isEmpty ()) {current = stack.pop (); System.out.print (current.data+""); actual = corriente.right; }}} / *** Implementa recursivamente Traversal posterior al pedido* @param treeNode* / public static void PostOrderMethodone (treeNode treeNode) {if (null! = TreeNode) {if (null! = TreeNode.left) {PostOrderMethodone (treeNODE.LETT); } if (null! = treeNode.right) {PostOrderMethodone (treeNode.right); } System.out.print (treeNode.Data + ""); }} / *** bucle para implementar el transcurrido posterior al pedido* @param treeNode* / public static void PostOrderMethodtwo (treeNode treeNode) {if (null! = TreeNode) {stack <treenode> stack = new stack <reeNode> (); TreeNode Current = treeNode; TreeNode RightNode = NULL; while (actual! = null || corriente = corriente.left; } actual = stack.pop (); while (current! = null && (current.right == null || current.right == rightnode)) {system.out.print (current.data + ""); rightnode = corriente; if (stack.isempty ()) {system.out.println (); devolver; } actual = stack.pop (); } stack.push (actual); actual = corriente.right; }}}}

4. Cómo usar

 paquete com.lin; / ** * Resumen de la función: */ public class SearchTreetest {/ ** * @param args */ public static void main (string [] args) {searchtree tree = new Searchtree (); árbol.addtreenode (50); árbol.addtreenode (80); árbol.addtreenode (20); árbol.addtreenode (60); árbol.addtreenode (10); árbol.addtreenode (30); árbol.addtreenode (70); árbol.addtreenode (90); árbol.addtreenode (100); árbol.addtreenode (40); System.out.println("===================================================================================================== ============================================================== ================================================================ ============================================================== ================================================================ ================================================================ ================================================================ System.out.println ("================================================ =================================================================== =================================================================== ===================================================================== =================================================================== =================================================================== =================================================================== ===================================================================== TreeOrge.PostOrderMethodone (tree.root); System.out.println("====================================================================================================== ================================================================ ================================================================= ================================================================ ================================================================= ================================================================ ================================================================= System.out.println ("================================================ =================================================================== =================================================================== ===================================================================== =================================================================== =================================================================== =================================================================== ===================================================================== TreeRorder.MedOrderMethodTwo (Tree.root);

Resultado de salida:

Del mismo modo, el proceso de búsqueda es el siguiente:

 TreeNode nodo = tree.findtreenode (100); System.out.println (nodo);

El resultado es correcto

Lo anterior es una introducción detallada al árbol de clasificación binario de Java. Espero que sea útil para la programación de Java de aprendizaje de todos.