С++ для начинающих. Бинарное дерево. Первое знакомство

Моё знакомство с бинарными деревьями начиналось, вероятно, как и у многих из вас: приблизтельно на таком примере, который демонстрируется в этой статье.
Как правило, у начинающих много вопросов и поначалу, но с появлением необходимости программировать динамические структуры вопросов становится значитильно больше, чем было. На момент написания этой темы я изучал С++ в одиночку, и при первых моих попытках понять, что такое бинарное дерево, у меня определённо возникли сложности. Особенно отпугивало слово рекурсия. Мало того, что оказалось достаточно проблематично отыскать простой код с объяснениями, так в большинстве случаев нарисован рисунок и дан код без комментариев.
Я считаю, что для первого знакомства значения в бинарное дерево достаточно вводить посредством клавиатуры и выводить значения на экран. Остальные функции лучше оставить на после изучения такого фундамента. Вполне может быть, что вы намного умнее меня и быстро схватываете, но есть такие люди, которые медленно развиваются, и им избираемый мной подход очень нужен.
Помимо всего только что сказанного, могу добавить, что для меня найденный код (абсолютно без пояснений) оказался подобием удара кулачного бойца для кулачного бойца. Иногда ведь говорят, что такие бойцы разговаривают кулаками; программисты, значит, должны разговаривать исходным кодом.

Первое, на что обращаю внимание, это сама структура Node, которая представляет одно звено нашего будущего дерева. В структуре объявлен информационный элемент и указатели на самую правую и на самую левую часть будущего дерева. Объявляем указатель на нашу структуру (на звено дерева) и во избежание непредвиденных ошибок сразу инициализируем этот указатель указыванием вникуда.
После описания структуры-звена бинарного дерева и объявления на неё указателя, в функции main() пишем стандартные строчки (сколько элементов ввести) и выполняем цикл, на каждом витке которого вводим элемент. Цикл выполняется указанное число раз. При этом нам нужно каждый новый элемент сразу записывать в дерево. С этой целью (записи в дерево) пишем отдельную функцию. В приведенном мной коде написанная функция принимает два параметра. Первый — записываемое значение (сейчас значение — число), второй — указатель на {указатель звена дерева}.
В начале занесения информации двоичное дерево или содержит информацию или еще не заполнялось, поэтому первый шаг — проверка на наличие данных в дереве.
  • Если дерево пустое, то надо создать первый элемент. Этот элемент будет корнем дерева. После создания первого элемента надо выделить память для возможных ветвей.
  • Если дерево что-то содержит, то проверяется условие, согласно которому мы размещаем в дереве элементы.
Вспомним основное определение бинарного дерева:

  • Бинарное дерево — это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причём для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.
При всём этом, если элемент, который мы хотим поместить в дерево, больше чем корневой, то с помощью рекурсивного вызова функции происходит последовательное перемещение элемента в правую часть. Наш элемент прыгает через один как через скакалку пока не найдет своё место. А его место — это то место, где справа элемент или больше чем он сам, или если прыгать больше не через кого. Одним словом "Чехарда". Если записываемый элемент меньше чем корневой, то выполняется такая же "Чехарда", только в левую сторону.
Для того, чтобы отобразить наше бинарное дерево на экране, сначала проверяем, вообще есть ли оно. Если мы не заполним дерево значениями и не заложим семечко (не создадим корень), то дерева в принципе существовать не может, и поэтому отображать будет нечего, но если создали, то используя рекурсивный вызов функции последовательно отображаем все элементы. Кроме того, эта первая проверка будет и сигналом для завершения рекурсивного вызова функции. Ведь если встретится нулевое звено, то произойдёт return, а мы после создания каждого звена очищали память для следующего роста.
Может, кому-то непонятно, зачем использован параметр u. При выводе на экран вы будете видеть палочки, которые выводятся с помощью цикла. Найти в коде это место не трудно. Эти палочки символически обозначают количество узлов. Я пока не писал, но узел дерева, не имеющий потомков, называется лист. В нашем случае у дерева два листа. 0 и 9.
Если кому мало всё это понятно, то чуть ниж моё личное художество. Предположительно пользователь вводит числа и из них строится дерево. То что вводит пользователь появляется поочередно и ищет своё место. Когда число находит свою позицию, то бронирует найденную позицию. Правую часть я не принял во внимание, но там всё заполняется точно также. После заполнения дерева пройтись по нему не составит труда. Каждый шаг прохода обозначен в конце красной цифрой. Если встречаются равные элементы, то они создают что-то похожее на ветку, и эта ветка с каждым элементом увеличивается (в конце обозначено стрелками). При считывании информации с дерева сначала всё собирается с одной ветки, потом со следующей, и так пока "ветки" не закончатся. Присмотритесь к рисунку, может вам получится понять ещё какие-то моменты.
(Пример на рисунке) красные 2 и 3 напутаны местами:
Деревья в C++
Для визуального восприятия можно посмотреть один из примеров. Достаточно просто использовать код из листинга #2 и посмотреть, как и что получается с бинарным деревом. (автор кода не я). В Borland C++ 3.1 пример работает. Особо сильно в код этого примера можно и не вникать, важнее, чтобы увидели, что же это за чудо такое — бинарное дерево. В принципе, понять как с программой работать — несложно.



