Что такое лист дерева?

Что такое лист дерева?

В структуре данных 'дерево' листом (leaf node) называется узел, который не имеет дочерних узлов. Это конечная точка ветви, от которой дальше не отходят новые узлы. Листья находятся на нижнем уровне иерархии и не содержат ссылок на другие узлы.

Пример в бинарном дереве

Рассмотрим бинарное дерево, где каждый узел может иметь до двух потомков. Листьями будут узлы, у которых оба потомка равны null.

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

// Создаем дерево:
//     1
//    / \
//   2   3
//  /
// 4

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);

// Листья: узел 3 (нет потомков) и узел 4 (нет потомков)
console.log(root.right.left === null && root.right.right === null); // true
console.log(root.left.left.left === null && root.left.left.right === null); // true

Применение

Листья важны при обходе дерева (например, в алгоритмах DFS и BFS), при вычислении высоты дерева, а также в синтаксических деревьях компиляторов, где листья представляют операнды или константы.

Вывод: Понимание листьев необходимо для работы с любыми иерархическими данными, от файловых систем до структур данных в программировании.