Как составить бинарное дерево

Бинарные деревья поиска и рекурсия – это просто

Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.

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

Рис. 1 Бинарное дерево

Бинарное дерево поиска — это бинарное дерево, обладающее дополнительными свойствами: значение левого потомка меньше значения родителя, а значение правого потомка больше значения родителя для каждого узла дерева. То есть, данные в бинарном дереве поиска хранятся в отсортированном виде. При каждой операции вставки нового или удаления существующего узла отсортированный порядок дерева сохраняется. При поиске элемента сравнивается искомое значение с корнем. Если искомое больше корня, то поиск продолжается в правом потомке корня, если меньше, то в левом, если равно, то значение найдено и поиск прекращается.

Рис. 2 Бинарное дерево поиска
Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. Данное определение скорее идейное, чем строгое. Строгое определение оперирует разницей глубины самого глубокого и самого неглубокого листа (в AVL-деревьях) или отношением глубины самого глубокого и самого неглубокого листа (в красно-черных деревьях). В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). В вырожденном случае несбалансированного бинарного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности.

Рис. 3 Сбалансированное бинарное дерево поиска

Сбалансированное бинарное дерево поиска применяется, когда необходимо осуществлять быстрый поиск элементов, чередующийся со вставками новых элементов и удалениями существующих. В случае, если набор элементов, хранящийся в структуре данных фиксирован и нет новых вставок и удалений, то массив предпочтительнее. Потому что поиск можно осуществлять алгоритмом бинарного поиска за то же логарифмическое время, но отсутствуют дополнительные издержки по хранению и использованию указателей. Например, в С++ ассоциативные контейнеры set и map представляют собой сбалансированное бинарное дерево поиска.

Рис. 4 Экстремально несбалансированное бинарное дерево поиска

Теперь кратко обсудим рекурсию. Рекурсия в программировании – это вызов функцией самой себя с другими аргументами. В принципе, рекурсивная функция может вызывать сама себя и с теми же самыми аргументами, но в этом случае будет бесконечный цикл рекурсии, который закончится переполнением стека. Внутри любой рекурсивной функции должен быть базовый случай, при котором происходит выход из функции, а также вызов или вызовы самой себя с другими аргументами. Аргументы не просто должны быть другими, а должны приближать вызов функции к базовому случаю. Например, вызов внутри рекурсивной функции расчета факториала должен идти с меньшим по значению аргументом, а вызовы внутри рекурсивной функции обхода дерева должны идти с узлами, находящимися дальше от корня, ближе к листьям. Рекурсия может быть не только прямой (вызов непосредственно себя), но и косвенной. Например А вызывает Б, а Б вызывает А. С помощью рекурсии можно эмулировать итеративный цикл, а также работу структуры данных стек (LIFO).

int factorial(int n)
{
    if(n <= 1)  // Базовый случай
    {
        return 1;
    }
    return n  * factorial(n - 1); //рекурсивеый вызов с другим аргументом
}
// factorial(1):     return 1
// factorial(2):     return 2 * factorial(1) (return 2 * 1)
// factorial(3):     return 3 * factorial(2) (return 3 * 2 * 1)
// factorial(4):     return 4 * factorial(3) (return 4 * 3 * 2 * 1)
// Вычисляет факториал числа n (n должно быть небольшим из-за типа int
// возвращаемого значения. На практике можно сделать long long  и вообще
// заменить рекурсию циклом. Если важна скорость рассчетов и не жалко память, то
// можно совсем избавиться от функции и использовать массив с предварительно
// посчитанными факториалами).

void reverseBinary(int n)
{
    if (n == 0)  // Базовый случай
    {
        return;
    }
    cout << n%2;
    reverseBinary(n/2); //рекурсивеый вызов с другим аргументом
}
// Печатает бинарное представление числа в обратном порядке

void forvardBinary(int n)
{
    if (n == 0)  // Базовый случай
    {
        return;
    }
    forvardBinary(n/2); //рекурсивеый вызов с другим аргументом
    cout << n%2;
}
// Поменяли местами две последние инструкции
// Печатает бинарное представление числа в прямом порядке
// Функция является примером эмуляции стека

