> For the complete documentation index, see [llms.txt](https://sananirajabov.gitbook.io/sanani-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sananirajabov.gitbook.io/sanani-notes/data-struktur-v-alqoritml-r/tree-ucun-bfs-v-dfs.md).
# 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.