Linia 1. public class Main otwórz nawias klamrowy. Linia 3. public static int otwórz nawias kwadratowy zamknij nawias kwadratowy zlicz otwórz nawias okrągły String wiadomosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca średnik. Linia 5. char min znak równości Character kropka MAX podkreślnik VALUE średnik. Linia 6. char max znak równości Character kropka MIN podkreślnik VALUE średnik. Linia 7. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły min zamknij nawias ostrokątny wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły. Linia 9. min znak równości wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 10. if otwórz nawias okrągły max otwórz nawias ostrokątny wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły. Linia 11. max znak równości wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 12. zamknij nawias klamrowy. Linia 13. tabZliczajaca znak równości new int otwórz nawias kwadratowy max minus min plus 1 zamknij nawias kwadratowy średnik. Linia 14. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. tabZliczajaca otwórz nawias kwadratowy wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły minus min zamknij nawias kwadratowy plus plus średnik. Linia 16. zamknij nawias klamrowy. Linia 17. return tabZliczajaca średnik. Linia 18. zamknij nawias klamrowy. Linia 20. public static Wierzcholek sortowanie otwórz nawias okrągły Wierzcholek otwórz nawias kwadratowy zamknij nawias kwadratowy listaWierzcholkow przecinek int dlugoscListy zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. int j znak równości dlugoscListy średnik. Linia 23. do otwórz nawias klamrowy. Linia 24. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny j minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 25. if otwórz nawias okrągły listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka czestosc otwórz nawias ostrokątny listaWierzcholkow otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy kropka czestosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. Wierzcholek temp znak równości listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 27. listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości listaWierzcholkow otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy średnik. Linia 28. listaWierzcholkow otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy znak równości temp średnik. Linia 29. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy. Linia 31. j minus minus średnik. Linia 32. zamknij nawias klamrowy while otwórz nawias okrągły j zamknij nawias ostrokątny 1 zamknij nawias okrągły średnik. Linia 34. int k znak równości dlugoscListy średnik. Linia 35. while otwórz nawias okrągły k zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. prawy ukośnik prawy ukośnik wierzchołki o najmniejszej częstości znajdują się na końcu listy. Linia 37. Wierzcholek pierwszyDoUsuniecia znak równości listaWierzcholkow otwórz nawias kwadratowy k minus 1 zamknij nawias kwadratowy średnik. Linia 38. Wierzcholek drugiDoUsuniecia znak równości listaWierzcholkow otwórz nawias kwadratowy k minus 2 zamknij nawias kwadratowy średnik. Linia 39. Wierzcholek nowyWierzcholek znak równości new Wierzcholek otwórz nawias okrągły apostrof lewy ukośnik 0 apostrof przecinek. Linia 40. pierwszyDoUsuniecia kropka czestosc plus drugiDoUsuniecia kropka czestosc przecinek pierwszyDoUsuniecia przecinek drugiDoUsuniecia zamknij nawias okrągły średnik. Linia 41. listaWierzcholkow otwórz nawias kwadratowy k minus 2 zamknij nawias kwadratowy znak równości nowyWierzcholek średnik. Linia 42. listaWierzcholkow otwórz nawias kwadratowy k minus 1 zamknij nawias kwadratowy znak równości null średnik. Linia 43. k minus minus średnik. Linia 44. prawy ukośnik prawy ukośnik umieść nowy wierzchołek w odpowiednim miejscu. Linia 45. for otwórz nawias okrągły int i znak równości k minus 1 średnik i zamknij nawias ostrokątny 0 średnik i minus minus zamknij nawias okrągły otwórz nawias klamrowy. Linia 46. if otwórz nawias okrągły listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy znak równości znak równości null. Linia 47. kreska pionowa kreska pionowa listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka czestosc zamknij nawias ostrokątny listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy kropka czestosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 48. Wierzcholek temp znak równości listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 49. listaWierzcholkow otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy średnik. Linia 50. listaWierzcholkow otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy znak równości temp średnik. Linia 51. zamknij nawias klamrowy else break średnik. Linia 52. zamknij nawias klamrowy. Linia 53. zamknij nawias klamrowy. Linia 54. return listaWierzcholkow otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 55. zamknij nawias klamrowy. Linia 57. static int obecnyElementTablicySlow znak równości 0 średnik. Linia 59. private static Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy zapiszKod otwórz nawias okrągły Wierzcholek doPrzeszukania przecinek String dotychczasowyKod przecinek Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy listaSlow zamknij nawias okrągły otwórz nawias klamrowy. Linia 60. if otwórz nawias okrągły doPrzeszukania kropka lewy znak równości znak równości null ampersant ampersant doPrzeszukania kropka prawy znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 61. listaSlow otwórz nawias kwadratowy obecnyElementTablicySlow zamknij nawias kwadratowy znak równości new Slowo otwórz nawias okrągły doPrzeszukania kropka znak przecinek doPrzeszukania kropka czestosc przecinek. Linia 62. dotychczasowyKod zamknij nawias okrągły średnik. Linia 63. obecnyElementTablicySlow plus plus średnik. Linia 64. zamknij nawias klamrowy. Linia 65. if otwórz nawias okrągły doPrzeszukania kropka lewy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 66. zapiszKod otwórz nawias okrągły doPrzeszukania kropka lewy przecinek dotychczasowyKod plus cudzysłów 0 cudzysłów przecinek listaSlow zamknij nawias okrągły średnik. Linia 67. zamknij nawias klamrowy. Linia 68. if otwórz nawias okrągły doPrzeszukania kropka prawy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 69. zapiszKod otwórz nawias okrągły doPrzeszukania kropka prawy przecinek dotychczasowyKod plus cudzysłów 1 cudzysłów przecinek listaSlow zamknij nawias okrągły średnik. Linia 70. zamknij nawias klamrowy. Linia 71. return listaSlow średnik. Linia 72. zamknij nawias klamrowy. Linia 74. static String zakodujZnak otwórz nawias okrągły char znak przecinek Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazkaSlow zamknij nawias okrągły otwórz nawias klamrowy. Linia 75. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny ksiazkaSlow kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 76. if otwórz nawias okrągły ksiazkaSlow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka znak znak równości znak równości znak zamknij nawias okrągły. Linia 77. return ksiazkaSlow otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka slowoKodowe średnik. Linia 78. zamknij nawias klamrowy. Linia 79. return cudzysłów cudzysłów średnik prawy ukośnik prawy ukośnik jeśli korzystamy z odpowiedniej funkcji kodowej przecinek ta instrukcja się nie wykona. Linia 80. zamknij nawias klamrowy. Linia 82. static String zakodujWiadomosc otwórz nawias okrągły String wiadomosc przecinek Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazkaSlow zamknij nawias okrągły otwórz nawias klamrowy. Linia 83. String zakodowanaWiadomosc znak równości cudzysłów cudzysłów średnik. Linia 84. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 85. zakodowanaWiadomosc plus znak równości zakodujZnak otwórz nawias okrągły wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły przecinek ksiazkaSlow zamknij nawias okrągły średnik. Linia 86. zamknij nawias klamrowy. Linia 87. return zakodowanaWiadomosc średnik. Linia 88. zamknij nawias klamrowy. Linia 90. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 91. String wiadomosc znak równości cudzysłów Jestem tekstem testowym cudzysłów średnik. Linia 92. int otwórz nawias kwadratowy zamknij nawias kwadratowy tabZliczajaca znak równości zlicz otwórz nawias okrągły wiadomosc zamknij nawias okrągły średnik. Linia 93. char minZnak znak równości Character kropka MAX podkreślnik VALUE średnik. Linia 94. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wiadomosc kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 95. if otwórz nawias okrągły minZnak zamknij nawias ostrokątny wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły. Linia 96. minZnak znak równości wiadomosc kropka charAt otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 97. zamknij nawias klamrowy. Linia 98. Wierzcholek otwórz nawias kwadratowy zamknij nawias kwadratowy listaWierzcholkow znak równości new Wierzcholek otwórz nawias kwadratowy tabZliczajaca kropka length zamknij nawias kwadratowy średnik. Linia 99. int dlugoscListy znak równości 0 średnik. Linia 100. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny listaWierzcholkow kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 101. if otwórz nawias okrągły tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 102. listaWierzcholkow otwórz nawias kwadratowy dlugoscListy zamknij nawias kwadratowy znak równości new Wierzcholek otwórz nawias okrągły otwórz nawias okrągły char zamknij nawias okrągły otwórz nawias okrągły i plus minZnak zamknij nawias okrągły przecinek tabZliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek null przecinek null zamknij nawias okrągły średnik. Linia 103. dlugoscListy plus plus średnik. Linia 104. zamknij nawias klamrowy. Linia 105. zamknij nawias klamrowy. Linia 106. Wierzcholek korzen znak równości sortowanie otwórz nawias okrągły listaWierzcholkow przecinek dlugoscListy zamknij nawias okrągły średnik. Linia 107. prawy ukośnik prawy ukośnik w przypadku gdy w tekście znajduje się tylko jeden unikalny znak musimy. Linia 108. prawy ukośnik prawy ukośnik obsłużyć ten wyjątek przecinek ponieważ drzewo się nie zbuduje. Linia 109. if otwórz nawias okrągły dlugoscListy znak równości znak równości 1 zamknij nawias okrągły. Linia 110. korzen znak równości new Wierzcholek otwórz nawias okrągły apostrof lewy ukośnik 0 apostrof przecinek 1 przecinek null przecinek listaWierzcholkow otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 111. Slowo otwórz nawias kwadratowy zamknij nawias kwadratowy ksiazkaSlow znak równości new Slowo otwórz nawias kwadratowy dlugoscListy zamknij nawias kwadratowy średnik. Linia 112. ksiazkaSlow znak równości zapiszKod otwórz nawias okrągły korzen przecinek cudzysłów cudzysłów przecinek ksiazkaSlow zamknij nawias okrągły średnik. Linia 113. String wiadomoscZakodowana znak równości zakodujWiadomosc otwórz nawias okrągły wiadomosc przecinek ksiazkaSlow zamknij nawias okrągły średnik. Linia 114. System kropka out kropka println otwórz nawias okrągły wiadomoscZakodowana zamknij nawias okrągły średnik. Linia 115. zamknij nawias klamrowy. Linia 116. zamknij nawias klamrowy. Linia 118. class Wierzcholek otwórz nawias klamrowy. Linia 119. char znak średnik. Linia 120. int czestosc średnik. Linia 121. Wierzcholek lewy znak równości null średnik. Linia 122. Wierzcholek prawy znak równości null średnik. Linia 124. Wierzcholek otwórz nawias okrągły char znak przecinek int czestosc przecinek Wierzcholek lewy przecinek Wierzcholek prawy zamknij nawias okrągły otwórz nawias klamrowy. Linia 125. this kropka znak znak równości znak średnik. Linia 126. this kropka czestosc znak równości czestosc średnik. Linia 127. this kropka lewy znak równości lewy średnik. Linia 128. this kropka prawy znak równości prawy średnik. Linia 129. zamknij nawias klamrowy. Linia 130. zamknij nawias klamrowy. Linia 132. class Slowo otwórz nawias klamrowy. Linia 133. char znak średnik. Linia 134. int czestosc średnik. Linia 135. String slowoKodowe średnik. Linia 137. Slowo otwórz nawias okrągły char znak przecinek int czestosc przecinek String slowoKodowe zamknij nawias okrągły otwórz nawias klamrowy. Linia 138. this kropka znak znak równości znak średnik. Linia 139. this kropka czestosc znak równości czestosc średnik. Linia 140. this kropka slowoKodowe znak równości slowoKodowe średnik. Linia 141. zamknij nawias klamrowy. Linia 142. zamknij nawias klamrowy.