void ReverseForvardBinary(int n)
{
    if (n == 0)  // Базовый случай
    {
        return;
    }
    cout << n%2; // печатает в обратном порядке
    ReverseForvardBinary(n/2); //рекурсивеый вызов с другим аргументом
    cout << n%2; // печатает в прямом порядке
}
// Функция печатает сначала бинарное представление в обратном порядке,
// а затем в прямом порядке


int product(int x, int y)
{
    if (y == 0)  // Базовый случай
    {
        return 0;
    }
    return (x + product(x, y-1)); //рекурсивеый вызов с другим аргументом
}
// Функция вычисляет произведение x * y ( складывает x y раз)
// Функция абсурдна с точки зрения практики,
// приведена для лучшего понимания рекурсии

Кратко обсудим деревья с точки зрения теории графов. Граф – это множество вершин и ребер. Ребро – это связь между двумя вершинами. Количество возможных ребер в графе квадратично зависит от количества вершин (для понимания можно представить турнирную таблицу сыгранных матчей). Дерево – это связный граф без циклов. Связность означает, что из любой вершины в любую другую существует путь по ребрам. Отсутствие циклов означает, что данный путь – единственный. Обход графа – это систематическое посещение всех его вершин по одному разу каждой. Существует два вида обхода графа: 1) поиск в глубину; 2) поиск в ширину.

Поиск в ширину (BFS) идет из начальной вершины, посещает сначала все вершины находящиеся на расстоянии одного ребра от начальной, потом посещает все вершины на расстоянии два ребра от начальной и так далее. Алгоритм поиска в ширину является по своей природе нерекурсивным (итеративным). Для его реализации применяется структура данных очередь (FIFO).

Поиск в глубину (DFS) идет из начальной вершины, посещая еще не посещенные вершины без оглядки на удаленность от начальной вершины. Алгоритм поиска в глубину по своей природе является рекурсивным. Для эмуляции рекурсии в итеративном варианте алгоритма применяется структура данных стек.

С формальной точки зрения можно сделать как рекурсивную, так и итеративную версию как поиска в ширину, так и поиска в глубину. Для обхода в ширину в обоих случаях необходима очередь. Рекурсия в рекурсивной реализации обхода в ширину всего лишь эмулирует цикл. Для обхода в глубину существует рекурсивная реализация без стека, рекурсивная реализация со стеком и итеративная реализация со стеком. Итеративная реализация обхода в глубину без стека невозможна.

Асимптотическая сложность обхода и в ширину и в глубину O(V + E), где V – количество вершин, E – количество ребер. То есть является линейной по количеству вершин и ребер. Записи O(V + E) с содержательной точки зрения эквивалентна запись O(max(V,E)), но последняя не принята. То есть, сложность будет определятся максимальным из двух значений. Несмотря на то, что количество ребер квадратично зависит от количества вершин, мы не можем записать сложность как O(E), так как если граф сильно разреженный, то это будет ошибкой.

DFS применяется в алгоритме нахождения компонентов сильной связности в ориентированном графе. BFS применяется для нахождения кратчайшего пути в графе, в алгоритмах рассылки сообщений по сети, в сборщиках мусора, в программе индексирования – пауке поискового движка. И DFS и BFS применяются в алгоритме поиска минимального покрывающего дерева, при проверке циклов в графе, для проверки двудольности.
Обходу в ширину в графе соответствует обход по уровням бинарного дерева. При данном обходе идет посещение узлов по принципу сверху вниз и слева направо. Обходу в глубину в графе соответствуют три вида обходов бинарного дерева: прямой (pre-order), симметричный (in-order) и обратный (post-order).

Прямой обход идет в следующем порядке: корень, левый потомок, правый потомок. Симметричный — левый потомок, корень, правый потомок. Обратный – левый потомок, правый потомок, корень. В коде рекурсивной функции соответствующего обхода сохраняется соответствующий порядок вызовов (порядок строк кода), где вместо корня идет вызов данной рекурсивной функции.

