Aggiungere un nodo ad un albero binario

[vfldj]

Ciao
Devo scrivere un metodo che aggiunga un nodo ad un albero binario.

public class BinaryTree {

	protected class Node {
	
		Integer element;
		Node left;
		Node right;
		
		Node(int element) {
			this.element = element;
			left = right = null;
		}

		Node(int element, Node left, Node right) {
			this.element = element;
			this.left = left;
			this.right = right;
		}

		boolean isLeaf() {
			return left == null && right == null;
		}
	}

	protected Node root;

	public BinaryTree() {
		root = null;
	}

	public boolean isEmpty() {
		return root == null;
	}
	
	/*
		Aggiunge un nodo nella posizione indicata da path
	*/
	public void add(int element, String path) {
		add(element, path, ?? );
	}

	protected Node add(int elem, String path, Node nd) {
		if(nd == null) 
			return new Node(elem);
		else { 
			if(path.length() == 0) 
				nd.element = elem; 
			else {
				char go = path.charAt(0);
				String nextPath = path.substring(1);
				if (go == 'L') 
					nd.left = add(elem, nd.left, nextPath);
				else if(go == 'R') 
					nd.right = add(elem, nd.right, nextPath);
				else 
					System.out.println("Path inadeguato");
			}
			
		}	
		return nd;
	}
}

Avevo pensato ad una cosa del genere ma non funziona, più che altro non so come completare il metodo..
Chi mi aiuta?

Grazie

[Patrick Jane]

Dai un occhio a questo codice: http://solopc.forumcommunity.net/?t=46658126
In particolare al metodo che ti interessa, add().

[vfldj]

Originariamente inviato da Patrick Jane
Dai un occhio a questo codice: http://solopc.forumcommunity.net/?t=46658126
In particolare al metodo che ti interessa, add().

Ma li parla delle liste ed il metodo add non è fatto come serve a me cioè usando in realtà due metodi (uno principale ed uno di appoggio)..

[Patrick Jane]

No scusa sono stato io a linkarti la roba sbagliata. xD
Dovrei avere del codice, ma è forse sull'altro pc... se lo trovo lo incollo qui.

EDIT:
Trovato, era disperso sulla chiavetta!

// Struttura Nodo
class Nodo {
  private int n;
  private Nodo left, right;
  private String p;

  Nodo(int n, Nodo left, Nodo right, String p) {
    this.n = n;
    this.left = left;
    this.right = right;
    this.p = p;
  }
  
  int getN() {
    return n;
  }
  
  Nodo getLeft() {
    return left;
  }
  
  Nodo getRight() {
    return right;
  }
  
  void setLeft(Nodo l) {
    this.left = l;
  }
  
  void setRight(Nodo r) {
    this.right = r;
  }
  String getP() {
    return p;
  }
}

// Alabero binario
class BinaryTree {
  private Nodo radice;
  
  // Riceve in ingresso un array di valori
  // da inserire nell'albero
  BinaryTree(int[] values) {
    Nodo nodo = null;
    String p = " ";
    for(int i=0; i<values.length; i++) {
      nodo = insertNodo(nodo, values[i], p);
    }
    radice = nodo;
  }
  
  void showTree() {
    show(radice);
  }
  
  private void show(Nodo start) {
    if(start != null) {
      System.out.println(start.getP()+" --> "+start.getN());
      show(start.getLeft());
      show(start.getRight());
    }
  }
  
  // Inserisce "val" nel nodo corretto
  private Nodo insertNodo(Nodo n, int val,String p) {
    // Se null non ha nodi figli; quindi creo
    // un nuovo nodo ed inizializzo i figli a null
    if(n == null) {
      n = new Nodo(val, null, null, p);
    }
    else {
      // Se il valore è maggiore al valore del nodo,
      // inserisco il valore nel figlio destro
      // (creandolo ricorsivamente)
      if(n.getN() < val) {
        p += "R";
        n.setRight(insertNodo(n.getRight(), val, p));
      }
      // Altrimenti nel sinistro...
      else if(n.getN() > val) {
        p += "L";
        n.setLeft(insertNodo(n.getLeft(), val, p));
      }
    }
    
    return n;
  }
  
  boolean present(int element) {
    return isPresent(element,radice);
  }
  
