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

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

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

Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны 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);  // Вставляем в стек левого потомка
    }
}
// В симметричном и обратном итеративном обходах просто меняем инструкции
// местами по аналогии с рекурсивными функциями.

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

банкета

статьи.

В этом уроке вы узнаете о разных типах двоичных деревьев и увидите, как их можно реализовать на Си, C++, Java и Python.

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

Типы двоичных деревьев

Полное двоичное дерево

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

Совершенное двоичное дерево

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

Законченное двоичное дерево

Законченное двоичное дерево похоже на совершенное, но есть три большие отличия.

1. Все уровни должны быть заполнены.
2. Все листовые вершины склоняются влево.
3. У последней листовой вершины может не быть правого собрата. Это значит, что завершенное дерево необязательно полное.

Вырожденное двоичное дерево

Вырожденное двоичное дерево — дерево, в котором на каждый уровень приходится по одной вершине.

Скошенное вырожденное дерево

Скошенное вырожденное дерево — вырожденное дерево, в котором есть либо только левые, либо только правые узлы. Таким образом, есть два типа скошенных деревьев — скошенные влево вырожденные деревья и скошенные вправо вырожденные деревья.

Сбалансированное двоичное дерево

Сбалансированное двоичное дерево — тип бинарного дерева, в котором у каждой вершины количество вершин в левом и правом поддереве различаются либо на 0, либо на 1.

Представление двоичного дерева

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

struct node
{
 int data;
 struct node *left;
 struct node *right;
};

Примеры реализации

Python

# Двоичное дерево в Python

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

    # Прямой обход дерева
    def traversePreOrder(self):
        print(self.val, end=' ')
        if self.left:
            self.left.traversePreOrder()
        if self.right:
            self.right.traversePreOrder()

    # Центрированный обход дерева
    def traverseInOrder(self):
        if self.left:
            self.left.traverseInOrder()
        print(self.val, end=' ')
        if self.right:
            self.right.traverseInOrder()

    # Обратный обход дерева
    def traversePostOrder(self):
        if self.left:
            self.left.traversePostOrder()
        if self.right:
            self.right.traversePostOrder()
        print(self.val, end=' ')

root = Node(1)

root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)

print("Прямой обход дерева: ", end="")
root.traversePreOrder()
print("nЦентрированный обход дерева: ", end="")
root.traverseInOrder()
print("nОбратный обход дерева: ", end="")
root.traversePostOrder()

Java

// Двоичное дерево на Java

// Создание узла
class Node {
  int key;
  Node left, right;

  public Node(int item) {
  key = item;
  left = right = null;
  }
}

class BinaryTree {
  Node root;

  BinaryTree(int key) {
  root = new Node(key);
  }

  BinaryTree() {
  root = null;
  }

  // Центрированный обход дерева
  public void traverseInOrder(Node node) {
  if (node != null) {
    traverseInOrder(node.left);
    System.out.print(" " + node.key);
    traverseInOrder(node.right);
  }
  }

  // Обратный обход дерева
  public void traversePostOrder(Node node) {
  if (node != null) {
    traversePostOrder(node.left);
    traversePostOrder(node.right);
    System.out.print(" " + node.key);
  }
  }

  // Прямой обход дерева
  public void traversePreOrder(Node node) {
  if (node != null) {
    System.out.print(" " + node.key);
    traversePreOrder(node.left);
    traversePreOrder(node.right);
  }
  }

  public static void main(String[] args) {
  BinaryTree tree = new BinaryTree();

  tree.root = new Node(1);
  tree.root.left = new Node(2);
  tree.root.right = new Node(3);
  tree.root.left.left = new Node(4);

  System.out.print("Прямой обход дерева: ");
  tree.traversePreOrder(tree.root);
  System.out.print("nЦентрированный обход дерева: ");
  tree.traverseInOrder(tree.root);
  System.out.print("nОбратный обход дерева: ");
  tree.traversePostOrder(tree.root);
  }
}

Си

// Обход дерева на Си

#include <stdio.h>
#include <stdlib.h>

struct node {
  int item;
  struct node* left;
  struct node* right;
};

// Центрированный обход дерева
void inorderTraversal(struct node* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  printf("%d ->", root->item);
  inorderTraversal(root->right);
}

// Прямой обход дерева
void preorderTraversal(struct node* root) {
  if (root == NULL) return;
  printf("%d ->", root->item);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

// Обратный обход дерева
void postorderTraversal(struct node* root) {
  if (root == NULL) return;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  printf("%d ->", root->item);
}

// Создание нового узла
struct node* createNode(value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->item = value;
  newNode->left = NULL;
  newNode->right = NULL;

  return newNode;
}

// Вставка потомка слева от родительской вершины
struct node* insertLeft(struct node* root, int value) {
  root->left = createNode(value);
  return root->left;
}

// Вставка потомка справа от родительской вершины
struct node* insertRight(struct node* root, int value) {
  root->right = createNode(value);
  return root->right;
}

int main() {
  struct node* root = createNode(1);
  insertLeft(root, 2);
  insertRight(root, 3);
  insertLeft(root->left, 4);

  printf("Центрированный обход дереваn");
  inorderTraversal(root);

  printf("nПрямой обход дереваn");
  preorderTraversal(root);

  printf("nОбратный обход дереваn");
  postorderTraversal(root);
}

С++

// Двоичное дерево на С++

#include <stdlib.h>
#include <iostream>

using namespace std;

struct node {
  int data;
  struct node *left;
  struct node *right;
};

// Создание нового узла
struct node *newNode(int data) {
  struct node *node = (struct node *)malloc(sizeof(struct node));
  node->data = data;

  node->left = NULL;
  node->right = NULL;
  return (node);
}

// Прямой обход дерева
void traversePreOrder(struct node *temp) {
  if (temp != NULL) {
    cout << " " << temp->data;
    traversePreOrder(temp->left);
    traversePreOrder(temp->right);
  }
}

// Центрированный обход дерева
void traverseInOrder(struct node *temp) {
  if (temp != NULL) {
    traverseInOrder(temp->left);
    cout << " " << temp->data;
    traverseInOrder(temp->right);
  }
}

// Обратный обход дерева
void traversePostOrder(struct node *temp) {
  if (temp != NULL) {
    traversePostOrder(temp->left);
    traversePostOrder(temp->right);
    cout << " " << temp->data;
  }
}

int main() {
  struct node *root = newNode(1);
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);

  cout << "Прямой обход дерева: ";
  traversePreOrder(root);
  cout << "nЦентрированный обход дерева: ";
  traverseInOrder(root);
  cout << "nОбратный обход дерева: ";
  traversePostOrder(root);
}

Где используется

• Для быстрого доступа к данным.
• В алгоритмах маршрутизации.
• Для реализации куч.
• В синтаксических деревьях.

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.

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

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

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)