Если нам дано изображение дерева, и нужно найти его обходы, то может помочь следующая техника (см. рис. 5). Обводим дерево огибающей замкнутой кривой (начинаем идти слева вниз и замыкаем справа вверх). Прямому обходу будет соответствовать порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами слева. Для симметричного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами снизу. Для обратного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами справа. В коде рекурсивного вызова прямого обхода идет: вызов, левый, правый. Симметричного – левый, вызов, правый. Обратного – левый правый, вызов.

Рис. 5 Вспомогательный рисунок для обходов

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

struct  TreeNode
{
    double data; // ключ/данные
    TreeNode *left; // указатель на левого потомка
    TreeNode *right; // указатель на правого потомка
};

void levelOrderPrint(TreeNode *root) {
    if (root == NULL)
    {
       return;
    }
    queue<TreeNode *> q; // Создаем очередь
    q.push(root); // Вставляем корень в очередь

    while (!q.empty() ) // пока очередь не пуста
    {
        TreeNode* temp = q.front(); // Берем первый элемент в очереди
        q.pop();  // Удаляем первый элемент в очереди
        cout << temp->data << " "; // Печатаем значение первого элемента в очереди

        if ( temp->left != NULL )
            q.push(temp->left);  // Вставляем  в очередь левого потомка

        if ( temp->right != NULL )
            q.push(temp->right);  // Вставляем  в очередь правого потомка
   }
}


void preorderPrint(TreeNode *root)
{
    if (root == NULL)   // Базовый случай
    {
       return;
    }
    cout << root->data << " ";
    preorderPrint(root->left);   //рекурсивный вызов левого поддерева
    preorderPrint(root->right);  //рекурсивный вызов правого поддерева
}
// Функция печатает значения бинарного дерева поиска в прямом порядке.
// Вместо печати первой инструкцией функции может быть любое действие
// с данным узлом

void inorderPrint(TreeNode *root)
{
    if (root == NULL)   // Базовый случай
    {
       return;
    }
    preorderPrint(root->left);   //рекурсивный вызов левого поддерева
    cout << root->data << " ";
    preorderPrint(root->right);  //рекурсивный вызов правого поддерева
}
// Функция печатает значения бинарного дерева поиска в симметричном порядке.
// То есть в отсортированном порядке

void postorderPrint(TreeNode *root)
{
    if (root == NULL)   // Базовый случай
    {
       return;
    }
    preorderPrint(root->left);   //рекурсивный вызов левого поддерева
    preorderPrint(root->right);  //рекурсивный вызов правого поддерева
    cout << root->data << " ";
}
// Функция печатает значения бинарного дерева поиска в обратном порядке.
// Не путайте обратный и обратноотсортированный (обратный симметричный).

void reverseInorderPrint(TreeNode *root)
{
    if (root == NULL)   // Базовый случай
    {
       return;
    }
    preorderPrint(root->right);  //рекурсивный вызов правого поддерева
    cout << root->data << " ";
    preorderPrint(root->left);   //рекурсивный вызов левого поддерева

}
// Функция печатает значения бинарного дерева поиска в обратном симметричном порядке.
// То есть в обратном отсортированном порядке

void iterativePreorder(TreeNode *root)
{
    if (root == NULL)
    {
       return;
    }
    stack<TreeNode *> s;  // Создаем стек
    s.push(root);  // Вставляем корень в стек
    /* Извлекаем из стека один за другим все элементы.
       Для каждого извлеченного делаем следующее
       1) печатаем его
       2) вставляем в стек правого! потомка
          (Внимание! стек поменяет порядок выполнения на противоположный!)
       3) вставляем в стек левого! потомка */
    while (s.empty() == false)
    {
        // Извлекаем вершину стека и печатаем
        TreeNode *temp = s.top();
        s.pop();
        cout << temp->data << " ";

        if (temp->right)
            s.push(temp->right); // Вставляем в стек правого потомка
        if (temp->left)
            s.push(temp->left);  // Вставляем в стек левого потомка
    }
}
// В симметричном и обратном итеративном обходах просто меняем инструкции
// местами по аналогии с рекурсивными функциями.

