Бинарное дерево — проще чем кажется

Знакомиться с бинарным деревом обычно очень сложно тем, кто совсем недавно начал изучать азы программирования. На самом деле обычное бинарное дерево строится достаточно просто, и надо бы руки поотрывать тем, кто то и делает, что путает начинающих программистов. Признаюсь честно — это не первая моя попытка описать бинарное дерево, но эта попытка всем моим попыткам попытка, и поэтому я постараюсь пояснить всё так, чтобы даже далёкий от идеала студент был способен осилить эту тему в начале. Меня вот тоже "черти" попутали, и я плохо понимал описываемую сейчас тему.
Чтобы понимать тему "бинарное дерево", нужно понимать основы рекурсии, хорошо знать матчасть об указателях и знать про передачу аргументов в функции. Я стараюсь не усложнять и показываю пример не совсем мой. Несмотря на то, что пример не мой, мне он дал хорошо понял, что тут где и зачем оно надо.
То первое, что нужно для создания бинарного дерева, — это структура с некоторыми определёнными полями. Я буду использовать 3 поля: 1 элемент и два адресных поля. Элемент — это то, что я хочу записать в узел дерева, а два адресных поля — это потому, что у бинарного дерева каждое звено по мере необходимости порождает два новых звена. Обычно такие порождения называют левым и правым звеном.
Чтобы было понятнее, вот кусок кода, о котором я разглагольствовал:


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

  1. Если дерева нет, то нужно заложить семечко для роста.
  2. Если же дерево уже есть, то нужно записывать данные либо влево, либо вправо.

Когда я писал о трёх частях, имел в виду, что запись влево — это одна часть кода, а запись вправо — другая. Вот внутри функции добавления элемента как раз будут использованы все три основные части + кое что ещё. Хватит мне болтать, а то мозг вам, наверное, и без меня выносят. Приступаю к написанию кода.

Сделаю небольшое отступление. Прошу обратить внимание, что я не стал выделять память сейчас. Сейчас просто объявлен один указатель, и во избежание ошибок этот указатель я сразу инициализировал нулевым адресом, чтобы обозначить его направленность вникуда.
==========================================
Шаг второй:
==========================================
Сейчас я сразу опишу функцию обхода. Ведь я всё-таки изначально хотел смотреть, как работает вывод дерева на экран. Да и потом так будет просто как-то нагляднее. Я использую рекурсию для обхода, потому что это намного проще, чем сейчас использовать обычные циклы.

Код постепенно растёт, но надеюсь ничего сложного я не демонстрирую. Если сделать из показанного в листинг #2 кода программу и запустить её, то ничего не будет. Всё это логично, потому что мы ничего для дерева и не описывали: не создавали звеньев. Звенья не добавлялись, а значит и выводить совсем нечего. Но сейчас начнётся самый интересный и ожидаемый момент: добавление звеньев в бинарное дерево.
==========================================
Шаг третий. Добавляем звенья в бинарное дерево:
==========================================

Я не буду переписывать три раза код, а сосредоточусь на функции добавления. Буду дописывать то, что там нужно и пояснять. Сейчас было заложено семечко, должен возникнуть вопрос, каким образом правильно заполнять левые звенья и правые. В моём примере будет использована рекурсия. Заполнение левого и правого поддерева аналогичны друг другу. Очень важно понять сам принцип.

Попробуйте понять принцип. Он не очень сложен. Сейчас создаётся дерево и данные записываются в левое поддерево, но осталось дописать и для правого. Для записи данных в правое поддерево нужно использовать такую же схему как и для записи в левое, только поменять условие и нужно обращаться уже к правым подзвеньям. Я очень советую обратить внимание на момент в рекурсии, какой там параметр указан. Внимательно посмотрите, чтобы потом не искать ошибку при своих попытках написать подобный код.
Доделываем недоделанное, дописываем код работы с правым поддеревом:

Такая функция добавления элемента в дерево вышла.
Маленькой совсем не кажется, но с моей точки зрения достаточно простая и удобная для понимания. Полный код описываемого примера даётся в листинге #4, но очень настоятельно советую почитать текст после приведённого кода, а не ограничиться показанным кодом.

Конечно, тут нет функций удаления, вставки звеньев между звеньями и вообще много чего нет. Да и я не освободил память — а это важно, и это ошибка! Память надо освобождать. Но моя задача сейчас была продемонстрировать элементарное доступным и понятным языком, языком обычных смертных, и я надеюсь, что это у меня получилось. Память освобождается почти также, как выполняется обход.
Казалось бы, что листинг #4 удачен, всё работает. Нет, это было бы наивно. Есть большой, огромный, гигантский недостаток. Тут выделяется память с помощью new. А есть ли хоть одно delete? — нет! Следовательно, мы имеем утечку памяти. Конечно, если не делать программу с деревом, а просто использовать тему для демонстрации дерева, утечки может и не будет заметно. Менеджеры памяти ОС почистят память по завершению работы программы, но если дерево только часть большого кода, то тут уже утечки могут проявиться во всей красе. Есть правило, что где new, там delete. Они работают только в паре. Поэтому более верный код выглядит так:


