Как определить, что у узла нет потомков?

Определение узла без потомков

В бинарном дереве каждый узел может иметь до двух потомков: левого и правого. Узел считается не имеющим потомков (листом), если оба его указателя на потомков равны null. Это фундаментальное свойство используется при анализе структуры дерева, например, при подсчёте количества листьев или при проверке, является ли дерево полным.

Пример на JavaScript

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

function isLeaf(node) {
  return node.left === null && node.right === null;
}

// Пример использования
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
console.log(isLeaf(root)); // false
console.log(isLeaf(root.left)); // true

Применение

Определение листовых узлов необходимо в алгоритмах обхода дерева (DFS, BFS), при вычислении высоты дерева, а также в задачах, связанных с удалением узлов или балансировкой. Например, в бинарных деревьях поиска листья — это узлы, которые можно безопасно удалить без нарушения структуры.

Вывод

Проверка на отсутствие потомков — базовая операция при работе с деревьями. Она позволяет идентифицировать листья, что важно для многих алгоритмов обработки деревьев, от простого подсчёта до сложных операций удаления и балансировки.