Надеюсь Вы не уснули, и статья была полезна. Скоро надеюсь последует продолжение

банкета

статьи.

Курс по структурам данных: https://stepik.org/a/134212

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

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

Начальная
вершина дерева, от которого следуют все остальные, называется корнем дерева
(root). Сами элементы
дерева – узлами или вершинами (nodes). Причем, узел
слева, называется левым, а справа – правым. Если у вершины нет
левого или правого потомка, то обычно указывают значение NULL. Вершины, у
которых нет потомков, называются листьями. Само же дерево, у которого
каждая вершина может содержать не более двух дочерних узлов, называется бинарным
или двоичным. Всю эту терминологию и обозначения, мы в дальнейшем
будем активно использовать.

Структура бинарного дерева

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

Каждая вершина
такого дерева содержит, как минимум, три поля:

• data – данные,
  хранимые в вершине дерева;

• left – ссылка
  (указатель) на потомка слева;

• right – ссылка
  (указатель) на потомка справа.

Иногда еще
добавляют ссылку на родительский узел. Но чаще всего ограничиваются этими тремя
полями.

На вершину
дерева, которая называется корнем, ведет указатель root. И через этот
указатель происходит вся работа с бинарным деревом: добавление/удаление
элементов; обход всех узлов дерева. То есть, из корневого узла можно пройти до
любого другого в данном дереве. При этом, количество вершин, через которые
нужно пройти, чтобы достичь некоторого узла, определяет уровень (level) дерева. Если
дерево не содержит ни одной вершины, то root = NULL. Также, если у
какой-либо вершины отсутствует левый или правый потомок, то соответствующий
указатель принимает значение NULL.

Добавление вершин в бинарное дерево

Давайте теперь
посмотрим, как можно формировать бинарное дерево, то есть, добавлять в него
новые вершины. Обычно, новые узлы добавляются к свободному указателю (то есть,
тот, который принимает значение NULL), начиная с корневого. То есть, первая
вершина всегда добавляется в корень, и других вариантов просто нет. А вот
далее, мы уже решаем добавить левый или правый узел. Строго говоря, ограничений
здесь никаких нет. Алгоритм добавления может быть самым разным, исходя из
поставленной задачи. Например, если нам нужно сформировать генеалогическое
древо, то, очевидно, в вершинах последовательно должны указываться потомки: на
нулевом уровне – некоторый человек; на первом – мама, папа; на втором –
бабушки, дедушки и т.д. Но есть отдельный класс задач, когда в вершинах
бинарного дерева хранятся данные, которые можно сравнивать на больше и меньше
(например, числа), и добавление нового узла происходит по правилам:

• если добавляемое
  значение меньше значения в родительском узле, то новая вершина добавляет в
  левую ветвь, иначе – в правую;

• если добавляемое
  значение уже присутствует в дереве, то оно игнорируется (то есть, дубли
  отсутствуют).

Например,
предположим, мы собираемся хранить в вершинах бинарного дерева целые числа. И
будем последовательно добавлять узлы для значений:

10, 5, 7, 16,
13, 2, 20

Первое значение
10 просто добавляется в корневую вершину. Следующее значение 5. Смотрим от
корня. Пять меньше 10. Тогда, согласно нашим правилам, это значение нужно
записать в левую ветвь. Формируем новый узел со значением 5. Следующее значение
7. Снова идет от корня дерева. Семь меньше 10, переходим в левую ветвь. Здесь у
нас узел со значением 5. И пять больше 7. Следовательно, семь нужно добавить в
качестве правого узла дерева у вершины 5. Далее, идет число 16. Оно больше 10,
поэтому добавляем его в качестве правой вершины у корневой. Затем, число 13.
Оно также больше 10, но меньше 16. Следовательно, нужно добавить левый узел у
вершины 16. Следующее значение 2 меньше 10 и меньше 5. Добавляем новый узел
справа от узла 5. И последнее значение 20 – самое большое, поэтому оно станет
самой крайней правой вершиной дерева.

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

