O que é uma árvore binária? Eu não vou apresentá -lo aqui. Você pode usar o Baidu: uma árvore binária. Aqui, use o Java para implementar a "Árvore binária de expressão".
Definição de Expressão Binária Árvore
O primeiro passo é entender qual é a árvore binária da expressão? Por exemplo, a expressão: (a+b × (cd))-e/f. Colocar números no nó e operador da folha no nó da filial forma uma árvore binária. Como armazena uma expressão, é chamada de "árvore binária de expressão".
As botas infantis podem estar curiosas sobre como isso foi construído? Pegue 45+23*56/2-5 como exemplo. Primeiro, retire o primeiro número 45 e coloque -o no nó da folha. Depois de encontrar "+", coloque -o no nó da filial.
Em seguida, coloque "23", "*", "56", "/" e "2" em sequência.
Finalmente coloque "-" e "5",
Isso é aproximadamente isso. (Eu mesmo tirei essas fotos, é feio, apenas dê uma olhada nelas (⊙⊙ ⊙⊙))
Etapas para construir uma árvore binária de expressão
1. Crie um objeto de nó;
2. Distinguir operadores e dados e armazená -los na lista correspondente (fila);
3. Retire os dois primeiros números e um operador para formar um novo nó numérico;
4. Repita a etapa 3 até que o operador esteja concluído;
5. Deixe o nó raiz igual ao último nó.
Implementação da árvore binária de expressão
Primeiro, crie a classe de objeto Node, incluindo dados, subárvore esquerda, subárvore direita e vários métodos de conjunto e obtenção.
pacote Tets0714;/** * Nó // Nó privado da subárvore esquerda lChild; // Nó privado da subárvore direita RCHILD; Node () {} node (string data) {this.data = data; } Node (dados da string, nó lchild, nó rchild) {super (); this.data = dados; this.lchild = lChild; this.rchild = rchild; } public string getData () {return data; } public node getlchild () {return lchild; } public node getrchild () {return rchild; }}Em seguida, construa a árvore binária de expressão.
pacote Tets0714; importar java.util.ArrayList;/** * Expressão classe de árvore binária * @author yuxiu * */public class Formaluetree {private string s = ""; raiz de nós privados; // nó raiz/*** Crie uma expressão binária* @param str expressão*/public void critree (string str) {// declare uma lista de matrizes, operadores de armazenamento, adicione, subtrair, multiplicação e divisão, ArrayList <String> operatorList = new ArrayList <String> (); // Declare uma lista de matrizes, armazenar dados do nó, ArrayList <Node> numList = new ArrayList <Node> (); // Primeiro, distingue o operador e os dados e armazene -o na lista correspondente para (int i = 0; i <str.Length (); i ++) {char ch = str.Charat (i); // busca os caracteres da string if (ch> = '0' && CH <= '9') {s+= ch; } else {numList.add (novo (s) nó (s)); s = ""; operatorlist.add (CH+""); }} // Adicione o último número ao nó numérico numList.add (novo (s) nó (s)); while (operlist.size ()> 0) {// Etapa 3, repita a segunda etapa até que o operador esteja concluído // segundo, retire os dois primeiros números e um operador para formar um novo nó número do nó esquerdo = numList.remove (0); Nó direito = numList.Remove (0); Operador string = operatorlist.remove (0); Nó do nó = novo nó (operação, esquerda, direita); numList.add (0, nó); // prefere o novo nó como o primeiro nó e o nó anterior com índice = 0 é alterado para index = 1} // Etapa 4, deixe o nó raiz igual ao último nó root = numList.get (0); } / *** Dados do nó de saída* / public void output () {output (root); // Pare de atravessar o nó raiz}/*** Dados do nó de saída* @param nó*/public void Output (nó nó) {if (node.getlchild ()! = Null) {// se for um nó folha, ele terá a saída (node.getlChild ()); } System.out.print (node.getData ()); // A transação inclui travessia de pré-encomenda (raiz esquerda e direita), travessia na ordem (raiz esquerda direita) e travessia do Postorder (raiz esquerda direita) se (node.getrchild ()! = Null) {output (node.getrchild ()); }} public static void main (string [] args) {formaluetree árvore = new Formaluetree (); árvore.creattree ("45+23*56/2-5"); // Crie a árvore binária da árvore de expressão.Output (); // Verificação de saída}} Finalmente, você pode produzir "45+23*56/2-5" no console, ok. Na traseira da ordem média usada aqui, os amigos podem tentar o que o efeito é usar travessias de pré -encomenda e travessias postais. Quanto a Traversal, falaremos sobre isso mais tarde.
O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.