Дерево бинарного поиска на JavaScript – массивы и структуры данных

Question 1

Я пытаюсь построить двоичное дерево с помощью массива. Я хочу взять массив, найти корень и разделить его на правую и левую стороны, затем выполнить такое же разделение на каждой стороне, если это необходимо, пока не останется два числа, при этом наименьшее будет слева, а наибольшее – справа. Числа с левой стороны будут меньше, чем числа с правой стороны.

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree{
    constructor(nums){
        this.nums = nums
        this.root = null
    }

    buildtree(nums) {

        if (nums.length <= 0) { return null} 

        let root = this.root
        //console.log(root)  null
        let mid = Math.floor(nums.length / 2)
        //console.log(nums[mid])3-just mid and 4-mid nums

        root = new Node(nums[mid])
        //console.log(root)

        let lSide = nums.slice(0, mid)
        console.log(lSide, "левая сторона, не использованная")

        let rSide = nums.slice(mid  + 1, nums.length)
        console.log(rSide, "правая сторона не использованная")
        
        console.log(lSide.length, rSide.length)
         //пока в очереди каждого мини массива есть что-то

        //Общая длина массива, используемая в качестве счетчика
        let totalLength = lSide.length + rSide.length
        console.log(totalLength)

        let i = 0;


        while(totalLength >= i){
            i++ //console.log(i) я получил 7 циклов

            //если левая сторона больше 3 и не равна null
            if (lSide.length >= 3 && lSide.length != null){
                //Получаем середину левой стороны

                let lMid = Math.ceil(lSide.length / 2)
                //console.log(lMid)
                
                let parent = new Node(lMid)
                root.left = parent //всё здесь умирает
                //buildtree(lSide)

                //Я хотел бы вернуть функцию после цикла while 
                //пока очередь не пуста, но мне не повезло
                //это сделать
                
            }  if (lSide <= 3 && lSide != null){
               
                if(lSide[0] < lSide[1]){
                    let child = new Node(lSide[0])
                    parent.left = child
                } else if (lSide[0] > lSide[1]){
                    let child = new Node(lSide[1])
                    parent.right = child
                } else if (rSide.length >= 3 && rSide.length != null){
                    //Получаем середину правой стороны
                    
                    let rMid = Math.ceil(rSide.length / 2)
                    console.log(rMid)
    
                    let parent = new Node(rMid)
                    root.left = parent
                }

                  else if (rSide <= 3 && rSide != null){
                    if(rSide[0] < rSide[1]){
                        let child = new Node(rSide[0])
                        parent.left = child
                    } else if (rSide[0] > rSide[1]){
                        let child = new Node(rSide[1])
                    }
                }
            }
        }//while
        return root
        
    }//функция
} //класс



const nums = [1, 2, 3, 4, 5, 6, 7]
const bst = new BinarySearchTree(nums)
//console.log(root.nums)
console.log(bst.buildtree(nums))

Html код ниже

<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width">
    <script type="module" src="myscript.js"></script>
    
    <title>Тест</title>
  </head>

  <body>
    
    
  </body>

</html>

Я пробовал множество различных способов сделать это, и это лучшая логика на данный момент. Я написал код, как будто разговаривал с собой.

Проблема заключается в комментариях: если я доберусь до первого узла, отправлю его в root.left и цикл while больше ничего для меня не делает. Я знаю, что цикл while все еще продолжается, пока переменная -i не достигнет длины, потому что я проверял это с помощью console.log. Может кто-нибудь помочь мне продвинуться дальше с этим.

Мой главный вопрос: как мне заставить текущий код работать без записи первого узла налево и без его “смерти”.

Question 2

Чтобы построить двоичное дерево поиска (BST) из отсортированного массива, мы можем рекурсивно выбирать средний элемент массива в качестве корневого узла, а затем рекурсивно строить левое поддерево из левой половины массива и правое поддерево из правой половины. Ваша логика правильная, но есть несколько проблем с вашим подходом, особенно со рекурсивной структурой.

Ключ к решению проблемы:

Используйте средний элемент массива в качестве корня.
Рекурсивно делите левые и правые подмассивы и назначайте их как левых и правых детей текущего узла.
Базовый случай: если массив содержит 1 или 2 элемента, обрабатывайте их соответствующим образом, убедившись, что меньшая величина идет налево, а большая – направо.

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(nums) {
        this.nums = nums;
        this.root = this.buildtree(nums);
    }

    buildtree(nums) {
        // Базовый случай: если нет элементов, возвращаем null
        if (nums.length === 0) return null;

        // Находим средний элемент массива
        let mid = Math.floor(nums.length / 2);
        let node = new Node(nums[mid]);

        // Рекурсивно строим левые и правые поддеревья
        node.left = this.buildtree(nums.slice(0, mid)); // Левый подмассив
        node.right = this.buildtree(nums.slice(mid + 1)); // Правый подмассив

        return node; // Возвращаем текущий узел (корень поддерева)
    }
}

// Тестирование реализации
const nums = [1, 2, 3, 4, 5, 6, 7];
const bst = new BinarySearchTree(nums);

// Функция для печати структуры дерева (для тестирования)
function printTree(node, level = 0) {
    if (node !== null) {
        printTree(node.right, level + 1);
        console.log(" ".repeat(4 * level) + "-> " + node.value);
        printTree(node.left, level + 1);
    }
}

printTree(bst.root);

Дерево бинарного поиска на JavaScript – массивы и структуры данных

Вопрос или проблема

Ответ или решение

Основные шаги реализации:

Реализация

Объяснение кода

Печать дерева

Заключение