Отображение разных представлений бинарного дерева поиска — частый вопрос, который задают во многих интервью, даже самых крупных!
Независимо от того, является ли это JavaScript или нет, вы должны быть в состоянии взломать логику. Но давайте немного конкретнее и посмотрим, как вы можете решить эту проблему в JavaScript. Прежде чем определить верхнее, нижнее, левое и правое представление бинарного поиска — нам нужно построить дерево.
Давайте начнем с построения бинарного дерева поиска в JavaScript.
Узлы
Каждый элемент в дереве известен как «узел». Узел можно изобразить как объект, обладающий несколькими свойствами. В случае бинарного дерева поиска оно будет содержать значение, указатель на левый узел, указатель на правый узел и даже информацию об уровне.
Конструктор можно использовать для создания отдельных объектов для каждого узла в дереве. В приведенном ниже коде мы создаем новый Класс под названием «Узел». У класса есть конструктор, который инициализирует свойства каждого узла Object. Вы можете создать столько Node Objects, сколько потребуется. И каждый объект узла будет рассматриваться как элемент в двоичном дереве поиска.
Преимущества использования конструктора для создания элемента дерева:
Конструктор делает код более лаконичным и простым.
Конструктор помогает инкапсулировать частные свойства. Это делает код масштабируемым и переносимым.
class Node{
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
}
Дерево
Дерево также является классом с конструктором, который инициализирует корень. И все методы, необходимые для построения дерева, отображения верхнего, нижнего, левого и правого представления, инкапсулированы в класс. Доступ к этим методам можно получить, создав новый объект дерева.
Определение класса будет следующим:
class tree{
constructor(){
this.root = null;
}
topView(root,hash){}
bottomView(root, hash){}
leftView(root, hash){}
rightView(root, hash){}
insert(value){}
}
Вставка нового узла в дерево
Чтобы вставить новый узел в бинарное дерево поиска, мы используем стандартную логику.
Если корневой узел нулевой, создайте новый узел и назначьте его корневым узлом.
Если корневой узел не нулевой, проверьте значение нового узла по сравнению со значением корневого узла.
Если корневой узел меньше нового узла, перейдите к правому дереву. Если корневой узел больше нового узла, перейдите к левому дереву. Продолжайте, пока не будет найден листовой узел.
Как только конечный узел достигнут, назначьте новый узел для конечного узла. Если новый Node больше, чем конечный Node, он становится правильным потомком. Если новый узел меньше листового узла, он становится левым дочерним элементом.
Код для вставки будет следующим в Javascript. Всегда помните, что логика двоичной вставки остается неизменной. Но стиль кодирования отличается. Давайте лучше разберемся с реальными строками кода.
insert(value){
let newNode = new Node(value);
if(this.root == null){
this.root = newNode;
return this;
}
addNode(this.root,newNode);
function addNode(node,newNode)
{
if (node.value == newNode.value)
return;
if (node.value > newNode.value)
{
if(node.left == null)
node.left = newNode;
else
addNode(node.left, newNode);
}
else
{
if(node.right == null)
node.right = newNode;
else
addNode(node.right,newNode);
}
}
}
Мы полагаемся на «addNode» для завершения вставки. И addNode — это локальная функция, инкапсулированная в вставку (значение). addNode не может быть доступен вне функции вставки (значения). Кроме того, это помогает легче строить рекурсивную логику.
Чтобы вызвать вставку, будут работать следующие строки кода:
let t = new tree(); t.insert(10); t.insert(2); t.insert(5); t.insert(13); t.insert(50); t.insert(1);
Вид сверху
Теперь давайте перейдем к сути вопроса нашего интервью. Как найти вид сверху бинарного дерева поиска в JavaScript? Один из подходов — использовать хэш-карту.
Псевдокод для построения вида сверху:
Назначьте корневому узлу хэш-ключ «0».
Когда левый узел пройден, уменьшите «1» из хэш-ключа родительского узла.
Когда пройден правый узел, увеличьте «1» из хеш-ключа родительского узла.
Если хэш-ключ не найден, создайте новый хэш-ключ, и значением должен быть узел.
Если хэш-ключ найден, ничего не делайте.
Отсортируйте все хэш-ключи, окончательный результат, отсортированный в хэш-карте, будет видом сверху двоичного дерева поиска.
Код для отображения вида сверху будет следующим:
topView(root, hash){
this.root.level = 0;
hash.set(0,this.root);
function buildTopView(node){
let leftie = node.left;
let rightie = node.right;
if(leftie != null){
leftie.level = node.level - 1;
if(!hash.get(leftie.level)){
hash.set(leftie.level, leftie);
}
buildTopView(leftie);
}
if(rightie != null){
rightie.level = node.level + 1;
if(!hash.get(rightie.level)){
hash.set(rightie.level, rightie);
}
buildTopView(rightie);
}
else
return;
}
buildTopView(this.root, 0);
var resultMap = new Map([...hash.entries()].sort());
for(let [k,v] of resultMap){
console.log(v.value);
}
}
Вид снизу
Код для отображения вида снизу очень похож на логику, рассмотренную выше. Однако есть небольшая поправка к способу изменения хэш-карты. При отображении нижнего вида хэш-карта всегда заменяется текущим узлом для соответствующего хеш-ключа.
Псевдокод для построения вида сверху:
Назначьте корневому узлу хэш-ключ «0».
Когда левый узел пройден, уменьшите «1» из хеш-ключа родительского узла.
Когда пройден правый узел, увеличьте «1» из хеш-ключа родительского узла.
Если хэш-ключ не найден, создайте новый хэш-ключ, и значением должен быть узел.
Если хэш-ключ найден, замените существующее хеш-значение текущим узлом.
Отсортируйте все хэш-ключи, окончательный результат, отсортированный в хэш-карте, будет видом сверху двоичного дерева поиска.
Код для отображения вида сверху будет следующим:
bottomView(root, hash){
this.root.level = 0;
hash.set(0,this.root);
function buildBottomView(node){
let leftie = node.left;
let rightie = node.right;
if(leftie != null){
leftie.level = node.level - 1;
if(!hash.get(leftie.level)){
hash.set(leftie.level, leftie);
}
buildBottomView(leftie);
}
if(rightie != null){
rightie.level = node.level + 1;
if(!hash.get(rightie.level)){
hash.set(rightie.level, rightie);
}
buildBottomView(rightie);
}
else
return;
}
buildBottomView(this.root, 0);
var resultMap = new Map([...hash.entries()].sort());
for(let [k,v] of resultMap){
console.log(v.value);
}
}
Левый взгляд
Еще раз, чтобы найти левый вид дерева, мы полагаемся на хеш-карту. Но все узлы одного уровня будут иметь один и тот же ключ. Это означает, что корень будет иметь ключ «0». Все его непосредственные дочерние узлы будут иметь ключ «1», а дочерние элементы этих узлов будут иметь ключ «2».
Псевдокод для отображения левого вида на основе приведенных выше ключей:
Инициализируйте текущий уровень «0» и создайте запись в хеш-карте с ключом = 0 и значением = корневой узел.
Увеличьте уровень на 1.
Перейдите к левому дочернему элементу текущего узла (во время первой итерации это будет корневой узел). Если в хэш-карте нет записи для текущего уровня, добавьте ее с ключом = текущий уровень, а значение = текущий узел.
Если в хэш-карте есть запись для текущего уровня, ничего не делайте.
Перейдите к правому потомку текущего узла (во время первой итерации это будет корневой узел). Уровень менять не нужно. Он был увеличен как часть шага 2. Если в хеш-карте нет записи для текущего уровня, добавьте ее с ключом = текущий уровень и значение = текущий узел.
Если в хэш-карте есть запись для текущего уровня, ничего не делайте.
Повторяйте шаги со 2 по 6, пока не будет пройдено все дерево.
Отсортируйте все хэш-ключи, окончательный результат, отсортированный в хэш-карте, будет видом сверху двоичного дерева поиска.
Код для достижения этой логики будет следующим:
leftView(root, hash){
this.root.level = 0;
hash.set(0,this.root);
function buildLeftView(node, nextLevel){
let leftie = node.left;
let rightie = node.right;
let levelInFocus = nextLevel +1;
if(!hash.get(levelInFocus) && leftie != null){
hash.set(levelInFocus, leftie);
buildLeftView(leftie,levelInFocus)
}
else if(!hash.get(nextLevel) && rightie != null){
hash.set(levelInFocus, rightie);
buildLeftView(rightie,levelInFocus)
}
else
return;
}
buildLeftView(this.root,0);
var resultMap = new Map([...hash.entries()].sort());
for(let [k,v] of resultMap){
console.log(v.value);
}
}
Правильный взгляд
Правое представление бинарного дерева поиска следует той же логике, что и левое представление. Но есть небольшое изменение в направлении обхода дерева. В отличие от левого представления, правое представление начинается с правого потомка корневого (или родительского) узла. Если правый дочерний узел пуст, он перемещается к левому дочернему элементу родительского узла.
Псевдокод для отображения правильного вида:
Инициализируйте текущий уровень «0» и создайте запись в хеш-карте с ключом = 0 и значением = корневой узел.
Увеличьте уровень на 1.
Перейдите к правому потомку текущего узла (во время первой итерации это будет корневой узел). Если в хэш-карте нет записи для текущего уровня, добавьте ее с ключом = текущий уровень, а значение = текущий узел.
Если в хэш-карте есть запись для текущего уровня, ничего не делайте.
Перейдите к левому дочернему элементу текущего узла (во время первой итерации это будет корневой узел). Уровень менять не нужно. Он был увеличен как часть шага 2. Если в хеш-карте нет записи для текущего уровня, добавьте ее с ключом = текущий уровень и значение = текущий узел.
Если в хэш-карте есть запись для текущего уровня, ничего не делайте.
Повторяйте шаги со 2 по 6, пока не будет пройдено все дерево.
Отсортируйте все хэш-ключи, окончательный результат, отсортированный в хэш-карте, будет видом сверху двоичного дерева поиска.
Код отображения правильного представления бинарного дерева поиска:
rightView(root, hash){
this.root.level = 0;
hash.set(0,this.root);
function buildRightView(node, nextLevel){
let leftie = node.left;
let rightie = node.right;
let levelInFocus = nextLevel +1;
if(rightie != null){
hash.set(levelInFocus, rightie);
buildRightView(rightie,levelInFocus)
}
else if(leftie != null){
hash.set(levelInFocus, leftie);
buildRightView(leftie,levelInFocus)
}
else
return;
}
buildRightView(this.root,0);
var resultMap = new Map([...hash.entries()].sort());
for(let [k,v] of resultMap){
console.log(v.value);
}
}
Пример
Приведенные выше строки кода тестируются на следующем примере:
let t = new tree();
t.insert(10);
t.insert(2);
t.insert(5);
t.insert(13);
t.insert(50);
t.insert(1);
let hashMap = new Map();
t.iterateTree(t.root);
console.log("Top View");
t.topView(t.root, hashMap);
console.log("Bottom View");
t.bottomView(t.root, hashMap);
console.log("Left View");
t.leftView(t.root, hashMap);
console.log("Right View");
t.rightView(t.root, hashMap);
И вывод следующий:
Top View 2 1 10 13 50 Bottom View 2 1 5 13 50 Left View 2 1 10 13 50 Right View 2 1 10 13 50
Вывод
Найти вид сверху, вид снизу, вид слева и вид справа бинарного дерева поиска несложно. Ключевым элементом логики будет использование Карт. Карты упрощают весь процесс хранения информации с помощью пары [Ключ, значение]. С такой структурой данных остальная часть кода зависит только от используемой логики!
Забрать домой
Ссылка на Github:
https://github.com/CodeLearnDDev/basicJS.git
имя файла: binarySearchTreeViews