Ещё более правильно описывать дерево с помощью классов. Поскольку в показанном коде очистку памяти надо каждый раз зазывать вручную, то иной раз можно прозевать момент нужности подчистки. При написании классов от необходимости ручного удаления можно избавиться при помощи деструктора. Деструктор такая же функция, как и обычные, но умеет самовызываться в нужный момент. Но при написании классов нужно будет учитывать обязательность написания кроме деструктора — конструктора по умолчанию, конструктора копирования и операции присваивания (а с С++11 ещё и конструктора перемещения и операцию присваивания перемещением). Поэтому на классах описывается чуть сложнее, но зато преимущество в удобстве использования хорошее получается.

34 комментария на «“Бинарное дерево — проще чем кажется”»

  1. Аноним:

    А как рекурсивно заполнить N-нарное дерево? Например где структура имеет вид

    6
    6
  2. Артём:

    А чем плохо если код так сократить? У меня вроде как корректно работает. И более читабельно.

    немножко код побился, но суть думаю ясна
    Вопрос снимается
    в этой статье как раз такой код и дан (http://ci-plus-plus-snachala.ru/?p=89)

    3
    4
  3. Alex:

    Все просто, если без &, то в функции ты будешь работать с копией дерева, а если с ним, то передаешь наше дерево и будешь работать всегда с одним и тем же.

    Автор сайта отвечает:

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

  4. Аноним:

    😆 😆 😆 😆

  5. Игорь:

    А как можно реализовать добавление нового элемента в бинарное дерево без рекурсии ?
    Ни как не могу сообразить

    Автор сайта отвечает:
    это сложнее делается чем с рекурсией.
    я сейчас не могу ответить на этот вопрос.

  6. Дмитрий:

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

  7. Дмитрий:

    Спасибо вам огромное! Буду разбираться, ибо для меня указатели — темный лес)

  8. Андрей:

    в бинарному дереве кроме укзателей левого і правого есть указатель на предидущий елемент, а здесь у вас двосвязний список
    :mrgreen: :mrgreen: :mrgreen: :mrgreen:

    а здесь реальное дерево нода которого реализована в виде стуктури с констуктором і деструктором а также клас словарь в котором лежит указатель на само дерево

    Автор сайта отвечает:
    У меня — бинарное дерево.
    У вас класс "Словарь" непонятно к чему нужный. дерева у вас нет.

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

    Автор сайта отвечает:
    ну ну.

  9. Arete:

    Это двусвязный список а не бинарное дерево, в узла дерева должен быть указатель на родительский узел.

    Автор сайта отвечает:
    Не обязательно

    Извините, стормозил. Это все таки дерево, а не двусвязных список. У двусвязного списка левый элемент узла Х ссылается обратно на узел Х своим “правым” элементом. И действительно, для дерева ссылка на родительский узел не обязательна.

    З.Ы.

    Спасибо за ваши труды 🙂

  10. Андрей:

    Спасибо за статью. Все супер растолковано, без лишней болтовни. Как раз для новичков.

  11. Дима:

    таки пример изложенный в статье это бинарное дерево или двусвязный список?

    Автор сайта отвечает:
    Бинарное дерево.

  12. DanMan:

    Привет! Спасбо за статью. С дереом более-мение, а вот с рекурсией — увы. Читал примеры со степенью и факториалом, а понять так и не смог. Вы случаем не публиковали статью о рекурсии в стиле данного бинарного дерева? Или подскажите, где можно почитатьть про рекурсии, так сказать, для дебилов ? =)

    Автор сайта отвечает:
    Для меня наиболее удачное объяснение скорее всего по ссылке:
    Рекурсия. Пример работы с натуральным числом
    Я тоже по Фиббоначи, факториалу и степени не понимал рекурсию.
    Если чертить схему, то все может стать очень запутано. Слишком много стрелочек начало вызова — возврат к началу вызова. Хотя и не пробовал.

  13. DanMan:

    Еще такой вопрос: в вашем примере числа, передаваемые в бинарное дерево, уникальны(от 5 до 1 без повторений). Если числа будут повторятся? При использовании функции rand()?Как тогда помещать значения?

    Пример:

    Автор сайта отвечает:
    Бинарные деревья, как правило, используют для поиска. В большинстве случаев наличие неуникальных элементов не имеет смысла. Как бы незачем строить большое ответвление если в этом ответвлении все значения представляют собой одно и то же значение, ведь при поиске будет (нами должно быть) задействовано только первое.

  14. Денис:

    Подскажите, а как можно узнать значение самого дальнего элемента по переходам?

    • Я сейчас не смогу подсказать. Простите уж.

      • Денис:

        Накопал-таки что-то похожее, работает исправно.
        Как только что-то прочитать — я могу, сам рекурсию написать не могу — не тот видимо склад ума(:

        • Вопрос времени и опыта.
          Я давно эту тему описывал и многое не помню. Хотя и сам плохо ориентриовался и сейчас плохо ориентируюсь. Если бы я мог, то подсказал бы обязательно.
          Спасибо, что поделились тем, что нашли. Может быть в будущем тоже кому-то пригодится.

  15. VikThor:

    Чтобы очистить память надо просто указателю на корень присвоить null

  16. Артур:

    Здравствуйте а как можно создать копию дерева? И как сделать что бы количество листьев, о которых вы писали, можно было посчитать и вывести это все на экран?

    Автор сайта отвечает:
    Листья дерева

  17. Жора:

    а как с помощью этого дерева определить встречается ли в тексте слово ??

    помогите пожалуйста

    • 1. Заполнить дерево словами. Для этого нужно разбить текст на слова и каждое считанное из текста слово добавлять в дерево.
      2. Описать дополнительную функцию проверки узла с выбранным словом.
      Самая сложная часть — разбиение текста на слова.
      Что пробовали, что есть и что не получается?

  18. Павел:

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

    Точнее чтобы дерево было ввиде дерева на консоли.Заранее спасибо.

    // Tree.cpp : Defines the entry point for the console application.
    //

    #include «stdafx.h»
    #include «iostream»

    using namespace std;

    struct Node
    {
    int x;//x-Число которое я буду записывать в дерево
    Node *left, *right;//Адресные поля на новые звенья

    };
    void show(Node *Tree)//Функция обхода
    {
    if (Tree != NULL)//Пока не встретится пустое зерно
    {
    show(Tree->left);//Рекурсивная функция для вывода левого поддерева//Доступ к члену структуры через указатель.
    cout << Tree->x;//Отображаем корень дерева
    show(Tree->right); //Рекурсивная функци для вывода правого поддерева
    }
    }

    /*Добавили очистку памяти*/
    void del(Node *&Tree)
    {
    if (Tree != NULL)//Пока не встретится пустое звено
    {
    del(Tree->left);//Рекурсивная функция прохода по левому поддереву
    del(Tree->right);//Рекурсивная функци для прохода по правому поддереву
    delete Tree; //Убиваем конечный элемент дерева
    Tree = NULL;//Может и не обязательно, но плохого не будет
    }
    }

    void add_node(int x, Node *&MyTree)//Функция добавления звена в дерево
    {
    if (NULL == MyTree)//Если дерева нет, то сеем семечко
    {
    MyTree = new Node; //Выделяем память под звено дерева
    MyTree->x = x; //Записываем данные в звено
    MyTree->left = MyTree->right = NULL;//Подзвенья инициализируем пустотой во избежание ошибок

    if (x < MyTree->x)
    {
    if (MyTree->left != NULL) add_node(x, MyTree->left); //При помощи рекурсии заталкиваем элемент на свободный участок
    else
    {
    MyTree->left = new Node;//Выделяем память левому подзвену. Именно подзвену, а не просто звену
    MyTree->left->left = MyTree->left->right = NULL;//У левого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой
    MyTree->left->x = x;//Записываем в левое подзвено записываемый элемент
    }

    if (x > MyTree->x)
    {
    if (MyTree->right != NULL) add_node(x, MyTree->right);
    else
    {
    MyTree->right = new Node;
    MyTree->right->left = MyTree->right->right = NULL;
    MyTree->right->x = x;
    }
    }
    }
    }
    }

    int main()
    {
    int a = 0;
    Node *Tree = NULL;//Создаю указатель, тип которого = звено дерева и иницилизирую его пустотой
    cout << «Vvedite chislo» << endl;
    for (int i = 0; i < 5; i++) {
    cin >> a;
    add_node(a, Tree);//Я решил так заполнять
    }

    show(Tree); //Показываем копию
    del(Tree); //Чистим память от копии
    system(«pause»);
    return 0;
    }

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

  19. Павел:

    Я не знаю как вывести его на экран:(

  20. Ирина:

    Отличная статья, спасибо огромное.

    Весь инет перерыла чтобы понять что за «постройте дерево» у меня в методичке.

    А оказалось все просто.

  21. Аноним:

    Долбаеб, у тебя выводит 12345 постоянно, сотри нахуй свой материал!

    20
  22. Аноним:

    😎 😎 😎

  23. Аноним:

    помогите пожалуйцта, вывести на екран информацию из самого узла бинарного дерева.(рекурсивно,итеративно)

  24. igor:

    void push(int a, node **t) на предыдущей странице должен быть представлен как *& же, и на этой void show(Node *&Tree) можно записать как *Tree, все равно изменений не производится

  25. NashelOshibku:

    Уважаемый автор! Ошибка найдена в листинге! прошу исправить это недоразумение!
    В функции добавления элемента в дерево Вы не учитываете того, что вводимые данные могут быть равными!
    К примеру, если передать массив из 10 единиц то дерево заполнится всего лишь одной единицей!

    • Здесь это не ошибка. Точное название описанного дерева «бинарное дерево поиска». Сама архитектура этого дерева такова, что если элемент уже есть, то он не добавляется, поскольку итак понятно, что если элемент есть, то при поиске такой элемент будет найдет. Не имеет смысла добавлять одно и то же, бесполезно увеличивая размер дерева.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/kevin-yank-2/php-i-mysql-ot-novichka-k-professionalu-2/?lfrom=15589587
Яндекс.Метрика