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

Опубликовано 02.09.2012 | Автор: admin

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

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

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

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

          //Листинг #aa         Структура, выступающая в роли звена дерева, такими структурами дерево будет заполняться
struct Node                             //Node - Это будет звеном дерева
{
   int x;                               //x - Число, которое я буду записывать в дерево
   Node *l,*r;                          //Адресные поля. Адрес левой части и Адрес правой части (от left,right)
};

//Листинг #aa Структура, выступающая в роли звена дерева, такими структурами дерево будет заполняться

struct Node //Node - Это будет звеном дерева

{

int x; //x - Число, которое я буду записывать в дерево

Node *l,*r; //Адресные поля. Адрес левой части и Адрес правой части (от left,right)

};

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

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

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

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

    //Листинг #1            Структура как основополагающая часть дерева
#include <iostream>
using namespace std;

struct Node                             //Звено дерева
{
   int x;                               //То, что записываем в дерево
   Node *l,*r;                          //Это указатели на новые звенья
};

int main()
{
   Node *Tree = NULL;                   //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой

   return 0;
}

//Листинг #1 Структура как основополагающая часть дерева

#include <iostream>

using namespace std;

struct Node //Звено дерева

{

int x; //То, что записываем в дерево

Node *l,*r; //Это указатели на новые звенья

};

int main()

{

Node *Tree = NULL; //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой

return 0;

}

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

==========================================
Шаг второй:
==========================================

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

    //Листинг #2            Добавляем функцию вывода дерева на экран
#include <iostream>
using namespace std;

struct Node                         //Звено дерева
{
   int x;                           //То, что записываем в дерево
   Node *l,*r;                      //Это указатели на новые звенья
};

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

int main()
{
   Node *Tree = NULL;               //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой

      show(Tree);                   //Вызов функции обхода дерева;

   cin.get();                       //Обычная задержка перед выходом;
   return 0;
}

//Листинг #2 Добавляем функцию вывода дерева на экран

#include <iostream>

using namespace std;

struct Node //Звено дерева

{

int x; //То, что записываем в дерево

Node *l,*r; //Это указатели на новые звенья

};

void show(Node *&Tree) //Функция обхода

