Mam za zadanie na studiach, napisanie kodu huffmana już najbliższą niedzielę. Kod ma przyjmować jakiś string , zliczyć ilość wystąpień, stworzyć drzewo, zakodować i przesłać strumieniowo do pliku bin. 1,2 i 4 to raczej nie problem.
Problem mam z drzewem. Javie nie ma wskażników* (Oficjalnie ich nie ma, ale można je zaimplementować, aczkolwiek są nie zalecane , tymbardziej pewnie byłby problem z zastrzeżoną pamięcią cóż tak zakładam).
Więc stworzyłem sobie obiekt Node który przechowuje wskażnik na rodzica i na swoje dzieci.
public class Node {
private int pointerToParent;
private int pointerToLeftChildren;
private int pointerToRightChildren;
private boolean iHaveLeftSon = false;
private boolean iHaveRightSon = false;
private int numberNode;
numberNode jest tylko wskażnikiem na indeks węzła, owszem obiekty są pakowane do listy, ale nie poruszam się po niej jak po liście jest tylko pojemnikiem braku laku innego wyboru.
No to wsadzam sobie węzeł.
if (quequeTree.isEmptyRoot()){
quequeTree.setRoot(asciChar);
}
Pierw co sprawdzam, czy moim drzewie jest korzeń jeżeli nie ma wstaw korzeń.
public void setRoot(AsciChar asciChar) {
System.out.println("Wstawiam korzeń");
Node node = new Node();
node.setAsciChar(asciChar);
node.setNumberNode(numberNode);
tree.add(node);
isEmptyRoot = false;
pointerToRoot = node;
increase();
}
Tworzę węzeł, wstawiam wartość i dodaje do drzewa i zwiększam licznik, zaznaczam, że korzeń istnieje. Dlaczego używam twierdzenia booleańskiego, cóż JAVA bardzo nie lubi null.
Mam już korzeń, leci kolejna iteracja.
if (asciChar.getCounter() <= quequeTree.getParentValue() ){
System.out.println("Sprawdzam wartości");
System.out.println("Czy wartość rodzica: " + quequeTree.getParentValue() + "jest większa od elementu wstawianego " + asciChar.getCounter() );
if(!quequeTree.isLeftSonExist()){
System.out.println("Nie mam lewego syna");
quequeTree.setLeftSon(asciChar);
}
Sprawdzam, czy wartość lewego nowego elementu jest mniejsza od elementu na którego pointer wskazuje(węzeł) , jeżeli tak sprawdzam czy istnieje lewy syn, jeżeli nie wstawiam lewego syna.
public void setLeftSon(AsciChar asciChar) {
Node node = new Node();
node.setAsciChar(asciChar);
node.setPointerToParent(pointerToRoot.getPointerToParent());
System.out.println("Lewy syn ma ojca " + node.getPointerToParent());
tree.get(pointerToRoot.getNumberNode()).setiHaveLeftSon(true);
tree.get(pointerToRoot.getNumberNode()).setPointerToLeftChildren(numberNode);
pointerToRoot.setiHaveLeftSon(true);
pointerToRoot.setPointerToLeftChildren(pointerToRoot.getNumberNode()+1);
System.out.println("Ojciec ma lewgo syna o indeksie: " + pointerToRoot.getPointerToLeftChildren() );
System.out.println("Wstawiam lewego syna");
tree.add(node);
increase();
}
Następnie tworzę relacje, między synem a ojcem ustawiajać wskażniki.
Jednakże, jeżeli syna priorytet(wartość) jest mniejsza od ojca i lewy syn istnieje, wskaż, że rootem jest teraz lewe dziecko na które wskazuje pointerToRoot.
else{
quequeTree.setParentToLeftNode(i);
}
public void setParentToLeftNode(int i ) {
pointerToParentNode = i;
}
I tu mi się trochę mój pomysł się sypie. Bo owszem wskazałem na co ma wskazać, ale węzła nie wstawiłem, myślę, że najsensowniejszym rozwiązaniem to prostu wywołować jeszcze raz rekurencję. Ale tu już rośnie złożoność obliczeniowa.Macie jakieś pomysły?
Potem buduje prawą gałązkę.
else {
if (!quequeTree.isRightSonExist()){
quequeTree.setRightSon(asciChar);
}
else{
quequeTree.setParentToRightNode(i);
}
System.out.println(quequeTree.getParentValue());
}
Teoretycznie, przedstawię za pomocą case:
1. Wsadzam 12.
2.Mam root.
3.Wsadzam 4.
4.Mam lewego syna.
5.Wsadzam 25.
6. Mam prawego syna.
7.Wsadzam 6
8. Istnieje lewy syn
9.Wskazuje na lewego syna.
10.REKURENCJA: Wsadzam ponownie 6.
11.Mam prawego syna.
12.Wsadzam 26
13.Jest większy od wartości rodzica sprawdzam czy prawy istnieje.
14.istnieje
15.buduje kolejny korzeń.
I tu się algorytm sypnie się, gdyż drzewo nie będzie miało odpowiednią ilość liści(cóż tak mi się wydaje)
Za wszelką pomoc z góry dziękuje :)
PS: Wiem, że jest BSTree oraz priorityQueque w JAVA. Ale nie o to chodzi w tym zadaniu.