Laboratoriya ishi-6

Binar daraxt balandligi
Binar daraxtning balandligi deb daraxt bosqichlari soniga aytiladi. Binar daraxt balandligini aniqlash uchun uning har bir tuguni chap va o’ng qismdaraxtlari balandliklari solishtiriladi va maksimal qiymat balandlik deb olinadi. Misol uchun quyidagi 4.9-rasmdagi daraxtning balandligi 2 ga teng.

5.9-rasm. Binar daraxt balandligi

3-misol
import java.util.LinkedList;

public class Main {

static class BinaryTreeextends Comparable>{
private T data;
private BinaryTree left, right;

public void add(T item){
if (data == null) {
data = item;
left = new BinaryTree<>();
right = new BinaryTree<>();
} else if (data.compareTo(item) > 0){
left.add(item);
} else if (data.compareTo(item) < 0){
right.add(item);
}
}

public void addAll(T ... items){
for(T item : items)
add(item);
}

public boolean contains(T item){
if (data == null) return false;
if (data.compareTo(item) == 0) return true;
if (data.compareTo(item) > 0) return left.contains(item);
return right.contains(item);
}

public boolean isEmpty(){ return data == null; }

T mostLeft(){

if (!left.isEmpty()) return left.mostLeft();
return data;
}

T mostRight(){

if (!right.isEmpty()) return right.mostRight();
return data;
}

public void remove(T item){
if (isEmpty()) return;
if (data.compareTo(item) == 0){
if (left.isEmpty() && right.isEmpty()) clear();
else if (!left.isEmpty()){
T temp = left.mostRight();
remove(temp);
data = temp;
} else {
T temp = right.mostLeft();
remove(temp);
data = temp;
}
} else if (data.compareTo(item) > 0){
if (!left.isEmpty()) left.remove(item);
} else {
if (!right.isEmpty()) right.remove(item);
}
}

public void clear(){
data = null;
left = null;
right = null;
}

public String inOrder(){
if (isEmpty()) return "";
String sl = left.inOrder();
String sr = right.inOrder();
return (sl.isEmpty() ? "" : sl+" ")+data.toString()+(sr.isEmpty() ? "" : " "+sr);
}

public LinkedList inOrderList(){
LinkedList list = new LinkedList<>();
if (isEmpty()) return list;
LinkedList leftList = left.inOrderList();
LinkedList rightList = right.inOrderList();

list.addAll(leftList);

list.add(data);
list.addAll(rightList);

return list;
}

public String preOrder(){
if (isEmpty()) return "";
String sl = left.preOrder();
String sr = right.preOrder();
return data.toString()+(sl.isEmpty() ? "" : " "+sl)+(sr.isEmpty() ? "" : " "+sr);
}

public LinkedList preOrderList(){
LinkedList list = new LinkedList<>();
if (isEmpty()) return list;
LinkedList leftList = left.preOrderList();
LinkedList rightList = right.preOrderList();

list.add(data);

list.addAll(leftList);
list.addAll(rightList);

return list;
}

public String postOrder(){
if (isEmpty()) return "";
String sl = left.postOrder();
String sr = right.postOrder();
return (sl.isEmpty() ? "" : sl+" ")+(sr.isEmpty() ? "" : sr+" ")+data.toString();
}

public LinkedList postOrderList(){
LinkedList list = new LinkedList<>();
if (isEmpty()) return list;
LinkedList leftList = left.preOrderList();
LinkedList rightList = right.preOrderList();

list.addAll(leftList);

list.addAll(rightList);
list.add(data);

return list;
}

public LinkedList leafList(){
LinkedList leaf = new LinkedList<>();

if (data == null) return leaf;
LinkedList leftLeaf = left.leafList();
LinkedList rightLeaf = right.leafList();

if (leftLeaf.isEmpty() && rightLeaf.isEmpty()) leaf.add(data);
if (!leftLeaf.isEmpty()) leaf.addAll(leftLeaf);
if (!rightLeaf.isEmpty()) leaf.addAll(rightLeaf);

return leaf;
}

public int distanceTo(T item){
if (isEmpty()) return -1;
if (data.compareTo(item) == 0) return 0;
if (data.compareTo(item) > 0) {
int t = left.distanceTo(item);
if (t == -1) return -1;
return t+1;
} else {
int t = right.distanceTo(item);
if (t == -1) return -1;
return t + 1;
}
}
}


public static void main(String[] args) {
BinaryTree bt = new BinaryTree<>();

bt.addAll(18, 9, 4, 6, 3, 5, 7, 23, 20, 19, 22, 21, 28, 25, 26, 24);

LinkedList leaf = bt.leafList();

System.out.println("Binar daraxtning barglari :");

for(Integer item : leaf){
System.out.print(item+" ");
}
}
}

15-misol
import java.util.LinkedList;