{

if (Tree != NULL) //Пока не встретится пустое звено

{

show(Tree->l); //Рекурсивная функция для вывода левого поддерева

cout<<Tree->x; //Отображаем корень дерева

show(Tree->r); //Рекурсивная функци для вывода правого поддерева

}

int main()

{

Node *Tree = NULL; //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой

show(Tree); //Вызов функции обхода дерева;

cin.get(); //Обычная задержка перед выходом;

return 0;

}

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

==========================================
Шаг третий. Добавляем звенья в бинарное дерево:
==========================================

    //Листинг #3            Добавляем функцию добавления в бинарное дерево звена
#include <iostream>
using namespace std;

struct Node                         //Звено дерева
{
   int x;                           //То, что записываем в дерево
   Node *l,*r;                      //Это указатели на новые звенья
};

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

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

int main()
{
   Node *Tree = NULL;               //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой


	  for (int i=5; i>0; i--) add_node(i,Tree);         //Я решил так заполнять
	  show(Tree);                   //Обход дерева

	  cin.get();

   return 0;
}

//Листинг #3 Добавляем функцию добавления в бинарное дерево звена

#include <iostream>

using namespace std;

struct Node //Звено дерева

{

int x; //То, что записываем в дерево

Node *l,*r; //Это указатели на новые звенья

};

void show(Node *&Tree) //Функция обхода

{

if (Tree != NULL) //Пока не встретится пустое звено

{

show(Tree->l); //Рекурсивная функция для вывода левого поддерева

cout<<Tree->x; //Отображаем корень дерева

show(Tree->r); //Рекурсивная функции для вывода правого поддерева

}

void add_node(int x,Node *&MyTree) //Функция добавления звена в дерево

{

if (NULL == MyTree) //То, о чем я в самом начале писал. Если дерева нет, то сеем семечко

{

MyTree = new Node; //Выделяем память под звено дерева

MyTree->x = x; //Записываем данные в звено

MyTree->l = MyTree->r = NULL; //Подзвенья инициализируем пустотой во избежание ошибок

}

int main()

{

Node *Tree = NULL; //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой

for (int i=5; i>0; i--) add_node(i,Tree); //Я решил так заполнять

show(Tree); //Обход дерева

cin.get();

return 0;

}

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

    //Листинг #ba           Описание функции добавления звена, (дополняем функцию кодом)
void add_node(int x,Node *&MyTree)                      //Функция добавления звена в дерево
{
	if (NULL == MyTree)                                 //То, о чем я в самом начале писал. Если дерева нет, то сеем семечко
	{
		MyTree = new Node;                              //Выделяем память под звено дерева
		MyTree->x = x;                                  //Записываем данные в звено
		MyTree->l = MyTree->r = NULL;                   //Подзвенья инициализируем пустотой во избежание ошибок
	}

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

//Листинг #ba Описание функции добавления звена, (дополняем функцию кодом)

void add_node(int x,Node *&MyTree) //Функция добавления звена в дерево

{

if (NULL == MyTree) //То, о чем я в самом начале писал. Если дерева нет, то сеем семечко

{

MyTree = new Node; //Выделяем память под звено дерева

MyTree->x = x; //Записываем данные в звено

MyTree->l = MyTree->r = NULL; //Подзвенья инициализируем пустотой во избежание ошибок

}

if (x < MyTree->x) //Если нововведенный элемент x меньше чем элемент x из семечка дерева, уходим влево

{

if (MyTree->l != NULL) add_node(x, MyTree->l); //При помощи рекурсии заталкиваем элемент на свободный участок

else //Если элемент получил свой участок, то

{

MyTree->l = new Node; //Выделяем память левому подзвену. Именно подзвену, а не просто звену

MyTree->l->l = MyTree->l->r = NULL; //У левого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой

MyTree->l->x = x; //Записываем в левое подзвено записываемый элемент

}

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

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

    //Листинг #bb       Описание функции добавления звена, (дополняем функцию кодом)
void add_node(int x,Node *&MyTree)                  //Функция добавления звена в дерево
{
	if (NULL == MyTree)                             //То, о чем я в самом начале писал. Если дерева нет, то сеем семечко
	{
		MyTree = new Node;                          //Выделяем память под звено дерева
		MyTree->x = x;                              //Записываем данные в звено
		MyTree->l = MyTree->r = NULL;               //Подзвенья инициализируем пустотой во избежание ошибок
	}

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

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

}

//Листинг #bb Описание функции добавления звена, (дополняем функцию кодом)

void add_node(int x,Node *&MyTree) //Функция добавления звена в дерево

{

if (NULL == MyTree) //То, о чем я в самом начале писал. Если дерева нет, то сеем семечко

{

MyTree = new Node; //Выделяем память под звено дерева

MyTree->x = x; //Записываем данные в звено

MyTree->l = MyTree->r = NULL; //Подзвенья инициализируем пустотой во избежание ошибок

}

if (x < MyTree->x) //Если нововведенный элемент x меньше чем элемент x из семечка дерева, уходим влево

{

if (MyTree->l != NULL) add_node(x, MyTree->l); //При помощи рекурсии заталкиваем элемент на свободный участок

else //Если элемент получил свой участок, то

{

MyTree->l = new Node; //Выделяем память левому подзвену. Именно подзвену, а не просто звену

MyTree->l->l = MyTree->l->r = NULL; //У левого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой

MyTree->l->x = x; //Записываем в левое подзвено записываемый элемент

}

if (x > MyTree->x) //Если нововведенный элемент x больше чем элемент x из семечка дерева, уходим вправо

{

if (MyTree->r != NULL) add_node(x, MyTree->r); //При помощи рекурсии заталкиваем элемент на свободный участок

else //Если элемент получил свой участок, то

{

MyTree->r = new Node; //Выделяем память правому подзвену. Именно подзвену, а не просто звену

MyTree->r->l = MyTree->r->r = NULL; //У правого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой

MyTree->r->x = x; //Записываем в правое подзвено записываемый элемент

}

Такая функция добавления элемента в дерево вышла.

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

    //Листинг #4            Бинарное дерево
#include <iostream>
using namespace std;

struct Node                         //Звено дерева
{
   int x;                           //То, что записываем в дерево
   Node *l,*r;                      //Это указатели на новые звенья
};

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

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

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

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

int main()
{
   Node *Tree = NULL;           //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой



	  for (int i=5; i>0; i--) add_node(i,Tree);             //Это я забивал 5-4-3-2-1, а вывод сами увидите
	  show(Tree);               //Вывод на экран дерева. или просто обход дерева

	  cin.get();

   return 0;
}

//Листинг #4 Бинарное дерево

#include <iostream>

using namespace std;

struct Node //Звено дерева

{

int x; //То, что записываем в дерево

Node *l,*r; //Это указатели на новые звенья

};

void show(Node *&Tree) //Функция обхода

{

if (Tree != NULL) //Пока не встретится пустое звено

{

show(Tree->l); //Рекурсивная функция для вывода левого поддерева

cout << Tree->x; //Отображаем корень дерева

show(Tree->r); //Рекурсивная функци для вывода правого поддерева

}

void add_node(int x,Node *&MyTree) //Фукция добавления звена в дерево

{

if (NULL == MyTree) //То, о чем я в самом начале писал. Если дерева нет, то ложим семечко

{

MyTree = new Node; //Выделяем память под звено дерева

MyTree->x = x; //Записываем данные в звено

MyTree->l = MyTree->r = NULL; //Подзвенья инициализируем пустотой во избежание ошибок

}

if (x < MyTree->x) //Если нововведенный элемент x меньше чем элемент x из семечка дерева, уходим влево

{

if (MyTree->l != NULL) add_node(x,MyTree->l); //При помощи рекурсии заталкиваем элемент на свободный участок

else //Если элемент получил свой участок, то

{

MyTree->l = new Node; //Выделяем память левому подзвену. Именно подзвену, а не просто звену

MyTree->l->l = MyTree->l->r = NULL; //У левого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой

MyTree->l->x = x; //Записываем в левое подзвено записываемый элемент

}

if (x > MyTree->x) //Если нововведенный элемент x больше чем элемент x из семечка дерева, уходим вправо

{

if (MyTree->r != NULL) add_node(x, MyTree->r); //При помощи рекурсии заталкиваем элемент на свободный участок

else //Если элемент получил свой участок, то

{

MyTree->r = new Node; //Выделяем память правому подзвену. Именно подзвену, а не просто звену

MyTree->r->l = MyTree->r->r = NULL; //У правого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой

MyTree->r->x = x; //Записываем в правое подзвено записываемый элемент

}

int main()

{

Node *Tree = NULL; //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой

for (int i=5; i>0; i--) add_node(i,Tree); //Это я забивал 5-4-3-2-1, а вывод сами увидите

show(Tree); //Вывод на экран дерева. или просто обход дерева

cin.get();

return 0;

}

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

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

          //Листинг #5          Бинарное дерево, дополняем код функцией для очистки памяти во избежание утечек
#include <iostream>
using namespace std;

struct Node                         //Звено дерева
{
   int x;                           //То, что записываем в дерево
   Node *l,*r;                      //Это указатели на новые звенья
};

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

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

}

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

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

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

int main()
{
   Node *Tree = NULL;                   //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой
	  for (int i=5; i>0; i--) add_node(i,Tree);       //Это я забивал 5-4-3-2-1, а вывод сами увидите
	  show(Tree);                        //Вывод на экран дерева. или просто обход дерева
	  cout << '\n';
	  del(Tree);                        //Чистка памяти! Распилили дерево

	  for (int i=20; i>5; i--) add_node(i,Tree);        //На месте спиленного дерева можно растить новое
	  show(Tree);                       //Смотрим, что выросло
	  del(Tree);                        //Когда дерево уже не нужно, зачищаем память
}

//Листинг #5 Бинарное дерево, дополняем код функцией для очистки памяти во избежание утечек

#include <iostream>

using namespace std;

struct Node //Звено дерева

{

int x; //То, что записываем в дерево

Node *l,*r; //Это указатели на новые звенья

};

void show(Node *&Tree) //Функция обхода

{

if (Tree != NULL) //Пока не встретится пустое звено

{

show(Tree->l); //Рекурсивная функция для вывода левого поддерева

cout << Tree->x << '\t'; //Отображаем корень дерева

show(Tree->r); //Рекурсивная функци для вывода правого поддерева

}

/*Добавили очистку памяти*/

void del(Node *&Tree){

if (Tree != NULL) //Пока не встретится пустое звено

{

del(Tree->l); //Рекурсивная функция прохода по левому поддереву

del(Tree->r); //Рекурсивная функци для прохода по правому поддереву

delete Tree; //Убиваем конечный элемент дерева

Tree = NULL; //Может и не обязательно, но плохого не будет

}

void add_node(int x,Node *&MyTree) //Фукция добавления звена в дерево

{

if (NULL == MyTree) //То, о чем я в самом начале писал. Если дерева нет, то ложим семечко

{

MyTree = new Node; //Выделяем память под звено дерева

MyTree->x = x; //Записываем данные в звено

MyTree->l = MyTree->r = NULL; //Подзвенья инициализируем пустотой во избежание ошибок

}

if (x < MyTree->x) //Если нововведенный элемент x меньше чем элемент x из семечка дерева, уходим влево

{

if (MyTree->l != NULL) add_node(x, MyTree->l); //При помощи рекурсии заталкиваем элемент на свободный участок

else //Если элемент получил свой участок, то

{

MyTree->l = new Node; //Выделяем память левому подзвену. Именно подзвену, а не просто звену

MyTree->l->l = MyTree->l->r = NULL; //У левого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой

MyTree->l->x = x; //Записываем в левое подзвено записываемый элемент

}

if (x > MyTree->x) //Если нововведенный элемент x больше чем элемент x из семечка дерева, уходим вправо

{

if (MyTree->r != NULL) add_node(x, MyTree->r); //При помощи рекурсии заталкиваем элемент на свободный участок

else //Если элемент получил свой участок, то

{

MyTree->r = new Node; //Выделяем память правому подзвену. Именно подзвену, а не просто звену

MyTree->r->l = MyTree->r->r = NULL; //У правого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой

MyTree->r->x = x; //Записываем в правое подзвено записываемый элемент

}

int main()

{

Node *Tree = NULL; //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой

for (int i=5; i>0; i--) add_node(i,Tree); //Это я забивал 5-4-3-2-1, а вывод сами увидите

show(Tree); //Вывод на экран дерева. или просто обход дерева

cout << '\n';

del(Tree); //Чистка памяти! Распилили дерево

for (int i=20; i>5; i--) add_node(i,Tree); //На месте спиленного дерева можно растить новое

show(Tree); //Смотрим, что выросло

del(Tree); //Когда дерево уже не нужно, зачищаем память

}

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

Рубрика: Бинарное дерево, Деревья, Динамические структуры, Знакомства, Указатели

Аноним:

14.05.2013 в 12:17 пп

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

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

struct Tree{

int x; //Некоторое значение в вершине дерева

Tree *n[N]; //Массив указателей на потомков (N)

Ответить

Артём:

16.05.2013 в 1:18 дп

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

void add_node(int node, Node *&Tree){
	if(Tree == NULL){
		Tree = new Node;
		Tree->node = node;
		Tree->left = NULL;
		Tree->right = NULL;
	}
	if(node node){
			add_node(node, Tree->left);
	}
	if(node > Tree->node){
			add_node(node, Tree->right);
	}
}

void add_node(int node, Node *&Tree){

if(Tree == NULL){

Tree = new Node;

Tree->node = node;

Tree->left = NULL;

Tree->right = NULL;

if(node node){

add_node(node, Tree->left);

if(node > Tree->node){

add_node(node, Tree->right);

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

Alex:

11.07.2013 в 2:38 пп

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

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

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

30.09.2013 в 11:27 дп

😆 😆 😆 😆

Игорь:

24.11.2013 в 5:28 пп

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

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

Дмитрий:

16.03.2014 в 10:22 пп

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

21.03.2014 в 9:16 пп

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

Андрей:

27.06.2014 в 7:34 пп

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

class CDictionary
{
	
	struct Word
	{
		char* key_Eng;
		char* translate;

		Word* pPrew;
		Word* pSmal;
		Word* pBig;

		Word(const char* key_word, const char* _translate) //konstruktor
			: pPrew(nullptr), pSmal(nullptr), pBig(nullptr),
			key_Eng(nullptr), translate(nullptr)
		{
			key_Eng = new char[strlen(key_word) + 1];
			strcpy_s(key_Eng, strlen(key_word) + 1, key_word);
			translate = new char[strlen(_translate) + 1];
			strcpy_s(translate, strlen(_translate) + 1, _translate);
		}

		~Word() //destruktor
		{
			/*if (pPrew)
				delete pPrew;
			if (pSmal)
				delete pSmal;
			if (pBig)
				delete pBig;
			if (key_Eng)
				delete[] key_Eng;
			if (translate)
				delete[] translate;*/
		}
	};	
public:
	CDictionary();
	~CDictionary();

private:
	Word* pRoot;
}

class CDictionary

struct Word

char* key_Eng;

char* translate;

Word* pPrew;

Word* pSmal;

Word* pBig;

Word(const char* key_word, const char* _translate) //konstruktor

: pPrew(nullptr), pSmal(nullptr), pBig(nullptr),

key_Eng(nullptr), translate(nullptr)

key_Eng = new char[strlen(key_word) + 1];

strcpy_s(key_Eng, strlen(key_word) + 1, key_word);

translate = new char[strlen(_translate) + 1];

strcpy_s(translate, strlen(_translate) + 1, _translate);

~Word() //destruktor

/*if (pPrew)

delete pPrew;

if (pSmal)

delete pSmal;

if (pBig)

delete pBig;

if (key_Eng)

delete[] key_Eng;

if (translate)

delete[] translate;*/

public:

CDictionary();

~CDictionary();

private:

Word* pRoot;

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

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

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

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

Arete:

14.11.2014 в 10:54 пп

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

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

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

З.Ы.

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

03.06.2015 в 9:17 дп

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

Дима:

13.09.2015 в 8:57 дп

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

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

DanMan:

16.09.2015 в 1:18 пп

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

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

16.09.2015 в 2:20 пп

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

Пример:

srand(time(NULL));
Node* Tree=0;
for(int i=5;i>0;i–)
{
int a=rand()%11;
AddNode(a,Tree);
}
Show(Tree);
cin.get();

return 0;
}

srand(time(NULL));

Node* Tree=0;

for(int i=5;i>0;i–)

int a=rand()%11;

AddNode(a,Tree);

Show(Tree);

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

Денис:

06.10.2015 в 11:42 дп

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

admin:

06.10.2015 в 12:35 пп

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

06.10.2015 в 2:01 пп

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

void FarX(List *element,	int &far,  //счетчик уровней(изменяется и возвращается из функции
							int &farO, //счетчик максимального уровня(изменяется только в сторону увеличения)
							int &X	   //число, которое находится на максимальном уровне
							){
	if (element->left != NULL)	//проверка левого ответвления
	{
		far++;
		if (farO left->x;
		}
		FarX(element->left, far, farO, X);
		far--;
	}
	if (element->right != NULL) //проверка правого ответвления
	{
		far++;
		if (farO right->x;
		}
		FarX(element->right, far, farO, X);
		far--;
	}
}

void FarX(List *element, int &far, //счетчик уровней(изменяется и возвращается из функции

int &farO, //счетчик максимального уровня(изменяется только в сторону увеличения)

int &X //число, которое находится на максимальном уровне

){

if (element->left != NULL) //проверка левого ответвления

far++;

if (farO left->x;

FarX(element->left, far, farO, X);

far--;

if (element->right != NULL) //проверка правого ответвления

if (farO right->x;

FarX(element->right, far, farO, X);

admin:

06.10.2015 в 3:48 пп

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

Ответить

VikThor:

26.10.2015 в 7:25 пп

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

admin:

26.10.2015 в 7:49 пп

Нет. Так память не чистят. new Только с delete

Ответить

Артур:

05.12.2015 в 11:24 дп

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

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

C++

#include <iostream> using namespace std; struct Node //Звено дерева { int x; //То, что записываем в дерево Node *l, *r; //Это указатели на новые звенья }; void show(Node *&Tree) //Функция обхода { if (Tree != NULL) //Пока не встретится пустое звено { show(Tree->l); //Рекурсивная функция для вывода левого поддерева cout << '-'; cout << Tree->x; //Отображаем корень дерева show(Tree->r); //Рекурсивная функци для вывода правого поддерева cout << '-'; } else { cout << '\n'; } } /*Добавили очистку памяти*/ void del(Node *&Tree) { if (Tree != NULL) //Пока не встретится пустое звено { del(Tree->l); //Рекурсивная функция прохода по левому поддереву del(Tree->r); //Рекурсивная функци для прохода по правому поддереву delete Tree; //Убиваем конечный элемент дерева Tree = NULL; //Может и не обязательно, но плохого не будет } } void get_leaf_count(Node *&Tree, int &count) { if (Tree != NULL) //Пока не встретится пустое звено { get_leaf_count(Tree->l, count); //Рекурсивная функция для вывода левого поддерева if (Tree->r == NULL) { cout << Tree->x << '-'; count++; } get_leaf_count(Tree->r, count); //Рекурсивная функци для вывода правого поддерева } } void add_node(int x, Node *&MyTree) //Фукция добавления звена в дерево { if (NULL == MyTree) //То, о чем я в самом начале писал. Если дерева нет, то ложим семечко { MyTree = new Node; //Выделяем память под звено дерева MyTree->x = x; //Записываем данные в звено MyTree->l = MyTree->r = NULL; //Подзвенья инициализируем пустотой во избежание ошибок } if (x<MyTree->x) //Если нововведенный элемент x меньше чем элемент x из семечка дерева, уходим влево { if (MyTree->l != NULL) add_node(x, MyTree->l); //При помощи рекурсии заталкиваем элемент на свободный участок else //Если элемент получил свой участок, то { MyTree->l = new Node; //Выделяем память левому подзвену. Именно подзвену, а не просто звену MyTree->l->l = MyTree->l->r = NULL; //У левого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой MyTree->l->x = x; //Записываем в левое подзвено записываемый элемент } } if (x>MyTree->x) //Если нововведенный элемент x больше чем элемент x из семечка дерева, уходим вправо { if (MyTree->r != NULL) add_node(x, MyTree->r); //При помощи рекурсии заталкиваем элемент на свободный участок else //Если элемент получил свой участок, то { MyTree->r = new Node; //Выделяем память правому подзвену. Именно подзвену, а не просто звену MyTree->r->l = MyTree->r->r = NULL; //У правого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой MyTree->r->x = x; //Записываем в правое подзвено записываемый элемент } } } Node* cloning(Node *&Tree, Node *&semko) //Функция копирования { if (Tree != NULL) //Пока не встретится пустое звено { int x = Tree->x; add_node(x,semko); cloning(Tree->l,semko); //Рекурсивная функция для вывода левого поддерева cloning(Tree->r,semko); //Рекурсивная функци для вывода правого поддерева } return semko; } int main() { Node *Tree = NULL; //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой add_node(81, Tree); add_node(49, Tree); add_node(34, Tree); add_node(51, Tree); add_node(52, Tree); add_node(53, Tree); add_node(94, Tree); add_node(93, Tree); add_node(100, Tree); int count_leaf = 0; //Число листьев show(Tree); //Вывод на экран дерева. или просто обход дерева cout << "\n=============================\n"; get_leaf_count(Tree, count_leaf); //Создаем копию Node *Clon = NULL; Clon = cloning(Tree,Clon); del(Tree); cout << "\n=============================\n count leaf == " << count_leaf << '\n'; show(Clon); //Показываем копию del(Clon); //Чистим память от копии cin.get(); }

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

#include <iostream>
using namespace std;

struct Node //Звено дерева
{
int x; //То, что записываем в дерево
Node *l, *r; //Это указатели на новые звенья
};

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

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

}

void get_leaf_count(Node *&Tree, int &count) {
if (Tree != NULL) //Пока не встретится пустое звено
{
get_leaf_count(Tree->l, count); //Рекурсивная функция для вывода левого поддерева
if (Tree->r == NULL) {
cout << Tree->x << '-';
count++;
}

get_leaf_count(Tree->r, count); //Рекурсивная функци для вывода правого поддерева
}

}

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

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

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

Node* cloning(Node *&Tree, Node *&semko) //Функция копирования
{
        if (Tree != NULL) //Пока не встретится пустое звено
        {
            int x = Tree->x;

                add_node(x,semko);
                cloning(Tree->l,semko); //Рекурсивная функция для вывода левого поддерева
                cloning(Tree->r,semko); //Рекурсивная функци для вывода правого поддерева
        }
        return semko;

}

int main()
{

Node *Tree = NULL;  //Создаю указатель, тип которого = звено дерева и инициализирую его пустотой

add_node(81, Tree);
add_node(49, Tree);
add_node(34, Tree);
add_node(51, Tree);
add_node(52, Tree);
add_node(53, Tree);
add_node(94, Tree);
add_node(93, Tree);
add_node(100, Tree);

int count_leaf = 0;  //Число листьев
show(Tree); //Вывод на экран дерева. или просто обход дерева
cout << "\n=============================\n";
get_leaf_count(Tree, count_leaf);

//Создаем копию
Node *Clon = NULL;
    Clon = cloning(Tree,Clon);

del(Tree);

cout << "\n=============================\n count leaf == " << count_leaf << '\n';

     show(Clon);   //Показываем копию
     del(Clon);    //Чистим память от копии


cin.get();
}

Жора:

12.12.2015 в 11:39 дп

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

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

admin:

12.12.2015 в 8:59 пп

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

Ответить

Павел:

22.03.2016 в 5:25 пп

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

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

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

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

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

admin:

23.03.2016 в 12:34 дп

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

Ответить

22.03.2016 в 5:27 пп

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

Ирина:

16.06.2016 в 2:08 пп

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

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

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

18.11.2016 в 2:45 пп

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

Ugly:

11.05.2021 в 2:49 пп

Долбаеб то тут ты, причем глупый

Ответить

29.05.2019 в 2:33 дп

😎 😎 😎

07.06.2019 в 11:16 дп

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

igor:

10.06.2019 в 4:46 пп

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

NashelOshibku:

09.03.2020 в 6:35 пп

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

admin:

09.03.2020 в 7:29 пп

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

Ответить