¿Qué es un árbol binario? No lo presentaré aquí. Puedes usar Baidu: un árbol binario. Aquí, use Java para implementar el "Árbol binario de expresión".
Definición de expresión de árbol binario
El primer paso es comprender cuál es el árbol binario de expresión? Por ejemplo, la expresión: (A+B × (CD))-E/F. Poner números en el nodo y operador de la hoja en el nodo de rama forma un árbol binario. Dado que almacena una expresión, se llama "árbol binario de expresión".
Las botas para niños pueden tener curiosidad sobre cómo se construyó esto. Tome 45+23*56/2-5 como ejemplo. Primero saque el primer número 45 y póngalo en el nodo de la hoja. Después de encontrar "+", póngalo en el nodo de rama.
Luego ponga "23", "*", "56", "/" y "2" en secuencia.
Finalmente poner "-" y "5",
Eso es más o menos eso. (Dibujé estas fotos, es feo, solo échales un vistazo (⊙⊙))
Pasos para construir un árbol binario de expresión
1. Crear un objeto de nodo;
2. Distinguir operadores y datos y almacenarlos en la lista correspondiente (cola);
3. Saque los dos primeros números y un operador para formar un nuevo nodo numérico;
4. Repita el paso 3 hasta que el operador esté terminado;
5. Deje que el nodo raíz sea igual al último nodo.
Implementación del árbol binario de expresión
Primero, cree la clase de objeto de nodo, incluidos los datos, el subárbol izquierdo, el subárbol derecho y varios métodos establecidos y obtenidos.
paquete tets0714;/** * Clase de objeto de nodo * @author yuxiu * */public class node {// datos privados de datos de cadena; // Izquierda Subtree Private Node Lchild; // Nodo privado de subárbol correcto RCHILD; Node () {} nodo (datos de cadena) {this.data = data; } Nodo (datos de cadena, nodo lchild, nodo rchild) {super (); this.data = data; this.lchild = lchild; this.rchild = rchild; } public string getData () {return data; } public nodo getLChild () {return lchild; } public nodo getrchild () {return rchild; }}Luego construya el árbol binario de expresión.
paquete tets0714; import java.util.ArrayList;/** * Expression Binary Tree Class * @author yuxiu * */public class formaluetree {private String s = ""; raíz de nodo privado; // root nodo/*** Crear expresión binary árbol* @param str express*/public void createTree (string str) {// declarar una lista de matriz, almacenar operadores, agregar, restar, multiplicar y división, arrayList <String> operatorList = new ArrayList <String> (); // declarar una lista de matriz, almacenar datos de nodo, arrayList <Node> numList = new ArrayList <Node> (); // Primero, distinga el operador y los datos y guárdelo en la lista correspondiente para (int i = 0; i <str.length (); i ++) {char ch = str.charat (i); // Retira los caracteres de la cadena if (ch> = '0' && ch <= '9') {s+= ch; } else {numList.Add (nuevo nodo (s)); s = ""; OperatorList.Add (CH+""); }} // Agregue el último número al nodo numérico numlist.add (nuevo (s) (s)); Mientras (operlist.size ()> 0) {// Paso 3, repita el segundo paso hasta que el operador esté terminado // segundo, elimine los dos primeros números y un operador para formar un nuevo nodo de nodo de número Left = numList.Remove (0); Nodo derecho = numList.remove (0); String operator = operatorList.remove (0); Nodo nodo = nuevo nodo (operación, izquierda, derecha); numList.Add (0, nodo); // Prefiere el nuevo nodo como el primer nodo, y el nodo anterior con index = 0 se cambia a index = 1} // Paso 4, deje que el nodo raíz sea igual al último nodo root = numList.get (0); } / *** Datos de nodo de salida* / public void output () {output (root); // Detener el transbordador del nodo raíz}/*** datos de nodo de salida* @param nodo*/public void output (nodo nodo) {if (node.getlchild ()! = Null) {// Si es un nodo de hoja, finalizará la salida (node.getlchild ()); } System.out.print (node.getData ()); // La transacción incluye el recorrido por preorden (raíz izquierda y derecha), transversal en orden (raíz izquierda a la derecha) y PostOrder Traversal (raíz izquierda derecha) if (node.getRchild ()! = Null) {output (node.getRchild ()); }} public static void main (string [] args) {formaluetree tree = new formaluetree (); árbol.creattree ("45+23*56/2-5"); // Crea el árbol binario de la expresión tree.output (); // Verificación de salida}} Finalmente, puede emitir "45+23*56/2-5" en la consola, OK. En el orden medio de transversal utilizado aquí, los amigos pueden probar cuál es el efecto de usar el recorrido por preorden y el recorrido posterior al orden. En cuanto al recorrido, hablaremos de ello más tarde.
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.