Tenho estas duas classes
/************************ BSTNode.java **************************
* node of a generic binary search tree
*/
public class BSTNode {
protected int key;
protected BSTNode left, right;
public BSTNode() {
left = right = null;
}
public BSTNode(int num) {
this(num,null,null);
}
public BSTNode(int num, BSTNode lt, BSTNode rt) {
this.key = num; left = lt; right = rt;
}
}
/************************ BST.java **************************
* generic binary search tree
*/
public class BST {
protected BSTNode root = null;
public BST() {
}
public void clear() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public BSTNode getRootNode (){
return root;
}
public boolean insert(int el) {
BSTNode p = root, prev = null;
// caso o valor já exista na árvore, não inserir e retornar false
if (search(el)!=null) return false;
// procurando um lugar para colocar o novo nó
while (p != null) {
prev = p;
if (el<p.key) p = p.left;
else p = p.right;
}
// se árvore vazia
if (root == null) root = new BSTNode(el);
else if (prev.key<el) prev.right = new BSTNode(el);
else prev.left = new BSTNode(el);
return true;
}
public BSTNode search(int el) {
return search(root,el);
}
protected BSTNode search(BSTNode p, int el) {
while (p != null) {
/* se valor procuradp == chave do nó retorna referência ao nó */
if (el==p.key) return p;
/* se valor procurado < chave do nó, procurar na sub-árvore esquerda deste nó */
else if (el<p.key) p = p.left;
/* se valor procurado > chave do nó, procurar na sub-árvore direita deste nó */
else p = p.right;
}
// caso chave não foi achada, retorna null
return null;
}
/* métodos de busca recursivos */
public BSTNode searchR (int el) {
return searchR(root,el);
}
protected BSTNode searchR(BSTNode p, int el) {
if (p==null || el==p.key) return p;
else if (el<p.key) return searchR (p.left, el);
else return searchR (p.right, el);
}
protected BSTNode searchFather (int el) {
BSTNode p = root;
BSTNode prev = null;
while (p != null && !(p.key==el)) { // acha o nó p com a chave el
prev = p;
if (p.key<el)
p = p.right;
else p = p.left;
}
if (p!=null && p.key==el) return prev;
return null;
}
public void inorder() {
inorder(root);
}
protected void inorder(BSTNode p) {
if (p != null) {
inorder(p.left);
System.out.print(p.key + " ");
inorder(p.right);
}
}
public void preorder() {
preorder(root);
}
protected void preorder(BSTNode p) {
if (p != null) {
System.out.print(p.key + " ");
preorder(p.left);
preorder(p.right);
}
}
public void postorder() {
postorder(root);
}
protected void postorder(BSTNode p) {
if (p != null) {
postorder(p.left);
postorder(p.right);
System.out.print(p.key + " ");
}
}
public void deleteByCopying(int el) {
BSTNode node, father = null;
node = search (el) ; // procura nó a ser deletado
if (node != null && node.key==el) {
if (node!=root) father = searchFather (el); // procura pai do nó a ser deletado
if (node.right == null){ // nó não tem filho direito (caso 2);
if (node==root) root= node.left;
else if (father.left == node) father.left = node.left;
else father.right = node.left;
}
else if (node.left == null) { // nó não tem filho esquerdo (caso 2)
if (node==root) root= node.right;
else if (father.left == node) father.left = node.right;
else father.right = node.right;
}
else { // nó tem ambos os filhos: fazer remoção por cópia
BSTNode tmp = node.left; // 1. pegando sub-arvore esquerda
while (tmp.right != null) { // 2. acha a posicao mais a direita
tmp = tmp.right; // da sub-árvore esquerda do nó
}
deleteByCopying (tmp.key); // remove por copia o nó que possui o maior valor
// da sub-arvore esquerda do nó a ser deletado
node.key = tmp.key; // copia o valor da chave do maior nó
// da subárvore esquerda
}
}
else if (root != null)
System.out.println("el " + el + " is not in the tree");
else System.out.println("the tree is empty");
}
public void deleteByMerging(int el) {
BSTNode tmp, node,father = null;
node = search (el) ; // procura nó a ser deletado
if (node != null && node.key==el) {
if (node!=root) father = searchFather (el); // procura pai do nó a ser deletado
if (node.right == null){ // nó não tem filho direito (caso 2);
if (root==node) root=node.left;
else if (father.left == node) father.left = node.left;
else father.right = node.left;
}
else if (node.left == null) { // nó não tem filho esquerdo (caso 2)
if (root==node) root=node.right;
else if (father.left == node) father.left = node.right;
else father.right = node.right;
}
else { // se tem dois filhos, faz deleção por fusão
tmp = node.left; // pega sub-arvore esquerda
while (tmp.right != null) // pega filho mais a direita da sub-arvore esquerda
tmp = tmp.right;
tmp.right = node.right; // o filho mais a direita da sub-arvore esquerda passa a ter
// como filho direito o filho direito do nó a ser deletado
if (root==node)
root = node.left;
else if (father.left == node)
father.left = node.left;
else father.right = node.left;
}
}
else if (root != null)
System.out.println("el " + el + " is not in the tree");
else System.out.println("the tree is empty");
}
public int max (int i, int j){
return i>j?i:j;
}
/** Método de autoria de Leonardo Zandoná - 2006/2
* Este método exibe a árvore em ASCII */
public void displayTree() {
if (isEmpty()) {
System.out.println("Árvore vazia!");
return;
}
String separator = String.valueOf(" |__");
System.out.println(this.root.key);
displaySubTree(root.left, separator);
displaySubTree(root.right, separator);
}
private void displaySubTree(BSTNode node, String separator) {
if (node != null) {
BSTNode father = this.searchFather(node.key);
if (node.equals(father.left) == true) {
System.out.println(separator+node.key+" (ESQ)");
}else{
System.out.println(separator+node.key+" (DIR)");
}
displaySubTree(node.left, " "+separator);
displaySubTree(node.right, " "+separator);
}
}
public static void main (String args[]){
BST b = new BST();
b.insert(5);
b.insert(3);
b.insert(8);
b.insert(1);
b.insert(4);
b.insert(6);
b.insert(9);
b.insert(2);
b.displayTree();
System.out.print("\n\nEM-ORDEM: ");
b.inorder();
System.out.print("\nPOS-ORDEM: ");
b.postorder();
System.out.print("\nPRE-ORDERM: ");
b.preorder();
System.out.println("\n");
}
}
Preciso criar um programa que recebe uma expessao infixa e coloca numa arvore segue o algoritinmo abaixo só que eu nao consegui entender nada deste algoritimo alguem que entende poderia me ajudar a converter para linguagem java?
Segue abaixo o algoritimo que nao consegui criar em java
Procedimento Interpretar(string)->ponteiro
COMEÇO
1. fazer uma árvore com a string como único nó;
2. procurar por operadores de MENOR precedência (+ ou -) que não
estejam dentro de ?(? e ?)?, pois estes serão considerados um
operando.
se tem, substitua a árvore por uma com o operador no nó raiz e com os
operandos nos nós folha. (se você procurar o PRIMEIRO operando com
menor precedência, basta dividir a árvore como explicado e aplicar esse
procedimento de procurar operador de menor precedência recursivamente
no nó da DIREITA). Lembre-se que um operando é um número, uma
variável uma expressão entre parêntesis ou uma função.
3. repetir o procedimento 2 com operadores de MÉDIA precedência (* e /)
SÓ EM NÓS FOLHA;
4. repetir o procedimento para operadores com MAIOR precedência (só o
^);
5. percorrer os nos folha (todos contém operandos)
se o operando é número ou variável, não mexe.
se o operando é expressão entre parêntesis, substituir esse nó por
Interpretar(expressão sem os parêntesis);
FIM Interpretar.