В уровневом порядке узел вставки вставляется в двоичное дерево уровень за уровнем. Ни один узел не будет вставлен на следующий уровень, пока не будет заполнен последний уровень.
На рис. 1 нам нужно вставить узел 5. На уровнях 0 и 1 нет свободных мест. На уровне 2 узел 2 не имеет левых дочерних элементов, а узел 3 не имеет дочерних элементов, но первое свободное место является левым дочерним элементом узла 2, поэтому узел 5 будет вставлен, как показано на рис. 1.
Мы можем инициализировать дерево следующим образом.
class Tree {
constructor() {
this.root = null;
}
Дерево состоит из узлов, поэтому у нас должен быть один класс узлов.
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
Теперь нам нужно создать метод для вставки узлов в дерево.
Если в дереве нет ни одного узла, то новый узел будет корневым.
insert(data){
if(this.root===null)
this.root= new Node(data)
}
Здесь this.root будет ссылаться на корень дерева, потому что метод вставки создается внутри класса дерева.
Для обхода порядка уровней мы будем использовать структуру данных очереди, основанную на механизме «первым пришел — первым обслужен». Остальная часть кода выглядит следующим образом.
insert(data) {
const q = [];
if (this.root === null) {
this.root = new Node(data);
} else {
q.push(this.root);
while (q.length !== 0) {
const node = q.shift();
if (node.left === null) {
node.left = new Node(data);
break;
} else {
q.push(node.left);
}
if (node.right === null) {
node.right = new Node(data);
break;
} else {
q.push(node.right);
}
}
}
Если вы заинтересованы в дальнейшем чтении о дереве и о том, как мы можем перемещаться по дереву, вы можете перейти по ссылке ниже.
Спасибо за прочтение :)
