# 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. ```java 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. ```java 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. ```java 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. ```java static void traverse(Node root) { Queue 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. ```java 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**, ```java 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**, ```java package bfs.dfs; import java.util.LinkedList; import java.util.Queue; public class BFS { static void traverse(Node root) { Queue 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. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://sananirajabov.gitbook.io/sanani-notes/data-struktur-v-alqoritml-r/tree-ucun-bfs-v-dfs.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.