Поиск значений в бинарном дереве

Хорошо, но что
нам это дает? Смотрите, здесь появляется несколько интересных эффектов. Первый
– это ускорение поиска заданного значения. Например, нам нужно определить,
находится ли число 2 в последовательности чисел 10, 5, 7, 16, 13, 2, 20. Если
бы мы хранили числа в обычном массиве:

то время поиска,
с точки зрения O большого, составило бы O(n), где n – число
элементов в массиве. Нам пришлось бы последовательно перебирать все элементы и
сравнивать значения с числом 2.

А вот в бинарном
дереве все несколько иначе и, в среднем, быстрее. Вначале число 2 сравнивается
с числом 10. Оно меньше, поэтому идем по левой ветви, где сосредоточены вершины
со значениями меньше 10. В результате, мы сразу отсекаем правую группу
элементов, значения которых заведомо не равны 2. За счет этого происходит
ускорение поиска. Затем, сравниваем 2 и 5. И, так как 2 меньше 5, то снова
переходим по левой ветви. Находим заданное значение. Как видите, нам
потребовалось всего три сравнения, чтобы найти число 2 в бинарном дереве. С
позиции О большого среднее число операций, необходимое для поиска нужного значения
составляет . И это
значительно быстрее, чем линейный поиск в массивах или связных списках.

Давайте теперь
посмотрим на работу алгоритма в случае, когда заданное значение для поиска в
бинарном дереве отсутствует. Например, это число 11. Очевидно, мы должны идти
сначала по правой ветви, в узле 16 – по левой, и доходим до листовой вершины
13. Далее, никаких узлов в дереве нет, но значение не было найдено,
следовательно, в дереве нет этого числа 11.

Или, такой
пример. Нам нужно найти число 5. Оно хранится в промежуточной вершине. Поэтому,
когда мы доходим до нее, то дальнейший процесс поиска прерывается, значение
найдено. Вот принцип, по которому выполняется поиск значений в вершинах
бинарного дерева.

Сбалансированные и несбалансированные деревья

Внимательный
зритель сейчас мог бы мне возразить и сказать, что у нас все так хорошо
получается, потому что я привел пример «красивого» бинарного дерева с минимальным
числом уровней (всего два):

Но, если бы
числа при формировании дерева поступали в другом порядке, или по возрастанию:

2, 5, 7, 10, 13,
16, 20

или по убыванию:

20, 16, 13, 10,
7, 5, 2

то деревья
выглядели бы совсем иначе:

Фактически, они
вырождаются в односвязный список и объем вычислений для поиска заданного
значения в них составляет O(n). Так же, как и
в обычных массивах или связных списках. Выигрыша уже нет.

Такие
вырожденные деревья (и подобные им) называются несбалансированными. В
отличие от первого, которое относится к сбалансированным.

Вообще, дерево
называется сбалансированным, если в нем поддеревья от одной вершины отличаются
не более чем на один уровень. И именно в сбалансированных деревьях поиск
значений в вершинах выполняется за минимальное число шагов с объемом вычислений
O(log n). Поэтому, на
практике, стремятся строить деревья близкие к сбалансированным. Для этого
используют методы балансировки двоичных деревьев, среди которых, наиболее
известны следующие:

• АВЛ-дерево (AVL tree), разработан в
  1968 году;

• красно-черное
  дерево (red-black tree), разработан в
  1972 году;

• расширяющееся
  или косое дерево (splay tree), разработан в
  1983 году.

Любой из этих
методов может быть реализован в бинарном дереве и вызываться при добавлении новых
вершин. В результате получаем более сбалансированное дерево при любых входных
последовательностях данных. В данном курсе мы не будем углубляться в эти темы.
Кому будет интересно, подробную информацию по этим методам легко найти на
просторах Интернета. Отмечу только, что если нам известно, что в решаемой
задаче данные (значения) поступают в случайном порядке, то в среднем, будет
формироваться бинарное дерево близкое к сбалансированному.

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

