Дерево, имеющее не более двух дочерних элементов, называется бинарным деревом.
Каждое дерево имеет корневой узел. На рис. 1 узел со значением 1 является корневым узлом.
Обход уровня
При обходе по уровням мы обходим узел уровень за уровнем. На уровне 0 у нас есть один узел со значением 1.
Уровень 1=› 2 узла со значением 2,3
Уровень 2=> 4 узла со значением 4,5,6,7
Уровень 3=> 6 узлов со значением 8,9,10,11,12,13,14
Обход порядка уровней для вышеприведенного дерева.
1,2,3,4,5,6,7,8,9,10,11,12,13,14
Алгоритм обхода следующий:
- Возьмите очередь с именем q
- Если root!==null, поместите root в q
- Удалите первое значение из q и назовите его узлом
- распечатать значение узла
- поместите левый дочерний элемент и правый дочерний элемент узла в очередь, если они не равны нулю
- повторять 3,4,5 до тех пор, пока q не станет пустым.
Код приведен ниже.
levelOrder(root) {
let q = [];
if (root !== null) q.push(root);
while (q.length !== 0) {
const node = q.shift();
console.log(node.data);
if (node.left != null) q.push(node.left);
if (node.right != null) q.push(node.right);
}
}
levelorder — это метод, который использует корень дерева в качестве параметра.
