public class Noeud {
	private Noeud gauche;
	private Noeud droit;

	public Noeud(Noeud g, Noeud d) {
		this.gauche = g;
		this.droit = d;
	}

	public Noeud() {
		this.gauche = null;
		this.droit = null;
	}

	public Noeud getGauche() {
		return this.gauche;
	}

	public Noeud getDroit() {
		return this.droit;
	}

	public void setGauche(Noeud x) {
		this.gauche = x;
	}

	public void setDroit(Noeud x) {
		this.droit = x;
	}

	public boolean estFeuille() {
		if(this.gauche == null && this.droit == null) {
			return true;
		}
		else {
			return false;
		}
	}

	public void bourgeons() {
		if(this.estFeuille()) {
			this.gauche = new Noeud();
			this.droit = new Noeud();
		}
		if(this.gauche != null) {
			this.gauche.bourgeons();
		}
		if(this.droit != null) {
			this.droit.bourgeons();
		}
	}

	public void elagage() {
		if(this.gauche != null) {
			if(this.gauche.estFeuille()) {
				this.gauche = null;
			}
			else {
				this.gauche.elagage();
			}
		}
		if(this.droit != null) {
			if(this.droit.estFeuille()) {
				this.droit = null;
			}
			else {
				this.droit.elagage();
			}
		}
	}

	public void croissance() {
		if(this.gauche != null) {
			this.gauche = new Noeud(this.gauche, null);
			this.gauche.gauche.croissance();
		}
		if(this.droit != null) {
			this.droit = new Noeud(null, this.droit);
			this.droit.droit.croissance();
		}
	}

	public void decroissance() {
		if(this.gauche != null && this.gauche.gauche != null) {
			this.gauche = this.gauche.gauche;
			this.gauche.decroissance();
		}
		if(this.droit != null && this.droit.droit != null) {
			this.droit = this.droit.droit;
			this.droit.decroissance();
		}
	}

	public Noeud sousArbre(String chemin) {
		if(chemin.equals("")) {
			return this;
		}
		char premier = chemin.charAt(0);
		if(premier == 'g') {
			if(this.gauche == null) {
				return null;
			}
			return this.gauche.sousArbre(chemin.substring(1));
		}
		if(premier == 'd') {
			if(this.droit == null) {
				return null;
			}
			return this.droit.sousArbre(chemin.substring(1));
		}
		System.out.println("Ceci n'est pas un chemin.");
		return null;
	}
}