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

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

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

То первое, что нужно для создания бинарного дерева — это структура с некоторыми определенными полями. Я буду использовать 1 элемент и два адресных поля. Элемент — это то, что я хочу записать в узел дерева, а два адресных поля — это потому, что у бинарного дерева каждое звено по мере необходимости порождает два новых звена, обычно их называют левое и правое.

Чтобы было яснее и понятнее вот кусок кода, о котором я разглагольствовал:

То, что я описал — это структура, описывающая звено дерева. По ходу выполнения программы Звенья будут создаваться и дописываться к существующим по указанным нами правилам. Сама эта структура — это фундамент очень простого бинарного дерева.

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

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

Код постепенно растет, но надеюсь ничего сложного я не демонстрирую. Сейчас программа компилируется и запустится. Но ничего не будет. Всё это логично, потому что мы ничего для дерева и не описывали и не создавали звеньев. Собственно, выводить совсем нечего. Но сейчас начнется самый интересный и ожидаемый этап. А именно этап добавления звеньев в Бинарное дерево
=================================
Этап третий. Добавляем звенья в бинарное дерево
=================================

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

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

Доделываем не доделанное и дописываем код для работы с правым поддеревом

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

  • ОБЯЗАТЕЛЬНО ЧИТАТЬ ДАЛЬШЕ КОДА

Конечно тут нет функций удаления, вставки звеньев между звеньями и много чего нет.
Да и Я не освободил память — а это важно и это ошибка, память надо освобождать. Но моя задача сейчас была продемонстрировать элементарное доступным и понятным языком обычных смертных, и я надеюсь это у меня получилось. Память освобождается почти также как выполняется обход, но оставляю это на вас как домашнее упражнение для лучшего понимания. Хороший фундамент должен облегчить дальнейшее понимание сложного материала.
==========================================

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

Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

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

  • Аноним говорит:

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

    struct Tree{
    int x; //Некоторое значение в вершине дерева
    Tree *n[N]; //Массив указателей на потомков (N)
    };

    Автор сайта отвечает:
    я не знаю




    3



    0
  • Артём говорит:

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

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




    0



    0
  • Роман говорит:

    Растолкуйте сочетание *& (void add_node(int node, Node *&Tree)),
    в чем отличие void add_node(int node, Node *&Tree) и void add_node(int node, Node *Tree) и если есть принципиальные различия, то в чем преимущество *&

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

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

     

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

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

     

    Растолкуйте сочетание *& (void add_node(int node, Node *&Tree))
    Не вижу смысла удлинять запись без необходимости. Я так ни в одной теме пример не описывал.
    Может быть это как-то влияет на переносимость или совместимость и пришло из языка Си, но может быть. Здесь я могу быть очень не прав.
    Может быть это так было нужно в старых компиляторах, которые прародители современних.
    Просто потребностей не было использовать такой вид записи.




    0



    0
  • Alex говорит:

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

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

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




    0



    0
  • Аноним говорит:

    😆 😆 😆 😆




    0



    0
  • Игорь говорит:

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

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




    0



    0
  • Дмитрий говорит:

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

    Автор сайта отвечает:
    Ну указатели сами по себе доставляют много проблем.
    По указателям на сайте совсем немного информации, нужно выйти на главную страницу (http://ci-plus-plus-snachala.ru) там в содержании есть несколько тем по указателям. Чтобы попроще найти было Ctr+F3 появится маленькое окошко для ввода текста, ввести указ
    нажать F3 и там будут разные темы (это простой поиск, для поиска F3 = искать дальше)




    1



    0
  • Дмитрий говорит:

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




    0



    0
  • Андрей говорит:

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

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

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

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

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




    0



    0
  • Arete говорит:

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

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

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

    З.Ы.

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




    0



    0
  • Андрей говорит:

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




    0



    0
  • Дима говорит:

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

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




    0



    0
  • DanMan говорит:

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

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




    0



    0
  • DanMan говорит:

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

    Пример:

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




    0



    0
  • Денис говорит:

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




    0



    0
    • admin говорит:

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




      0



      0
      • Денис говорит:

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




        0



        0
        • admin говорит:

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




          0



          0
  • VikThor говорит:

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




    0



    0
  • Артур говорит:

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

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




    0



    0
  • Жора говорит:

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

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




    0



    0
    • admin говорит:

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




      0



      0
  • Павел говорит:

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

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

    // 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;
    }




    0



    0
    • admin говорит:

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




      0



      0
  • Павел говорит:

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




    0



    0
  • Ирина говорит:

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

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

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




    0



    0
  • Аноним говорит:

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




    0



    2

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

Ваш e-mail не будет опубликован.

Поиск

 
     

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

https://www.litres.ru/maykl-neygard/release-it-proektirovanie-i-dizayn-po-dlya-teh-komu-ne-vse-ravno-16901930/?lfrom=15589587
Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Встречает в аду один черт другого и говорит: "Слушай, это ты того компьютерщика сюда притащил?" - "Да, а что?" - "Ты в другой раз толком объясняй, что такое ад - а то он, пока понял, что это не Doom, двести чертей перестрелял..."

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок