Двоичное дерево в javascript

Введение

Бинарное дерево — это структура данных, в которой каждый элемент (узел) может иметь не более двух дочерних элементов.

В этой статье я расскажу вам, как мы можем реализовать двоичное дерево в javascript. Итак, давайте кодировать

Код

class Node {
    constructor(data) {
        this.data = data;
    }
}
class BinaryTree {
    constructor() {
        this.root = new Node(2);
        this.root.left = new Node(7);
        this.root.right = new Node(5);
    }
}

Программа проста: двоичное дерево содержит корневой элемент, который является узлом, и содержит еще два узла, которые находятся в левой и правой позициях. Как и корневой элемент, каждый узел содержит еще два узла в левой и правой позициях. У узла есть три части - данные, левая и правая.

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

Обход

Теперь давайте посмотрим, как обойти дерево. Есть три типа обхода -

• Неупорядоченный обход - сначала посетите левый узел, затем корень и последний правый узел.
• Обход в предварительном порядке - сначала посетите корневой узел, затем левый и последний правый узел.
• Обход в обратном порядке - сначала посетите левый узел, затем правый и последний корневой узел.

Давайте напишем программу для обхода данных:

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinaryTree {
    constructor() {
        this.root = new Node(2);
        this.root.left = new Node(10);
        this.root.right = new Node(5);
   }
    inOrderTraverse() {
        const traverse = (node) => {
            if (node != null) {
                traverse(node.left);
                console.log(node.data);
                traverse(node.right);
            }
        }
        traverse(this.root);
    }
   preOrderTraverse() {
        const traverse = (node) => {
            if (node != null) {
                console.log(node.data);
                traverse(node.left);
                traverse(node.right);
            }
         }
        traverse(this.root);
    }
    postOrderTraverse() {
        const traverse = (node) => {
            if (node != null) {
                traverse(node.left);
                traverse(node.right);
                console.log(node.data);
            }
         }
        traverse(this.root);
    }
}
const tree = new BinaryTree();
tree.inOrderTraverse();
tree.preOrderTraverse();
tree.postOrderTraverse();

Searching

Поиск в бинарном дереве можно выполнить двумя способами:

• BFS - поиск элемента по ширине, т.е. сначала проверьте левый элемент, а затем правый элемент
• DFS - поиск по глубине, т.е. сначала проверьте всю левую сторону, а затем правую сторону или сначала правую сторону, а затем левую сторону.

Давайте посмотрим каждый из них -

БФС

Алгоритм BFS проверяет элементы по строкам, то есть сначала проверяет все левые и правые элементы строки, прежде чем перейти к следующей строке.

Давайте посмотрим программу, чтобы было понятнее -

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
class BinaryTree {
  constructor() {
    this.root = new Node(2);
    const leftNode = new Node(10);
    leftNode.left = new Node(22);
    leftNode.right = new Node(123);
    this.root.left = leftNode;
    this.root.right = new Node(5);
  }
  bfs(searchValue) {
    const search = (tree) => {
      var queue = []
      queue.push(tree);
      while (queue.length !== 0) {
        for (let i = 0; i < queue.length; i++) {
          var node = queue.shift()
          if (node.data === searchValue) {
            return node
          }
          // search breadth wise, so push left & right node
          if (node.left) {
            queue.push(node.left)
          }
          if (node.right) {
            queue.push(node.right)
          }
        }
      }
      return null
    }
    return search(this.root);
   }
}
const tree = new BinaryTree();
tree.bfs(22);

ДФС

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinaryTree {
    constructor() {
        this.root = new Node(2);
        const leftNode = new Node(10);
        leftNode.left = new Node(22);
        leftNode.right = new Node(123);
        this.root.left = leftNode;
        this.root.right = new Node(5);
    }
    dfs(searchValue) {
        var stack = []
        stack.push(this.root);
        while (stack.length !== 0) {
            for (let i = 0; i < stack.length; i++) {
                var node = stack.pop()
                if (node.data === searchValue) {
                    return node
                }
                // search breadth wise, so push left & right node
                if (node.left) {
                    stack.push(node.left)
                }
                if (node.right) {
                    stack.push(node.right)
                }
            }
        }
        return null
    }
}
const tree = new BinaryTree();
tree.dfs(22);

Как вы можете видеть, единственная разница между bsf и dfs заключается в том, что bfs использует очередь, а dfs использует стек, и, конечно, из-за этого они ищут элемент по-разному.

Спасибо, что прочитали это, ребята. Надеюсь, вы найдете ее полезной.