Untitled
unknown
plain_text
4 years ago
11 kB
5
Indexable
public class TreeShahad {
// ===============BT=====================
public static <E> void preOrder(TNode<E> n) { // parent --> left --> right
if (n != null) {
System.out.print(n.getItem() + " ");
preOrder(n.getLeft()); // يستدعي نفسه ريكرجن لين يخلص كل اللي باللفت بعدين ينتقل للرايت
preOrder(n.getRight());
}
}
// ================================================
public static <E> void inOrder(TNode<E> n) { // left --> parent --> right
if (n != null) {
preOrder(n.getLeft());
System.out.print(n.getItem() + " ");
preOrder(n.getRight());
}
}
// ================================================
public static <E> void postOrder(TNode<E> n) { // left --> right --> parent
if (n != null) {
preOrder(n.getLeft());
preOrder(n.getRight());
System.out.print(n.getItem() + " ");
}
}
// ================================================
public static <E> void printSingls(TNode<E> n) { // تطبع العناصر اللي ماله اطفال
if (n == null) // base condition
return;
if (n.getLeft() != null && n.getRight() != null) {
printSingls(n.getLeft()); // بيمشي لفت كل شوي عشان كذا نحط ريكرجن
printSingls(n.getRight());
} else if (n.getRight() != null) {
System.out.print(n.getRight().getItem() + " ");
printSingls(n.getRight());
} else if (n.getLeft() != null) {
System.out.print(n.getLeft().getItem() + " ");
printSingls(n.getLeft());
}
}
// ================================================
public static <E extends Comparable<E>> int occurrence(E v, TNode<E> n) { // ميثود تشوف كم عدد مرات التكرار للرقم
// اللي ارسلناه
if (n == null) // base condition
return 0;
else if (n.getItem().compareTo(v) == 0)
return occurrence(v, n.getLeft()) + occurrence(v, n.getRight()) + 1;
else
return occurrence(v, n.getLeft()) + occurrence(v, n.getRight());
}
// ================================================
public static boolean search(TNode rt, Integer k) {
if (rt != null) {
if (rt.getItem() == k) {
return true;
}
return search(rt.getLeft(), k) || search(rt.getRight(), k);
}
return false;
}
// ================================================
public static <E> int sum(TNode<E> n) { // ميثود تجمع
if (n == null)
return 0;
else
return ((int) n.getItem() + sum(n.getLeft()) + sum(n.getRight())); // لازم الميثود تستدعي نفسها عشان تجمع
}
// ================================================
public static int findMax(TNode node) {
if (node == null)
return 0;
int max = (int) node.getItem();
int LMax = findMax(node.getLeft());
int RMax = findMax(node.getRight());
if (LMax > max)
max = LMax;
if (RMax > max)
max = RMax;
return max;
}
// ================================================
public static int findMin(TNode node) {
if (node == null)
return 0;
int min = (int) node.getItem();
int LMin = findMax(node.getLeft());
int RMin = findMax(node.getRight());
if (LMin < min)
min = LMin;
if (RMin < min)
min = RMin;
return min;
}
public static int Even(TNode node) { // تجيب العدد الزوجي
if (node == null)
return 0;
if ((int) node.getItem() % 2 == 0)
return 1 + Even(node.getLeft()) + Even(node.getRight());
else
return Even(node.getLeft()) + Even(node.getRight());
}
// ==================BST==========================
public static <Key, T> void preOrder(BSTNode<Key, T> n) { // parent --> left --> right
if (n != null) {
System.out.print(n.getData() + " ");
preOrder(n.getLeft()); // يستدعي نفسه ريكرجن لين يخلص كل اللي باللفت بعدين ينتقل للرايت
preOrder(n.getRight());
}
}
// ================================================
public static <Key, T> void inOrder(BSTNode<Key, T> n) { // left --> parent --> right
if (n != null) {
inOrder(n.getLeft());
System.out.print(n.getData() + " ");
inOrder(n.getRight());
}
}
// ================================================
public static <Key, T> void postOrder(BSTNode<Key, T> n) { // left --> right --> parent
if (n != null) {
postOrder(n.getLeft());
postOrder(n.getRight());
System.out.print(n.getData() + " ");
}
}
public static <K extends Comparable<K>, T> boolean isBST(BSTNode<K, T> node, BSTNode<K, T> l, BSTNode<K, T> r) {
if (node == null)
return true;
if (l != null && node.getKey().compareTo(l.getKey()) <= 0)
return false;
if (r != null && node.getKey().compareTo(r.getKey()) >= 0)
return false;
return isBST(node.getLeft(), l, node) && isBST(node.getRight(), node, r);
}
// ================================================
public static <Key, T> int findMax(BSTNode<Key, T> node) { // الاكبر
if (node == null)
return 0;
int max = (int) node.getData();
int LMax = findMax(node.getLeft());
int RMax = findMax(node.getRight());
if (LMax > max)
max = LMax;
if (RMax > max)
max = RMax;
return max;
}
// ================================================
public static <Key, T> int findMin(BSTNode<Key, T> node) { // الاصغر
if (node == null)
return 0;
int min = (int) node.getData();
int LMin = findMax(node.getLeft());
int RMin = findMax(node.getRight());
if (LMin < min)
min = LMin;
if (RMin < min)
min = RMin;
return min;
}
public static <Key, T> int sum(BSTNode<Key, T> node) { // ميثود تجمع
if (node == null)
return 0;
else
return ((int) node.getData() + sum(node.getLeft()) + sum(node.getRight())); // لازم الميثود تستدعي نفسها
// عشان تجمع
}
public static void main(String[] args) {
// ==========BTree=========
TNode<Integer> root = new TNode<>();
TNode<Integer> l1 = new TNode<>();
TNode<Integer> l2 = new TNode<>();
TNode<Integer> l3 = new TNode<>();
TNode<Integer> l4 = new TNode<>();
TNode<Integer> r1 = new TNode<>();
TNode<Integer> r2 = new TNode<>();
TNode<Integer> r3 = new TNode<>();
root.setItem(0);
l1.setItem(1);
l2.setItem(3);
l3.setItem(4);
l4.setItem(6);
r1.setItem(3);
r2.setItem(5);
r3.setItem(7);
root.setLeft(l1);
root.setRight(r1);
l1.setLeft(l2);
l1.setRight(l3);
l2.setRight(l4);
r1.setLeft(r2);
r2.setRight(r3);
// ==========تيست على الترافيرسال==============
System.out.println("===BT===");
System.out.println("preOrder : ");
preOrder(root);
System.out.println("\n\ninOrder : ");
inOrder(root);
System.out.println("\n\npostOrder : ");
postOrder(root);
// ===============ميثود مهمه للاختبار==============
System.out.println("\n\nsum is = " + sum(root));
System.out.println("\noccurrence 3 = " + occurrence(3, root));
System.out.println("Max is : " + findMax(root));
System.out.println("Mini is : " + findMin(root));
System.out.println("is found? " + search(root, 3));
// ===========BST============
/*
* BSTNode<Integer, Integer> root1 = new BSTNode<Integer, Integer>();
* BSTNode<Integer, Integer> l1 = new BSTNode<Integer, Integer>();
* BSTNode<Integer, Integer> l2 = new BSTNode<Integer, Integer>();
* BSTNode<Integer, Integer> l3 = new BSTNode<Integer, Integer>();
* BSTNode<Integer, Integer> l4 = new BSTNode<Integer, Integer>();
* BSTNode<Integer, Integer> r1 = new BSTNode<Integer, Integer>();
* BSTNode<Integer, Integer> r2 = new BSTNode<Integer, Integer>();
* BSTNode<Integer, Integer> r3 = new BSTNode<Integer, Integer>();
* root1.setData(0);
* l1.setData(1);
* l2.setData(3);
* l3.setData(4);
* l4.setData(6);
*
* r1.setData(3);
* r2.setData(5);
* r3.setData(7);
* root1.setLeft(l1);
* root1.setRight(r1);
*
* l1.setLeft(l2);
* l1.setRight(l3);
*
* l2.setRight(l4);
*
* r1.setLeft(r2);
* r2.setRight(r3);
*/
System.out.println("===BST===");
BSTree<Integer, Integer> bst = new BSTree<Integer, Integer>();
bst.insert(23, 1);
bst.insert(18, 2);
bst.insert(44, 3);
bst.insert(12, 4);
bst.insert(35, 5);
bst.insert(52, 6);
bst.insert(20, 7);
System.out.println("\nprint bst : ");
bst.print(bst.Getroot());
System.out.println("\npreOrder : ");
preOrder(bst.Getroot());
System.out.println("\ninOrder : ");
inOrder(bst.Getroot());
System.out.println("\npostOrder : ");
postOrder(bst.Getroot());
System.out.println("\nMax is : " + findMax(bst.Getroot()));
System.out.println("\nMin is : " + findMin(bst.Getroot()));
System.out.println("\nsum is : " + sum(bst.Getroot()));
System.out.println("\nisBST = " + isBST(bst.Getroot(), null, null));
}
}
Editor is loading...