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

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

Динамические структуры данных используются много и часто, но у начинающих много вопросов и для начинающих много непонятных моментов в программировании этих динамических структур. Так как я полностью и целиком самостоятельно изучаю с++, то при первых попытках понять что такое бинарное дерево возникли сложности. Особенно отпугивало слово рекурсия. Мало того что оказалось достаточно проблематично отыскать простой код с объяснениями, так в большинстве случаев нарисован рисунок и дан код без комментариев.

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

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

Код С++ Бинарное Дерево

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

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

В приведенном мною коде функция принимает 2 параметра. Первый — записываемое число, второй указатель на указатель звена дерева.

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

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

 

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

При всем этом, если элемент, который мы хотим поместить в дерево больше чем корневой, то с помощью рекурсивного вызова функции происходит последовательное перемещение элемента в правую часть. Наш элемент прыгает через один как через скакалку, пока не найдет своё место. А его место это то место, где справа элемент или больше чем он сам или если прыгать больше не через кого. Одним словом «Чехарда»
Если записываемый элемент меньше чем корневой, то выполняется такая же «Чехарда», только в левую сторону.

Для того чтоб отобразить наше Бинарное дерево на экране сначала проверяем вообще есть ли оно. Если мы не заполним дерево и не заложим семечко (не создадим корень), то дерева в принципе существовать не может и поэтому отображать будет нечего, но если создали, то используя рекурсивный вызов функции последовательно отображаем все элементы. Кроме того, эта первая проверка будет и сигналом для завершения рекурсивного вызова функции. Ведь если встретится Нулевое звено, то происходит return, а мы после создания каждого звена очищали память для следующего роста

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

Я не писал, но узел дерева, не имеющий потомков называется лист. В нашем случае у дерева два листа. 0 и 9.

Если кому мало что понятно, то вот мое личное художество. Предположительно пользователь вводит числа и из них строится дерево. То что вводит пользователь появляется поочередно и ищет свое место. Когда число находит свою позицию, то бронирует её. Правую часть я не брал, но там все заполняется точно также. После заполнения дерева, пройтись по нему не составит труда. Каждый шаг прохода обозначен в конце красной цифрой. Если встречаются равные элементы, то они создают что-то похожее на ветку и эта ветка с каждым элементом увеличивается (в конце обозначено стрелками). При считывании информации с дерева сначала все собирается с одной ветки, потом со следующей и так пока «ветки» не закончатся. Присмотритесь к рисунку, может получиться понять еще какие-то моменты.

(Пример на рисунке) красные 2 и 3 напутаны местами
===
Деревья в C++
===

Для визуального восприятия можно посмотреть один из примеров. Достаточно просто запустить нижеприведенный пример и посмотреть как и что получается с бинарным деревом. (автор не я). В Borland C++ 3.1 пример работает. Особо в код этого примера можно и не вникать, главное увидеть что же то за чудо такое — бинарное дерево.
В принципе понять как с программой работать несложно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Вот так вот.

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

  • сссссссссссмсмвм говорит:

    😈

  • Петр говорит:

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

    • admin говорит:

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

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

        • admin говорит:

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

          и вопроса не понял.
          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); //С помощью рекурсии посещаем правое поддерево
            }
            ну вот же ваш пример, который обходит дерево и печатает содержимое , я смотрел как работает ретёрн в дебагере , все не так как вы говорите.После того , как т== нулл выполняется цикл,потом сиаут,потом рекурсия на правое поддерево, потом проверка Т==нулл!!!

  • Эдуард говорит:

    опять кусок кода куда-то пропал , и сиаут битый , было так !!
    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 ); //С помощью рекурсии посещаем правое поддерево
    }

  • Эдуард говорит:

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

    • admin говорит:

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

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

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

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

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

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

      • Эдуард говорит:

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

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

        • admin говорит:

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

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

  • Прохожий говорит:

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

    Прошу прощения,я забыл убрать *previous
    Пока что это только мои размышления, и они могут сбить вас с толку

    Автор сайта отвечает:
    надо пробовать. я не знаю. склоняюсь к варианту "не смог бы" достаточно сложные циклы нужно делать. пробовать не стану.

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

    Почему?

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

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

  • young говорит:

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

    • admin говорит:

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

      • Михаил говорит:

        Здравствуйте, очень интересная статья, в плане понимания бинарных деревьев.
        Дабы ее улучшить предлагаю внести правки в первый листинг.
        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;
        }
        

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

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

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

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

  • Михаил говорит:

  • Леонид говорит:

    Привет

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

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

     

     

  • Nafisa говорит:

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

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

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

Поиск

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

НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Демотиватор как забыть С++ для чайников

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

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