public class Main {


static class BinaryTreeextends Comparable>{
private T data;
private BinaryTree left, right;

public void add(T item){
if (data == null) {
data = item;
left = new BinaryTree<>();
right = new BinaryTree<>();
} else if (data.compareTo(item) > 0){
left.add(item);
} else if (data.compareTo(item) < 0){
right.add(item);
}
}

public void addAll(T ... items){
for(T item : items)
add(item);
}

public boolean contains(T item){
if (data == null) return false;
if (data.compareTo(item) == 0) return true;
if (data.compareTo(item) > 0) return left.contains(item);
return right.contains(item);
}

public boolean isEmpty(){ return data == null; }

T mostLeft(){

if (!left.isEmpty()) return left.mostLeft();
return data;
}

T mostRight(){

if (!right.isEmpty()) return right.mostRight();
return data;
}

public void remove(T item){
if (isEmpty()) return;
if (data.compareTo(item) == 0){
if (left.isEmpty() && right.isEmpty()) clear();
else if (!left.isEmpty()){
T temp = left.mostRight();
remove(temp);
data = temp;
} else {
T temp = right.mostLeft();
remove(temp);
data = temp;
}
} else if (data.compareTo(item) > 0){
if (!left.isEmpty()) left.remove(item);
} else {
if (!right.isEmpty()) right.remove(item);
}
}

public void clear(){
data = null;
left = null;
right = null;
}

public String inOrder(){
if (isEmpty()) return "";
String sl = left.inOrder();
String sr = right.inOrder();
return (sl.isEmpty() ? "" : sl+" ")+data.toString()+(sr.isEmpty() ? "" : " "+sr);
}

public LinkedList inOrderList(){
LinkedList list = new LinkedList<>();
if (isEmpty()) return list;
LinkedList leftList = left.inOrderList();
LinkedList rightList = right.inOrderList();

list.addAll(leftList);

list.add(data);
list.addAll(rightList);

return list;
}

public String preOrder(){
if (isEmpty()) return "";
String sl = left.preOrder();
String sr = right.preOrder();
return data.toString()+(sl.isEmpty() ? "" : " "+sl)+(sr.isEmpty() ? "" : " "+sr);
}

public LinkedList preOrderList(){
LinkedList list = new LinkedList<>();
if (isEmpty()) return list;
LinkedList leftList = left.preOrderList();
LinkedList rightList = right.preOrderList();

list.add(data);

list.addAll(leftList);
list.addAll(rightList);

return list;
}

public String postOrder(){
if (isEmpty()) return "";
String sl = left.postOrder();
String sr = right.postOrder();
return (sl.isEmpty() ? "" : sl+" ")+(sr.isEmpty() ? "" : sr+" ")+data.toString();
}

public LinkedList postOrderList(){
LinkedList list = new LinkedList<>();
if (isEmpty()) return list;
LinkedList leftList = left.preOrderList();
LinkedList rightList = right.preOrderList();

list.addAll(leftList);

list.addAll(rightList);
list.add(data);

return list;
}

public LinkedList leafList(){
LinkedList leaf = new LinkedList<>();

if (data == null) return leaf;
LinkedList leftLeaf = left.leafList();
LinkedList rightLeaf = right.leafList();

if (leftLeaf.isEmpty() && rightLeaf.isEmpty()) leaf.add(data);
if (!leftLeaf.isEmpty()) leaf.addAll(leftLeaf);
if (!rightLeaf.isEmpty()) leaf.addAll(rightLeaf);

return leaf;
}

public int distanceTo(T item){
if (isEmpty()) return -1;
if (data.compareTo(item) == 0) return 0;
if (data.compareTo(item) > 0) {
int t = left.distanceTo(item);
if (t == -1) return -1;
return t+1;
} else {
int t = right.distanceTo(item);
if (t == -1) return -1;
return t + 1;
}
}
}


public static void main(String[] args) {
BinaryTree bt = new BinaryTree<>();

bt.addAll(18, 9, 4, 6, 3, 5, 7, 23, 20, 19, 22, 21, 28, 25, 26, 24);

// ildiz birinchi kelishi uchun preOrder uslida chiqaramiz
LinkedList list = bt.preOrderList();

BinaryTree evens = new BinaryTree<>();

for (Integer item : list) {
if (item % 2 == 0) evens.add(item);
}

System.out.println("Boshlang'ich daraxt (inorder) : ");

System.out.println(bt.inOrder()+"\n");
System.out.println("Juft elementlardan tuzilgan daraxt (inorder) : ");
System.out.println(evens.inOrder());
}
}

17-misol
import java.util.LinkedList;

public class Main {

static class BinaryTreeextends Comparable>{
private T data;
private BinaryTree left, right;

public void add(T item){
if (data == null) {
data = item;
left = new BinaryTree<>();
right = new BinaryTree<>();
} else if (data.compareTo(item) > 0){
left.add(item);
} else if (data.compareTo(item) < 0){
right.add(item);
}
}

public void addAll(T ... items){
for(T item : items)
add(item);
}

public boolean contains(T item){
if (data == null) return false;
if (data.compareTo(item) == 0) return true;
if (data.compareTo(item) > 0) return left.contains(item);