Курс по структурам данных: https://stepik.org/a/134212

Напомним свойства бинарных деревьев:

В этом случае структура узла принимает следующий вид:

class BinaryTreeNode {
  constructor(value, parent) {
    this.left = null; //ссылка на левый дочерний узел
    this.right = null; //ссылка на правый дочерний
    this.parent = parent; //ссылка на родителя
    this.value = value; //полезная нагрузка
  }
}

Java

class BinaryTreeNode {
    public BinaryTreeNode left = null;
    public BinaryTreeNode right = null;
    public BinaryTreeNode parent;
    public Object value;

    BinaryTreeNode(Object value, BinaryTreeNode parent) {
        this.parent = parent;
        this.value = value;
    }
}

Python

class BinaryTreeNode:
    def __init__(self, value, parent=None):
        self.left = None  # ссылка на левый дочерний узел
        self.right = None  # ссылка на правый дочерний узел
        self.parent = parent  # ссылка на родителя
        self.value = value  # полезная нагрузка

Теперь нам необходимо расширить наш класс и реализовать необходимые операции, чтобы взаимодействовать с проектируемым классом. Начнем с операции поиска узла.

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

Разберем каждую операцию подробнее.

function findNode(value){
  let node = this;
  while (node){
    if (value == node.value) return node;
    if (value < node.value) node = node.left;
    if (value > node.value) node = node.right;
  }

  return null;
}

class BinaryTreeNode {
    // ...

    BinaryTreeNode findNode(int value) {
        BinaryTreeNode node = this;
        while (node != null) {
            if (value == node.value) {
                return node;
            }
            if (value < node.value) {
                node = node.left;
            }
            if (value > node.value) {
                node = node.right;
            }
        }

        return null;
    }
}

def find_node(self, value):
    node = self
    while node:
        if value == node.value:
            return node
        if value < node.value:
            node = node.left
        if value > node.value:
            node = node.right
    return None

function insertNode(value){
  return #insertNode(value, this)
}

function #insertNode(value, parentNode){
  if (value < parentNode.value){
    if (parentNode.left == null){
      parentNode.left = new BinaryTreeNode(value, parentNode);
    }
    else {
      #insertNode(value, parentNode.left);
    }
  }
  if (value > parentNode.value){
    if (parentNode.right == null){
      parentNode.right = new BinaryTreeNode(value, parentNode);
    }
    else {
      #insertNode(value, parentNode.right);
    }
  }
}

class BinaryTreeNode {
    // ...

    public void insertNode(int value) {
        insertNode(value, this);
    }

    private void insertNode(int value, BinaryTreeNode parentNode) {
        if (value < parentNode.value) {
            if (parentNode.left == null) {
                parentNode.left = new BinaryTreeNode(value, parentNode);
            } else {
                insertNode(value, parentNode.left);
            }
        }
        if (value > parentNode.value){
            if (parentNode.right == null){
                parentNode.right = new BinaryTreeNode(value, parentNode);
            } else {
                insertNode(value, parentNode.right);
            }
        }
    }
}

def insert_node(self, value):
    return self._insert_node(value, self)

def _insert_node(self, value, parent_node):
    if value < parent_node.value:
        if parent_node.left is None:
            parent_node.left = BinaryTreeNode(value, parent_node)
        else:
            self._insert_node(value, parent_node.left)
    elif value > parent_node.value:
        if parent_node.right is None:
            parent_node.right = BinaryTreeNode(value, parent_node)
        else:
            self._insert_node(value, parent_node.right)

function removeNode(value){
  return #removeNode(value, this)
}

function #removeNode(value, node){
  if (node == null) return null;

  if (value < node.value) {
    node.left = #removeNode(node.left, value);
  }
  else if (value > node.value){
    node.right = #removeNode(node.right, value);
  }
  else{
    if (node.left == null) return node.right;
    if (node.right == null) return node.left;
  }

  let original = node;
  node = node.right;
  while (node.left){
    node = node.left;
  }

  node.right = #removeMin(original.right);
  node.left = original.left;
}

