Tree Traversing
V minulé části jsme si vytvořili Binary Search Tree a zkusili jsme si v něm hledat hodnoty. Díky tomu, že je Binary Search Tree seřazený, je hledání hodnot celkem jednoduché. Pokud ale chceme hledat hodnotu v tree, který není seřazený, tak už to je trochu složitější. Existuje více cest jak hledat hodnotu v tree, který není seřazený. V této části si ukážeme celkem čtyři metody, které k tomu můžeme použít.
Co je to Tree Traversing
Tato část je pojmenovaná jako Tree Traversing. V češtině traversing znamená procházení. Ukážeme si tu tedy, jakými způsoby můžeme tree procházet. Vytvoříme si na to celkem čtyři metody, a každá metoda bude pro procházení tree používat jiný algoritmus. Tyto metody budou hodnoty procházených nodes ukládat do pole a to potom vrátí. Pokud byste ale tyto metody chtěli použít k vyhledávání node, tak si je můžete trochu poupravit. Cílem této části je jen ukázat, jakými způsoby se dá tree procházet a chtěl jsem aby se vždy projel celý tree.
Existují dva hlavní způsoby pro procházení tree: Breadth First Search a Depth First Search. Breadth First Search prochází tree horizontálně a Depth First Search spíš vertikálně. Jak přesně tyto algoritmy fungují si tu později ukážeme. U Depth First Search navíc existují tři hlavní verze: InOrder, PreOrder a PostOrder. Všechny tyto verze si v této části ukážeme.
Co pro ukázku procházení tree použijeme
Abychom si mohli ukázat různé způsoby procházení tree, tak k tomu musíme mít nějaký tree vytvořený. V minulé části jsme si vytvořili třídu pro Binary Search Tree, kterou teď můžeme použít. Přidáme si do ní metody pro ukázku různých způsobů procházení tree. Binary Search Tree je sice seřazený, ale metody, které si pro něj vytvoříme by fungovali i kdyby seřazený nebyl. Binary Search Tree z minulé části používáme hlavně proto, abychom nemuseli vytvářet nějaký nový tree.
Další věc, kterou budeme potřebovat, je Queue. Budeme ji potřebovat pro Breadth First Search. Queue jsme si ukazovali v části Stack a Queue.
Následující ukázka ukazuje startovní kód. Protože Queue i BinarySearchTree třídy používali stejně pojmenované třídy pro node, tak je Node třída pro Queue přejmenována na QueueNode.
class QueueNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
enqueue(value) {
const newNode = new QueueNode(value);
if (!this.first) {
this.first = newNode;
this.last = newNode;
} else {
this.last.next = newNode;
this.last = newNode;
}
return ++this.size;
}
dequeue() {
if (!this.first) return null;
const value = this.first.value;
if (this.first === this.last) {
this.last = null;
}
this.first = this.first.next;
this.size--;
return value;
}
}
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
if (value === current.value) return undefined;
if (value > current.value) {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
} else {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
}
}
}
find(value) {
if (!this.root) return false;
let current = this.root;
while (current) {
if (value === current.value) return current;
if (value > current.value) {
current = current.right;
} else {
current = current.left;
}
}
return false;
}
}Breadth First Search
První algoritmus pro procházení tree, který si ukážeme, je Breadth First Search. Tento algoritmus prochází tree horizontálně. Začne se u root a dále se tree postupně prochází dolů. Vždy se nejprve projdou nodes na stejné úrovni a poté se pokračuje dál.
Tento algoritmus používá datovou strukturu Queue, do které se postupně přidávají nodes, které se mají procházet. Na začátku se do queue přidá root node. Poté se spustí cyklus, který se opakuje tak dlouho, dokud queue není prázdná. V každém cyklu se vždy z queue vezme jedna node a její potomci se do queue přidají. Tímto způsobem se postupně projde celý tree.
class BinarySearchTree {
/* ... */
// metoda pro Breadth First Search
BFS() {
// vytvoření queue
const queue = new Queue();
// do tohoto pole se budou postupně ukládat hodnoty nodes
const data = [];
// přidání root node do queue
queue.enqueue(this.root);
// tento cyklus se bude opakovat tak dlouho, dokud queue nebude prázdná
while (queue.size > 0) {
// získání node z queue
const node = queue.dequeue();
// hodnota node se vloží do pole data
data.push(node.value);
// pokud má node potomky, tak se přidají do queue (nejprve se přidá potomek nalevo)
if (node.left) queue.enqueue(node.left);
if (node.right) queue.enqueue(node.right);
}
// vrácení pole s hodnotami
return data;
}
}
// vytvoření tree
const tree = new BinarySearchTree();
tree.insert(10).insert(5).insert(16).insert(13).insert(6).insert(2);
tree.insert(17).insert(7).insert(3).insert(14).insert(11);
// zavolání metody pro Breadth First Search
const vysledek = tree.BFS();
console.log("Tree se procházel v tomto pořadí:");
console.log(vysledek);Depth First Search - PreOrder
Druhý algoritmus, který si pro procházení tree ukážeme, je Depth First Search. Tento algoritmus má tři verze: PreOrder, PostOrder a InOrder. Tyto verze se liší jen umístěním jednoho řádku kódu. Jako první si ukážeme PreOrder.
Depth First Search algoritmus funguje tak, že se tree začne procházet od root node dolů směrem doleva. Jakmile se narazí na konec větve, tak se pokračuje zpátky nahoru, přičemž se procházejí potomci napravo. Pro ty se tato operace také provádí a postupně se tak projde celý tree.
Rozdíl mezi všemi třemi verzemi Depth First Search algoritmu je umístění kódu, který v našem případě přidává hodnotu node do pole. U PreOrder verze se hodnota uloží hned, jak se na node narazí a než se pokračuje v procházení dál.
Depth First Search používá rekurzy, takže pro vás může být jeho pochopení o něco těžší než Breadth First Search. Ale myslím, že následující vizuální ukázka vám v jeho pochopení může dost pomoct.
class BinarySearchTree {
/* ... */
// metoda pro Depth First Search - PreOrder
DFSPreOrder() {
// do tohoto pole se budou postupně ukládat hodnoty nodes
const data = [];
// pomocná funkce pro procházení tree
const traverse = function(node) {
// hodnota node se vloží do pole data
data.push(node.value);
// pokud má node levého potomka, tak se zavolá funkce traverse a potomek se předá jako argument
if (node.left) traverse(node.left);
// pokud má node pravého potomka, tak se zavolá funkce traverse a potomek se předá jako argument
if (node.right) traverse(node.right);
}
// zavolání funkce pro procházení tree s root node jako argumentem
traverse(this.root);
// vrácení pole s hodnotami
return data;
}
}
// vytvoření tree
const tree = new BinarySearchTree();
tree.insert(10).insert(5).insert(16).insert(13).insert(6).insert(2);
tree.insert(17).insert(7).insert(3).insert(14).insert(11);
// zavolání metody pro Depth First Search - PreOrder
const vysledek = tree.DFSPreOrder();
console.log("Tree se procházel v tomto pořadí:");
console.log(vysledek);Depth First Search - PostOrder
V předchozí ukázce jsme si ukázali PreOrder verzi Depth First Search algoritmu. Teď si ukážeme PostOrder verzi. Ta se od PreOrder verze liší tím, že se nejprve prochází potomci node a až poté se hodnota node uloží do pole. Hodnota node se tedy do pole uloží až při vracení zpět nahoru.
Jediný rozdíl v kódu pro PreOrder a PostOrder verzi je umístění řádku kódu, který vkládá hodnotu node do pole.
class BinarySearchTree {
/* ... */
// metoda pro Depth First Search - PostOrder
DFSPostOrder() {
const data = [];
const traverse = function(node) {
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
// u PostOrder verze se hodnota node do pole data vloží až se projde její levý a pravý potomek
data.push(node.value);
}
traverse(this.root);
return data;
}
}
// vytvoření tree
const tree = new BinarySearchTree();
tree.insert(10).insert(5).insert(16).insert(13).insert(6).insert(2);
tree.insert(17).insert(7).insert(3).insert(14).insert(11);
// zavolání metody pro Depth First Search - PostOrder
const vysledek = tree.DFSPostOrder();
console.log("Tree se procházel v tomto pořadí:");
console.log(vysledek);Depth First Search - InOrder
Poslední verze Depth First Search algoritmu, kterou si ukážeme, je InOrder. Ta funguje tak, že se nejprve prochází levý potomek node, potom se hodnota node uloží do pole a poté se prochází pravý potomek node.
Jediný rozdíl v kódu oproti verzím PreOrder a PostOrder je opět umístění řádku kódu, který vkládá hodnotu node do pole.
class BinarySearchTree {
/* ... */
// metoda pro Depth First Search - InOrder
DFSInOrder() {
const data = [];
const traverse = function(node) {
if (node.left) traverse(node.left);
// u InOrder verze se hodnota node do pole data vloží až se projde její levý potomek
data.push(node.value);
if (node.right) traverse(node.right);
}
traverse(this.root);
return data;
}
}
// vytvoření tree
const tree = new BinarySearchTree();
tree.insert(10).insert(5).insert(16).insert(13).insert(6).insert(2);
tree.insert(17).insert(7).insert(3).insert(14).insert(11);
// zavolání metody pro Depth First Search - InOrder
const vysledek = tree.DFSInOrder();
console.log("Tree se procházel v tomto pořadí:");
console.log(vysledek);