public class Main {

	public static int[] zlicz(String wiadomosc) {
		int[] tabZliczajaca;
		char min = Character.MAX_VALUE;
		char max = Character.MIN_VALUE;
		for (int i = 0; i < wiadomosc.length(); i++) {
			if (min > wiadomosc.charAt(i))
				min = wiadomosc.charAt(i);
			if (max < wiadomosc.charAt(i))
				max = wiadomosc.charAt(i);
		}
		tabZliczajaca = new int[max - min + 1];
		for (int i = 0; i < wiadomosc.length(); i++) {
			tabZliczajaca[wiadomosc.charAt(i) - min]++;
		}
		return tabZliczajaca;
	}

	public static Wierzcholek sortowanie(Wierzcholek[] listaWierzcholkow, int dlugoscListy) {

		int j = dlugoscListy;
		do {
			for (int i = 0; i < j - 1; i++) {
				if (listaWierzcholkow[i].czestosc < listaWierzcholkow[i + 1].czestosc) {
					Wierzcholek temp = listaWierzcholkow[i];
					listaWierzcholkow[i] = listaWierzcholkow[i + 1];
					listaWierzcholkow[i + 1] = temp;
				}
			}
			j--;
		} while (j > 1);

		int k = dlugoscListy;
		while (k > 1) {
			// wierzchołki o najmniejszej częstości znajdują się na końcu listy
			Wierzcholek pierwszyDoUsuniecia = listaWierzcholkow[k - 1];
			Wierzcholek drugiDoUsuniecia = listaWierzcholkow[k - 2];
			Wierzcholek nowyWierzcholek = new Wierzcholek('\0',
					pierwszyDoUsuniecia.czestosc + drugiDoUsuniecia.czestosc, pierwszyDoUsuniecia, drugiDoUsuniecia);
			listaWierzcholkow[k - 2] = nowyWierzcholek;
			listaWierzcholkow[k - 1] = null;
			k--;
			// umieść nowy wierzchołek w odpowiednim miejscu
			for (int i = k - 1; i > 0; i--) {
				if (listaWierzcholkow[i - 1] == null
						|| listaWierzcholkow[i].czestosc > listaWierzcholkow[i - 1].czestosc) {
					Wierzcholek temp = listaWierzcholkow[i];
					listaWierzcholkow[i] = listaWierzcholkow[i - 1];
					listaWierzcholkow[i - 1] = temp;
				} else break;
			}
		}
		return listaWierzcholkow[0];
	}