class BinaryTreeNode {
    // ...

    private BinaryTreeNode removeNode(int value, BinaryTreeNode node) {
        if (node == null) {
            return null;
        }

        if (value < node.value) {
            node.left = removeNode(value, node.left);
        }
        else if (value > node.value) {
            node.right = removeNode(value, node.right);
        }
        else{
            if (node.left == null) {
                return node.right;
            }
            if (node.right == null) {
                return node.left;
            }
        }

        BinaryTreeNode original = node;
        node = node.right;
        while (node.left != null){
            node = node.left;
        }

        node.right = removeNode(original.right);
        node.left = original.left;
        return node.right;
    }
}

def remove_node(self, value):
    return self._remove_node(value, self)

def _remove_node(self, value, node):
    if node is None:
        return None

    if value < node.value:
        node.left = self._remove_node(value, node.left)
        return node
    elif value > node.value:
        node.right = self._remove_node(value, node.right)
        return node
    else:
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        else:
            original = node
            node = node.right
            while node.left:
                node = node.left
            node.right = self._remove_min(original.right)
            node.left = original.left
            return node

function traverseRecursive(node) {
  if (node != null) {
         console.log(`node = ${node.val}`);
         traverseRecursive(node.left);
         traverseRecursive(node.right);
     }
}

function traverseWithStack() {
  let stack = [];
  stack.push(this);
	while (stack.length > 0) {
		let currentNode = stack.pop();

		console.log(`node = ${currentNode.val}`);
		if (currentNode.right != null) {
			stack.push(currentNode.right);
		}
		if (currentNode.left != null) {
			stack.push(currentNode.left);
		}
	}
}

function traverseWithQueue() {
  let queue = [];
	queue.push(this.root);
	while (queue.length > 0) {
		let currentNode = queue.shift();
		console.log(`node = ${currentNode.val}`);
		if (currentNode.left){
			queue.push(currentNode.left);
		}
		if (currentNode.right) {
			queue.push(currentNode.right);
		}
	}
}

class BinaryTreeNode {
    // ...

    public void traverseRecursive() {
        traverseRecursive(this);
    }

    private void traverseRecursive(BinaryTreeNode node) {
        if (node != null) {
            System.out.println("node = " + node.value);
            traverseRecursive(node.left);
            traverseRecursive(node.right);
        }
    }

    public void traverseWithStack() {
        Deque<BinaryTreeNode> stack = new ArrayDeque<>();
        stack.push(this);
        while (stack.size() > 0) {
            BinaryTreeNode currentNode = stack.pop();

            System.out.println("node = " + currentNode.value);

            if (currentNode.right != null) {
                stack.push(currentNode.right);
            }
            if (currentNode.left != null) {
                stack.push(currentNode.left);
            }
        }
    }

    public void traverseWithQueue() {
        Deque<BinaryTreeNode> queue = new ArrayDeque<>();
        queue.push(this);
        while (queue.size() > 0) {
            BinaryTreeNode currentNode = queue.removeFirst();
            System.out.println("node" + currentNode.value);
            if (currentNode.left != null ){
                queue.push(currentNode.left);
            }
            if (currentNode.right != null) {
                queue.push(currentNode.right);
            }
        }
    }
}

def traverse_recursive(node):
    if node is not None:
        print(f"node = {node.value}")
        traverse_recursive(node.left)
        traverse_recursive(node.right)

def traverse_with_stack(root):
    stack = []
    stack.append(root)
    while len(stack) > 0:
        current_node = stack.pop()
        print(f"node = {current_node.value}")
        if current_node.right is not None:
            stack.append(current_node.right)
        if current_node.left is not None:
            stack.append(current_node.left)

def traverse_with_queue(root):
    queue = []
    queue.append(root)
    while len(queue) > 0:
        current_node = queue.pop(0)
        print(f"node = {current_node.value}")
        if current_node.left:
            queue.append(current_node.left)
        if current_node.right:
            queue.append(current_node.right)

A binary tree is a tree data structure in which each node can have at most two children, which are referred to as the left child and the right child. 

