Dostalem program do napisania, mialem zrobic drzewo binarne BST. Wypisac minimalna liczbe oraz dodawac badz usuwac dodatkowe wezly, problem w tym ze nie wiem co dalej zrobic..
package dodatkowezadanie;
import java.util.Scanner;
class BSTNode{
int value; //wartosc w wezle
BSTNode left, right; //synowie - lewy i prawy
BSTNode(int v){ //konstruktor wezla
value = v;
left = right = null;
}
}
class BSTTree{
BSTNode root; //korzeń
BSTTree(){ //konstruktor drzewa BST
root = null;
}
public void add(int v){ //dodawanie do drzewa
if(root == null){ //gdy drzewo jest puste
root = new BSTNode(v);
return;
}
BSTNode p = root;
while(true){ //szukamy odpowiedniego miejsca, p = aktualny
if(v < p.value){ //gdy mamy wartość mniejszą niż na aktualnym węźle
if(p.left == null){ //patrzymy, czy możemy tutaj wstawić (czy nie ma lewego poddrzewa)
p.left = new BSTNode(v); //wstawiamy i kończymy
return;
}
else p = p.left; //idziemy w lewe poddrzewo
}
else{ //analogicznie
if(p.right == null){
p.right = new BSTNode(v);
return;
}
else p = p.right;
}
}
}
void remove(int v){
BSTNode o = null; //ojciec aktualnego (ojcem korzenia jest null)
BSTNode p = root; //aktualny węzeł
while(true){ //szukamy
if(p == null){ //tutaj dojdziemy, gdy nie ma elementu na drzewie
return;
}
if(v < p.value){ //gdy element jest mniejszy - schodzimy w lewe poddrzewo
o = p;
p = p.left;
continue;
}
if(v > p.value){ //gdy element jest większy - schodzimy w prawe poddrzewo
o = p;
p = p.right;
continue;
}
if(p.left == null && p.right == null){ //usuwany element jest liściem - po prostu kasujemy
if(o == null){
root = null; //jeśli element jest korzeniem, ustawiamy nowy korzeń
} else{
if(p.value < o.value)o.left = null; //jeśli element nie jest korzeniem, ustawiamy jego ojca, tak aby wskazywał na odpowiedni element
else o.right = null;
}
return;
}
if(p.left != null && p.right == null){ //element ma jednego syna (lewego)
if(o == null){
root = p.left; //jeśli element jest korzeniem, ustawiamy nowy korzeń
} else{
if(p.value < o.value)o.left = p.left; //jeśli element nie jest korzeniem, ustawiamy jego ojca, tak aby wskazywał na odpowiedni element
else o.right = p.left;
}
return;
}
if(p.left == null && p.right != null){
if(o == null){
root = p.right; //jeśli element jest korzeniem, ustawiamy nowy korzeń
} else{
if(p.value < o.value)o.left = p.right; //jeśli element nie jest korzeniem, ustawiamy jego ojca, tak aby wskazywał na odpowiedni element
else o.right = p.right;
}
return;
}
if(p.left != null && p.right != null){ //element na dwóch synów
BSTNode q = p.right; //znajdujemy element q do zamiany
while(q.left != null)q=q.left; //jest to najmniejszy element z prawego poddrzewa
int x = q.value; //zapamiętujemy wartość elementu do zamiany
this.remove(x); //kasujemy ten element
p.value = x; //wstawiamy tą wartość w miejsce elementu p
return;
}
}
}
BSTNode min(){
if(root==null)return null; //gdy drzewo jest puste
BSTNode p = root; //ustawiamy p na korzeń
while(p.left != null){ //dopóki istnieje lewy syn
p = p.left; //ustawiamy p na lewego syna
}
return p; //minimalna wartość
}
void wypisz(BSTNode p,int r){ //funkcja pomocnicza - rysuje nam drzewo
if(p != null){
this.wypisz(p.left,r+1);
for(int i=0; i<r; i++){
System.out.print(" ");
}
System.out.println(p.value);
this.wypisz(p.right,r+1);
}
}
}
public class Main {
public static void main(String[] args)
{
BSTTree b = new BSTTree();
Scanner in = new Scanner(System.in);
int x,y;
while(true){
x = in.nextInt();
y = in.nextInt();
if(x==1)b.add(y);
if(x==2)b.remove(y);
if(x==3)b.wypisz(b.root,0);
if(x==4)break;
}
}
}
prosze o pomoc.