	static int obecnyElementTablicySlow = 0;

	private static Slowo[] zapiszKod(Wierzcholek doPrzeszukania, String dotychczasowyKod, Slowo[] listaSlow) {
		if (doPrzeszukania.lewy == null && doPrzeszukania.prawy == null) {
			listaSlow[obecnyElementTablicySlow] = new Slowo(doPrzeszukania.znak, doPrzeszukania.czestosc,
					dotychczasowyKod);
			obecnyElementTablicySlow++;
		}
		if (doPrzeszukania.lewy != null) {
			zapiszKod(doPrzeszukania.lewy, dotychczasowyKod + "0", listaSlow);
		}
		if (doPrzeszukania.prawy != null) {
			zapiszKod(doPrzeszukania.prawy, dotychczasowyKod + "1", listaSlow);
		}
		return listaSlow;
	}

	static String zakodujZnak(char znak, Slowo[] ksiazkaSlow) {
		for (int i = 0; i < ksiazkaSlow.length; i++) {
			if (ksiazkaSlow[i].znak == znak)
				return ksiazkaSlow[i].slowoKodowe;
		}
		return "";// jeśli korzystamy z odpowiedniej funkcji kodowej, ta instrukcja się nie wykona
	}

	static String zakodujWiadomosc(String wiadomosc, Slowo[] ksiazkaSlow) {
		String zakodowanaWiadomosc = "";
		for (int i = 0; i < wiadomosc.length(); i++) {
			zakodowanaWiadomosc += zakodujZnak(wiadomosc.charAt(i), ksiazkaSlow);
		}
		return zakodowanaWiadomosc;
	}