The topmost node in a binary tree is called the root, and the bottom-most nodes are called leaves. A binary tree can be visualized as a hierarchical structure with the root at the top and the leaves at the bottom.

Binary trees have many applications in computer science, including data storage and retrieval, expression evaluation, network routing, and game AI. They can also be used to implement various algorithms such as searching, sorting, and graph algorithms.

Representation of Binary Tree:

Each node in the tree contains the following:

• Data
• Pointer to the left child
• Pointer to the right child

In C, we can represent a tree node using structures. In other languages, we can use classes as part of their OOP feature. Below is an example of a tree node with integer data.

Basic Operations On Binary Tree:

• Inserting an element.
• Removing an element.
• Searching for an element.
• Deletion for an element.
• Traversing an element. There are four (mainly three) types of traversals in a binary tree which will be discussed ahead.

Auxiliary Operations On Binary Tree:

• Finding the height of the tree
• Find the level of the tree
• Finding the size of the entire tree.

Applications of Binary Tree:

• In compilers, Expression Trees are used which is an application of binary trees.
• Huffman coding trees are used in data compression algorithms.
• Priority Queue is another application of binary tree that is used for searching maximum or minimum in O(1) time complexity.
• Represent hierarchical data.
• Used in editing software like Microsoft Excel and spreadsheets.
• Useful for indexing segmented at the database is useful in storing cache in the system,
• Syntax trees are used for most famous compilers for programming like GCC, and AOCL to perform arithmetic operations.
• For implementing priority queues.
• Used to find elements in less time (binary search tree)
• Used to enable fast memory allocation in computers. 
• Used to perform encoding and decoding operations.
• Binary trees can be used to organize and retrieve information from large datasets, such as in inverted index and k-d trees.
• Binary trees can be used to represent the decision-making process of computer-controlled characters in games, such as in decision trees.
•  Binary trees can be used to implement searching algorithms, such as in binary search trees which can be used to quickly find an element in a sorted list.
• Binary trees can be used to implement sorting algorithms, such as in heap sort which uses a binary heap to sort elements efficiently.

Binary Tree Traversals:

Tree Traversal algorithms can be classified broadly into two categories:

• Depth-First Search (DFS) Algorithms
• Breadth-First Search (BFS) Algorithms

Tree Traversal using Depth-First Search (DFS) algorithm can be further classified into three categories:

• Preorder Traversal (current-left-right): Visit the current node before visiting any nodes inside the left or right subtrees. Here, the traversal is root – left child – right child. It means that the root node is traversed first then its left child and finally the right child.
• Inorder Traversal (left-current-right): Visit the current node after visiting all nodes inside the left subtree but before visiting any node within the right subtree. Here, the traversal is left child – root – right child.  It means that the left child is traversed first then its root node and finally the right child.
• Postorder Traversal (left-right-current): Visit the current node after visiting all the nodes of the left and right subtrees.  Here, the traversal is left child – right child – root.  It means that the left child has traversed first then the right child and finally its root node.

Tree Traversal using Breadth-First Search (BFS) algorithm can be further classified into one category:

• Level Order Traversal:  Visit nodes level-by-level and left-to-right fashion at the same level. Here, the traversal is level-wise. It means that the most left child has traversed first and then the other children of the same level from left to right have traversed. 

Let us traverse the following tree with all four traversal methods:

Pre-order Traversal of the above tree: 1-2-4-5-3-6-7
In-order Traversal of the above tree: 4-2-5-1-6-3-7
Post-order Traversal of the above tree: 4-5-2-6-7-3-1
Level-order Traversal of the above tree: 1-2-3-4-5-6-7

Implementation of Binary Tree:

Let us create a simple tree with 4 nodes. The created tree would be as follows. 

Below is the Implementation of the binary tree:

Conclusion:

Tree is a hierarchical data structure. Main uses of trees include maintaining hierarchical data, providing moderate access and insert/delete operations. Binary trees are special cases of tree where every node has at most two children.

What else can you read?

• Properties of Binary Tree
• Types of Binary Tree

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.