Untitled

 avatar
unknown
plain_text
3 years ago
11 kB
3
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...