	public static void main(String[] args) {
		String wiadomosc = "Jestem tekstem testowym";
		int[] tabZliczajaca = zlicz(wiadomosc);
		char minZnak = Character.MAX_VALUE;
		for (int i = 0; i < wiadomosc.length(); i++) {
			if (minZnak > wiadomosc.charAt(i))
				minZnak = wiadomosc.charAt(i);
		}
		Wierzcholek[] listaWierzcholkow = new Wierzcholek[tabZliczajaca.length];
		int dlugoscListy = 0;
		for (int i = 0; i < listaWierzcholkow.length; i++) {
			if (tabZliczajaca[i] != 0) {
				listaWierzcholkow[dlugoscListy] = new Wierzcholek((char) (i + minZnak), tabZliczajaca[i], null, null);
				dlugoscListy++;
			}
		}
		Wierzcholek korzen = sortowanie(listaWierzcholkow, dlugoscListy);
		// w przypadku gdy w tekście znajduje się tylko jeden unikalny znak musimy
		// obsłużyć ten wyjątek, ponieważ drzewo się nie zbuduje
		if (dlugoscListy == 1)
			korzen = new Wierzcholek('\0', 1, null, listaWierzcholkow[0]);
		Slowo[] ksiazkaSlow = new Slowo[dlugoscListy];
		ksiazkaSlow = zapiszKod(korzen, "", ksiazkaSlow);
		String wiadomoscZakodowana = zakodujWiadomosc(wiadomosc, ksiazkaSlow);
		System.out.println(wiadomoscZakodowana);
	}
}

class Wierzcholek {
	char znak;
	int czestosc;
	Wierzcholek lewy = null;
	Wierzcholek prawy = null;

	Wierzcholek(char znak, int czestosc, Wierzcholek lewy, Wierzcholek prawy) {
		this.znak = znak;
		this.czestosc = czestosc;
		this.lewy = lewy;
		this.prawy = prawy;
	}
}

class Slowo {
	char znak;
	int czestosc;
	String slowoKodowe;

	Slowo(char znak, int czestosc, String slowoKodowe) {
		this.znak = znak;
		this.czestosc = czestosc;
		this.slowoKodowe = slowoKodowe;
	}
}