Qu'est-ce qu'un arbre binaire? Je ne le présenterai pas ici. Vous pouvez utiliser Baidu: un arbre binaire. Ici, utilisez Java pour implémenter "l'expression arborescence binaire".
Définition de l'expression arbre binaire
La première étape consiste à comprendre ce qu'est l'arbre binaire d'expression? Par exemple, l'expression: (a + b × (cd)) - e / f. Mettre des nombres dans le nœud foliaire et l'opérateur dans le nœud de branche forme un arbre binaire. Puisqu'il stocke une expression, il est appelé "l'expression arborescence binaire".
Les bottes pour enfants peuvent être curieuses de la façon dont cela a été construit? Prenez 45 + 23 * 56 / 2-5 comme exemple. Sortez d'abord le premier numéro 45 et mettez-le dans le nœud feuille. Après avoir rencontré "+", mettez-le sur le nœud de branche.
Ensuite, mettez "23", "*", "56", "/" et "2" en séquence.
Enfin, mettez "-" et "5",
C'est à peu près ça. (J'ai dessiné ces photos moi-même, c'est moche, jetez un œil aux yeux (⊙⊙))
Étapes pour construire l'expression arbre binaire
1. Créez un objet de nœud;
2. Distinguer les opérateurs et les données et les stocker dans la liste correspondante (file d'attente);
3. Sortez les deux premiers numéros et un opérateur pour former un nouveau nœud de numéro;
4. Répétez l'étape 3 jusqu'à la fin de l'opérateur;
5. Laissez le nœud racine égal au dernier nœud.
Implémentation de l'expression arbre binaire
Tout d'abord, créez la classe d'objets de nœud, y compris les données, le sous-arbre gauche, le sous-arbre droit et plusieurs méthodes d'ensemble et d'obtention.
Package TETS0714; / ** * Classe d'objets de nœud * @author yuxiu * * / classe publique nœud {// data private String data; // Le nœud privé de Subtree gauche lChild; // RCHILD PRIVÉ SUBTREE DROIT; Node () {} Node (String Data) {this.data = data; } Nœud (data de chaîne, nœud lChild, nœud rchild) {super (); this.data = data; this.lchild = lchild; this.rchild = rchild; } public String getData () {return data; } Node public getlchild () {return lChild; } Node public getrchild () {return rChild; }}Construisez ensuite l'arbre binaire d'expression.
package tets0714; import java.util.arraylist; / ** * expression classbin binaire * @author yuxiu * * / classe publique formulArEREe {chaîne privée s = ""; racine de nœud privé; // Root Node / ** * Create Expression Binary Tree * @param Str Expression * / public void CreatTree (String str) {// Declare une liste de tableaux, opérateurs de magasin, add, soustraire, multiplication et division, arrayList <string> opératorList = new ArrayList <string> (); // Déclare une liste de tableaux, Store Node Data, ArrayList <Node> numList = new ArrayList <Node> (); // Distinguer l'opérateur et les données et les stocker dans la liste correspondante pour (int i = 0; i <str.length (); i ++) {char ch = str.charat (i); // Récupérez les caractères de la chaîne if (ch> = '0' && ch <= '9') {s + = ch; } else {numList.add (nouveau nœud (s)); S = ""; OperatorList.add (Ch + ""); }} // Ajouter le dernier numéro dans le nœud nœud numList.add (nouveau nœud (s)); while (operList.size ()> 0) {// Étape 3, répétez la deuxième étape jusqu'à ce que l'opérateur soit terminé // seconde, retirez les deux premiers numéros et un opérateur pour former un nouveau nœud de nœud de numéro Left = numList.Remove (0); Node droit = numList.Remove (0); String Operator = OperatorList.Remove (0); Nœud nœud = nouveau nœud (opé, gauche, droite); numList.add (0, nœud); // préfère le nouveau nœud comme premier nœud, et le nœud précédent avec index = 0 est modifié en index = 1} // étape 4, laissez le nœud racine égal au dernier nœud root = numList.get (0); } / ** * Données de nœud de sortie * / public void Output () {output (root); // Stop Traversal du nœud racine} / ** * Données de nœud de sortie * @param nœud * / public void output (nœud node) {if (node.getlchild ()! = Null) {// s'il s'agit d'un nœud de feuille, il finira la sortie (node.getlchild ()); } System.out.print (Node.getData ()); // La transaction inclut la traversée de précommande (root gauche et droite), la traversée dans l'ordre (root gauche à droite) et la traversée post-ordre (Root à droite gauche) if (node.getRchild ()! = Null) {output (node.getrchild ()); }} public static void main (String [] args) {FormAluetree arbre = new FormAlueTree (); Tree.Creatree ("45 + 23 * 56 / 2-5"); // Créez l'arbre binaire de l'expression arborescence.output (); // Vérification de sortie}} Enfin, vous pouvez produire "45 + 23 * 56 / 2-5" dans la console, OK. Dans la traversée de l'ordre moyen utilisé ici, les amis peuvent essayer l'effet d'utiliser la traversée de traversée et la traversée post-ordre de la précommande. Quant à la traversée, nous en parlerons plus tard.
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.