Tree üçün BFS və DFS

BFS (Breadth-First Search) və DFS (Depth-First Search) bir tree-ni gəzmək üçün və ya bir tree-də axtarış etmək üçün istifadə olunan bir texnikadı. BFS və DFS-i həmçinin graphlarada tətbiq etmək mümkündür. Bu yazımızda biz tree-ni necə gəzə bilərik ona nəzər yetirəcik.

İlk olaraq DFS-dən başlayaq. DFS-in, 3 növ ağacı gəzmək metodu vardır. Bunları sıralasaq,

• In-Order

• Pre-Order

• Post-Order

In-Order metodunda, biz, ilk olaraq sol noda, sonra sağ noda və sonra isə root noda gedirik.

static void traverseInOrder(Node root) {
    if (root == null) return;

    traverseInOrder(root.getLeftNode());
    System.out.print(root.getData() + " ");
    traverseInOrder(root.getRightNode());
}

8 6 9 5 10 7 12 11 13 

Pre-Order metodunda, biz, başlıyırıq root noddan, sonra gedirik sol noda və sonra gedirik sağ noda.

static void traversePreOrder(Node root) {
     if (root == null) return;

     System.out.print(root.getData() + " ");
     traversePreOrder(root.getLeftNode());
     traversePreOrder(root.getRightNode());
}

5 6 8 9 7 10 11 12 13 

Son olaraq, Post-Order metodunda isə, sol noddan başlıyırıq, sonra gedirik sağ noda və sonra isə root noda gedirik.

static void traversePostOrder(Node root) {
    if (root == null) return;

    traversePostOrder(root.getLeftNode());
    traversePostOrder(root.getRightNode());
    System.out.print(root.getData() + " ");
}

8 9 6 10 12 13 11 7 5 

İndi isə keçək BFS-ə. BFS, Level-Order metodu istifadə olunur. Yəni, root nodu ziyarət etdikdən sonra keçirik onun alt nodlarına (child nodes). Və burada biz Queue data strukturundan istifadə edirik. Alqoritmi addım-addım izah etsək belə bir şey çıxar ortaya:

1. Boş bir queue yaradırıq

2. İlk olaraq root nodu queue-ə əlavə edirik.

3. Queue boş olana qədər döngünü işlədirik

   1. Nodu print edirik

   2. Nodumuzun alt sol nodu varsa queue-ə əlavə edirik.

   3. Nodumuzun alt sağ nodu varsa queue-ə əlavə edirik.

   4. Queue-dən birinci daxil olan nodu götürüb və silirik.

static void traverse(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        System.out.print(node.getData() + " ");

        if (node.getLeftNode() != null) {
            queue.add(node.getLeftNode());
        }

        if (node.getRightNode() != null) {
            queue.add(node.getRightNode());
        }
    }
}

5 6 7 8 9 10 11 12 13 

Aşağıda kodu tam formasına baxa bilərsiniz. Node classımız özündə bir dəyər və alt sol-sağ nodları saxlıyır.

package bfs.dfs;

public class Node {

    private int data;
    private Node leftNode;
    private Node rightNode;

    public Node(int data) {
        this.data = data;
        this.leftNode = null;
        this.rightNode = null;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }
}

DFS,

package bfs.dfs;

public class DFS {

    static void traversePreOrder(Node root) {
        if (root == null) return;

        System.out.print(root.getData() + " ");
        traversePreOrder(root.getLeftNode());
        traversePreOrder(root.getRightNode());
    }

    static void traverseInOrder(Node root) {
        if (root == null) return;

        traverseInOrder(root.getLeftNode());
        System.out.print(root.getData() + " ");
        traverseInOrder(root.getRightNode());
    }

    static void traversePostOrder(Node root) {
        if (root == null) return;

        traversePostOrder(root.getLeftNode());
        traversePostOrder(root.getRightNode());
        System.out.print(root.getData() + " ");
    }

    public static void main(String[] args) {
        Node root = new Node(5);

        root.setLeftNode(new Node(6));
        root.getLeftNode().setLeftNode(new Node(8));
        root.getLeftNode().setRightNode(new Node(9));

        root.setRightNode(new Node(7));
        root.getRightNode().setLeftNode(new Node(10));
        root.getRightNode().setRightNode(new Node(11));
        root.getRightNode().getRightNode().setLeftNode(new Node(12));
        root.getRightNode().getRightNode().setRightNode(new Node(13));

        traversePreOrder(root);
        System.out.println();
        traverseInOrder(root);
        System.out.println();
        traversePostOrder(root);
    }
}

BFS,

package bfs.dfs;

import java.util.LinkedList;
import java.util.Queue;

public class BFS {

    static void traverse(Node root) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.getData() + " ");

            if (node.getLeftNode() != null) {
                queue.add(node.getLeftNode());
            }

            if (node.getRightNode() != null) {
                queue.add(node.getRightNode());
            }
        }
    }

    public static void main(String[] args) {
        Node root = new Node(5);

        root.setLeftNode(new Node(6));
        root.getLeftNode().setLeftNode(new Node(8));
        root.getLeftNode().setRightNode(new Node(9));

        root.setRightNode(new Node(7));
        root.getRightNode().setLeftNode(new Node(10));
        root.getRightNode().setRightNode(new Node(11));
        root.getRightNode().getRightNode().setLeftNode(new Node(12));
        root.getRightNode().getRightNode().setRightNode(new Node(13));

        traverse(root);
    }
}

Son olaraq, DFS və BFS-in time complexity-si O(V)-dir. Burada V, nodların sayıdır.