  private boolean isPresent(int element, Nodo radice) {
    if(radice != null) {
      if(radice.getN() == element) return true;
      else if(radice.getN() < element) {
        return isPresent(element, radice.getRight());
      }
      else {
        return isPresent(element, radice.getLeft());
      }
    }
    return false;
  }
  
}

class TestTree {
  public static void main(String[] args) {
    BinaryTree bt = new BinaryTree(new int[] {104,32,121,152,44,200,23, 55, 64, 12, 32, 91, 4});
    bt.showTree();
    
    int elemento = 91;
    System.out.println("Elemento da cercare: "+elemento+" --> "+bt.present(elemento));
  }
}

[vfldj]

Originariamente inviato da Patrick Jane
No scusa sono stato io a linkarti la roba sbagliata. xD
Dovrei avere del codice, ma è forse sull'altro pc... se lo trovo lo incollo qui.

EDIT:
Trovato, era disperso sulla chiavetta!

// Struttura Nodo
class Nodo {
  private int n;
  private Nodo left, right;
  private String p;

  Nodo(int n, Nodo left, Nodo right, String p) {
    this.n = n;
    this.left = left;
    this.right = right;
    this.p = p;
  }
  
  int getN() {
    return n;
  }
  
  Nodo getLeft() {
    return left;
  }
  
  Nodo getRight() {
    return right;
  }
  
  void setLeft(Nodo l) {
    this.left = l;
  }
  
  void setRight(Nodo r) {
    this.right = r;
  }
  String getP() {
    return p;
  }
}

// Alabero binario
class BinaryTree {
  private Nodo radice;
  
  // Riceve in ingresso un array di valori
  // da inserire nell'albero
  BinaryTree(int[] values) {
    Nodo nodo = null;
    String p = " ";
    for(int i=0; i<values.length; i++) {
      nodo = insertNodo(nodo, values[i], p);
    }
    radice = nodo;
  }
  
  void showTree() {
    show(radice);
  }
  
  private void show(Nodo start) {
    if(start != null) {
      System.out.println(start.getP()+" --> "+start.getN());
      show(start.getLeft());
      show(start.getRight());
    }
  }
  
  // Inserisce "val" nel nodo corretto
  private Nodo insertNodo(Nodo n, int val,String p) {
    // Se null non ha nodi figli; quindi creo
    // un nuovo nodo ed inizializzo i figli a null
    if(n == null) {
      n = new Nodo(val, null, null, p);
    }
    else {
      // Se il valore è maggiore al valore del nodo,
      // inserisco il valore nel figlio destro
      // (creandolo ricorsivamente)
      if(n.getN() < val) {
        p += "R";
        n.setRight(insertNodo(n.getRight(), val, p));
      }
      // Altrimenti nel sinistro...
      else if(n.getN() > val) {
        p += "L";
        n.setLeft(insertNodo(n.getLeft(), val, p));
      }
    }
    
    return n;
  }
  
  boolean present(int element) {
    return isPresent(element,radice);
  }
  
  private boolean isPresent(int element, Nodo radice) {
    if(radice != null) {
      if(radice.getN() == element) return true;
      else if(radice.getN() < element) {
        return isPresent(element, radice.getRight());
      }
      else {
        return isPresent(element, radice.getLeft());
      }
    }
    return false;
  }
  
}

class TestTree {
  public static void main(String[] args) {
    BinaryTree bt = new BinaryTree(new int[] {104,32,121,152,44,200,23, 55, 64, 12, 32, 91, 4});
    bt.showTree();
    
    int elemento = 91;
    System.out.println("Elemento da cercare: "+elemento+" --> "+bt.present(elemento));
  }
}

Gentilissimo pero' nel tuo caso l'albero e' ordinato, giusto?
Io non ce l'ho ordinato...

[Patrick Jane]

Si, nel mio caso si. In caso non lo volessi ordinato, dovrebbe anche essere più semplice... dovrebbe essere sufficiente verificare la presenza dell'elemento nel figlio sinistro, e se è vuoto inserirlo.

[vfldj]

Originariamente inviato da Patrick Jane
Si, nel mio caso si. In caso non lo volessi ordinato, dovrebbe anche essere più semplice... dovrebbe essere sufficiente verificare la presenza dell'elemento nel figlio sinistro, e se è vuoto inserirlo.

ehm no perchè il nodo dev'essere inserito nella posizione che dice il path (es. L, R, LL...)..

[vfldj]

Qualcun altro che mi aiuti?