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

Пользователь

от maya , в категории: C/C++ , 2 года назад

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

Facebook Vk Ok Twitter LinkedIn Telegram Whatsapp

2 ответа

Пользователь

от cloyd , 2 года назад

@maya 

Вот простой пример создания бинарного дерева на языке C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;

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

Node* newNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

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

    return 0;
}


Этот код создает бинарное дерево со следующей структурой:

1
2
3
     1
   /     2     3
 / 4   5


Функция newNode создает новый узел с заданным значением и нулевыми указателями на левое и правое поддеревья. Затем в функции main создается корневой узел с значением 1 и двумя дочерними узлами со значениями 2 и 3. Затем узел со значением 2 получает двух дочерних узлов со значениями 4 и 5.


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

Пользователь

от francis_schuster , 10 месяцев назад

@maya 

Дополнительная информация:


Помимо создания бинарного дерева, программисты часто работают с бинарным деревом поиска (Binary Search Tree, BST). В BST, значения на левом поддереве меньше значения текущего узла, а значения на правом поддереве больше. Это позволяет эффективно находить, вставлять и удалять элементы, а также выполнять другие операции поиска и сортировки.


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


Если вам интересны более сложные операции с бинарным деревом, вы можете ознакомиться с реализацией алгоритмов глубокого обхода дерева (pre-order, in-order и post-order traversal), поиска наименьшего и наибольшего элемента, а также с методами балансировки дерева, такими как AVL и Красно-черные деревья.