23 комментария на «“С++ для начинающих. Бинарное дерево. Первое знакомство”»

  1. Артём:

    Здравствуйте простите но вот возник вопрос о
    print(tree,0);
    почему здесь нужен 0, а не другое число потому что я подставлял разные числа и результат тот же. Объясните пожалуйста.

    Автор сайта отвечает:
    u – число узлов (звеньев).
    При выводе на экран слева символы | вот количество этих символов будет разным. Но в пустом дереве ноль узлов, поэтому там нужен ноль, а не другое число. Сколько символов, столько звеньев. исправлено

    То есть если бы левая часть или правая делились на две ветки было бы 2 или больше узлов?

    Автор сайта отвечает:
    нет. Вы рисунок видите? Тут нарисована Анимация. Есть кружки. Выбираем любой элемент и визуально проходим по кратчайшему пути до выбранного элемента. Считаем все остановки (кружок = остановка). Сколько будет остановок, столько и будет узлов. (Узел = Звено)
    Смотрим на рисунок и выбираем три значения (например Две единицы и тройка). Считаем сколько надо кружков пройти до этих элементов по кратчайшему пути. Потом запускаем программу, вводим числа в порядке как на рисунке (8 значений), смотрим на результат работы программы. (считаем число символов | перед единицами и тройками соответственно).

    Если ввести не ноль там где вы спросили, то этих символов | будет больше чем нужно. Т.е. число звеньев будет неверным.

    Выше я неправильно ответил. Извините.

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

    Автор сайта отвечает:
    Верно, сначала нет ничего. Первый кружок пустота. Пустоту за узел не считаем. Записали в пустое место значение, появился первый узел. Записали еще одно значение, появился новый узел. Но верно не всё. Тут такое дело, что До разных конечных пунктов, число узлов может быть одинаковым.

     
    например 0-5, одинаковое число узлов и 1-2 одинаковое

    Не так выразился.Сначала печатаеться елемент который имеет 1 узел (левый) то есть корень указывает на левый елемент получаеться 1 узел и делее идем подключаеться ищё один узел то есть второй и так далее? Я правильно понял?

    Автор сайта отвечает:
    теперь я запутался.
    При выводе на экран программа проходит кратчайший путь до узла с минимальным значением и выводит на экран найденный элемент, потом кратчайшим маршрутом до следующего минимального и так пока не пройдет по всему дереву. Корень дерева ни на что не указывает, кроме как точки старта просмотра
     
    красные цифры рисунка — порядок просмотра узлов в дереве (красные 2 и 3 перепутаны местами)
    может вы имели ввиду рисуется (например для рисунка вручную) на бумаге?

    Извените за то что запутал и за множество вопросов.
    Как бы щитаеться количество узлов от корня к следующему елементу и все? И естествено беруться кратчайшие пути.

    Автор сайта отвечает:
    Да. Так.

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

    О функции печати понял. Вот еще один вопрос. Указатель на указатель позволяет менять елемент на который он указывает?

    Автор сайта отвечает:
    Какой вопрос — такой ответ.
    Указатель на указатель позволяет менять только две вещи.
    1) Адрес, на который сам указывает.
    2) Адрес того Указателя на который указывает.
    ===============
    Указатель — это адрес памяти, а не элемент, поэтому адреса памяти можно изменить, а элемент вряд ли. (Не совсем правильно сказано, но в контексте подразумевается, что элемент — это не адрес, а что-то, что там по адресу лежит)

    Разыменованный указатель позволяет

    Вот так вот.

    Большущее спасибо за помощ, и отличные ответы. Теперь вроде все понял.

  2. сссссссссссмсмвм:

    😈

  3. Петр:

    Совсем не понял про «|», не могли бы объяснить подробнее и понятнее?)

    • В комментариях написано уже, что это количество звеньев по кратчайшему пути. (отсчет от единицы)
      Количество символов | = количество звеньев.

      Смотрите на анимированный рисунок. Лучше всего сделайте из рисунка один скрин готового (полного) дерева.
      Вообразите, что кружок с цифрой — это остановка.
      Запустите воображаемый маршрутный автобус с точки, обозначеной красной цифрой 8, по кратчайшему пути до определенного места и посчитайте сколько он остановок проедет.

      Количество символов | как раз и будет количеством таких остановок. до пункта назначения.
      ____________________________
      некоторую путаницу может внести, что в примере есть одинаковые числа внутри дерева. При выводе на экран смотрите для каждого одинакового числа, а не только от первого попавшегося.

      в примере всего остановок 8. ввод 5,4,0,1,2,5,1,3 (как появляются так и вводятся)

      • Эдуард:

        Добро деятель, прошу вашей помощи !
        вот кусок кода , в нем непонятно как работает оператор ретёрн , он же должен делать выход из функции, а получается так , что есле условие
        (Т == НУЛЛ) после вызова рекурсии( print(t->l); ) истинно , то выполняется оператор Cout , а не передача уравления в точку вызова функции , почему ??
        вот код :
        void print (node *t)
        {
        if (t == NULL) return; //Если дерево пустое, то отображать нечего, выходим
        else //Иначе
        {
        print(t->l);//С помощью рекурсивного посещаем левое поддерево
        cout<info<r); //С помощью рекурсии посещаем правое поддерево
        }

        • вообще-то я не знаю что у вас за

          и вопроса не понял.
          return не может не делать выход из функции. тут он тоже делает только выход из функции и ничего другого.
          ================
          если вы изначально не инициализируете первое звено дерева значением NULL, то при пустом дереве первый return выполнен не будет.
          если вы инициализируете первое звено дерева значением NULL, Но не введете в дерево новых звеньев, то оператор return будет выполнен сразу, ибо ваш t==NULL (как пустое первое звено)
          если вы внесете в первое звено дерева какие-то значения, то (согласно моему примеру) при помощи new первое звено дерева будет не NULL (t!=NULL), т.е. return для первого звена пропустится

          это же относится ко всем последующим звеньям.

          • Эдуард:

            /*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
            void print (node *t,int u)
            {
            if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
            else //Иначе
            {
            print(t->l,++u);//С помощью рекурсивного посещаем левое поддерево
            for (int i=0;i<u;++i) cout<<"|";
            cout<info<r,++u); //С помощью рекурсии посещаем правое поддерево
            }
            ну вот же ваш пример, который обходит дерево и печатает содержимое , я смотрел как работает ретёрн в дебагере , все не так как вы говорите.После того , как т== нулл выполняется цикл,потом сиаут,потом рекурсия на правое поддерево, потом проверка Т==нулл!!!

  4. Эдуард:

    опять кусок кода куда-то пропал , и сиаут битый , было так !!
    void print (node *t,int u)
    {
    if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
    print(t->l,++u);//С помощью рекурсивного посещаем левое поддерево
    for (int i=0;i<u;++i) cout<<"|";
    cout < info <r, ++u ); //С помощью рекурсии посещаем правое поддерево
    }

  5. Эдуард:

    понятия не имею что у вас с сайтом, но очень прошу вас помочь мне ! гляньте /*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/ в первом же вашем примере , я ту часть кода пытался скопировать .

    • чтобы код норм выглядел нужно использовать [phр][/рhp] (только теги руками пишите, а не копируйте отсюда)
      это проблемы WordPress

      и не знаю я как работает компилятор, что вы в дебаггере видите, что смотрите.
      я что вижу, то и говорю. Попробую угадать (в прямом смысле без сарказмов и ироний)
      если ниже cout<r написать cout<<"—-\n", а внутри main не добавлять в дерево ни одного элемента, то получим такой результат

      потому как return сработает сразу.

      Если введете 1 элемент в дерево, то из-за new первое звено дерева будет не NULL, поэтому при выводе на экран будет выведено и «—\n» (от вышенаписанного cout), т.е. return пропускается, т.к. проверка на NULL показывет, что это не NULL и выполняется рекурсивный вызов.
      А т.к. при добавлении звена в дерева, подготавливается почва (я это где-то семечками называл), в которую сначала приписывается NULL, то при существующем единственном звене, в текущем вызове определится, что текущее звено пустое, и произойдет возврат в точку вызова без прописывания «—» (т.е. return опять сработает сразу)

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

      я не буду отрицать, что я могу быть в чем-то не прав. я все-таки не спец.

      • Эдуард:

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

        я не буду отрицать, что я могу быть в чем-то не прав. я все-таки не спец.
        ___________________________________________________________________________________
        Спасибо большое вам , ретерн передавал управление именно в точку вызова ( вызов рекурсии) а не в мэин(как думал я) именно этого я не понимал , и именно это показывал дебагер. И , кстати, зря вы не пользуетесь дебагером , с помошью него , можно пошагово рассматривать выполнение программы , просматривать что лежит в переменной и как она изменяется при переходе на след. шаг . Это только то , что я умею .

        • я сейчас не занимаюсь и не изучаю C++, а когда писал темы, то там как-то дебаггер под руку не попался. Да и некоторые проблемы с дебагерами существуют (не везде они удобные).
          неумение использовать деббагер я компенсировал тем, что максимально сокращал код и смотрел по выводу на экран. Это немного трудозатратнее чем с деббагером, но все же иногда проще получается и помогает при незнакомых языках.

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

  6. Аноним:

    Почему?

  7. Дима:

    Помогите пожалуйста с созданием функции по замене самого правого элемента самым левым.

  8. young:

    Ох.. спасибо тебе огромное. Динамическое программирование только с помощью твоих статей и освоил. У меня единственный вопрос, который постоянно мучает. Почему в в ф-ю push мы передаем указатель на указатель дерева. В чем разница, если бы мы передали просто указатель?

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

      • Михаил:

        Здравствуйте, очень интересная статья, в плане понимания бинарных деревьев.
        Дабы ее улучшить предлагаю внести правки в первый листинг.
        1. Все-таки такое смешивание plain C кода и C++ выглядит немного странно
        2. Тут в комментариях люди пишут, что изучали динамическое выделение памяти по этой статье, тогда лучше будет добавить освобождение памяти.
        3. использование приводит к привязке только к microsoft платформе.
        4. все-таки передавать указатель на указатель — не обязательно( Ни в коем разе не хочу сказать, что это неправильно, но мне кажется, что так код читается несколько лучше)
        5. такой код скомпилится на любой ОС, любой архитектуре(даже 8-битной). я это, например, компилил с помощью GCC на mac os x.
        6. Если из этого кода выбросить еще и всю кирилицу, то получим чистый ANSI C89 код

        #include <stdio.h>
        #include <stdlib.h>
        
        //Наша структура
        typedef struct node
        {
            int info; 									//Информационное поле
            struct node *l, *r;							//Левая и Правая часть дерева
        }* nodeptr;
        
        /*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
        nodeptr push(int a, nodeptr t)
        {
        	if (t==NULL) 								//Если дерева не существует
        	{
        		t = malloc(sizeof(struct node)); 		//Выделяем память
        		t->info = a; 							//Кладем в выделенное место аргумент a
        		t->l = t->r = NULL; 					//Очищаем память для следующего роста
        		return t; 								//Заложили семечко, выходим
        	}
        	//Дерево есть
        	if (a > t->info) t->r = push(a, t->r); 		//Если аргумент а больше чем текущий элемент, кладем его вправо
        	else t->l = push(a, t->l); 					//Иначе кладем его влево
        	return t;
        }
        
        /*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
        void print (nodeptr t,int u)
        {
        	if (t == NULL) return; 						//Если дерево пустое, то отображать нечего, выходим
        	else 										//Иначе:
        	{
        		int i;
        		print(t->l, ++u);						//С помощью рекурсивного посещаем левое поддерево
        		for (i = 0; i < u; ++i) printf("|");
        		printf("%d\n", t->info); 				//И показываем элемент
        		u--;
        	}
        	print(t->r, ++u); 							//С помощью рекурсии посещаем правое поддерево
        }
        
        /*ФУНКЦИЯ ОСВОБОЖДЕНИЯ ПАМЯТИ ДЕРЕВА НА ЭКРАНЕ*/
        void freeTree(nodeptr t){
        	if (t == NULL) return;
        	freeTree(t->l);
        	freeTree(t->r);
        	free(t);
        }
        
        int main (int argc, char** argv)
        {
        	nodeptr tree = NULL;						//Объявляем переменную, тип которой структура Дерево
        	int i;										//В ANSI C нельзя объявлять переменную в for
        	int n; 										//Количество элементов
        	int s; 										//Число, передаваемое в дерево
        	printf("введите количество элементов  ");
        	scanf("%d", &n); 							//Вводим количество элементов
        
        	for (i=0; i < n; ++i)
        	{
        		printf("ведите число  ");
        		scanf("%d", &s); 						//Считываем элемент за элементом
        		tree = push(s,tree);					//И каждый кладем в дерево
        	}
        	printf("ваше дерево\n");
        	print(tree,0);
        	freeTree(tree);								//Освободить память!
        	return 0;
        }
        

        Автор сайта отвечает:
        Спс за проявленное внимание и полезные замечания.

        Единственное, весь листинг, написанный исключительно на С, когда он показан на сайте, посвященному С++ , более странным должен казаться, чем смесь С++ и С

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

        ___________________
        Насчет указателя на указатель я точно не помню, надо посмотреть. Но причина этому скорее всего в том, что когда создается копия указателя на начало дерева, то высвобождение памяти работает для копии (для псевдодерева), в котором есть начало, но нет продолжения. (Сейчас это неточная информация, но похоже на то, отчего не просто одинарным указателем делалось)

  9. Михаил:

  10. Леонид:

    Привет

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

    Сайт толковый, по-спартански, ничего лишнего. Тоже, за это,  спасибо огромное.

     

     

  11. Nafisa:

    Реальные номера узлов дерева. Все узлы дерева вторичной алгоритма расчета арифметика и программного обеспечения
    help????

  12. Иван:

    Почему выполнение кода обрывается после первой итерации цикла в мейне?

  13. Очень полезная информация. Наконец то я нашла то что искала. Спасибо.

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

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

Поиск

 
     

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

https://www.litres.ru/devid-herron/node-js-razrabotka-servernyh-veb-prilozheniy-na-javascript/?lfrom=15589587

Последние комментарии

Яндекс.Метрика