Двоично дърво в C
В C, a двоично дърво е екземпляр на дървовидна структура от данни с родителски възел, който може да притежава максимален брой от два дъщерни възела; 0, 1 или 2 потомствени възли. Всеки един възел в a двоично дърво има собствена стойност и два указателя към своите деца, един указател за лявото дете, а другият за дясното дете.
Декларация на двоично дърво
А двоично дърво може да се декларира в C с помощта на обект, наречен структура който изобразява един от възлите в дървото.
структура възел {
тип данни var_name ;
структура възел * наляво ;
структура възел * точно ;
} ;
По-горе е декларация на един двоично дърво име на възел като възел. Съдържа три стойности; едната е променливата за съхранение на данни, а другите две са указателите към детето. (ляво и дясно дете на родителския възел).
Факти за двоичното дърво
Дори за големи набори от данни, използвайки a двоично дърво прави търсенето по-лесно и по-бързо. Броят на клоните на дърветата не е ограничен. За разлика от масива, дървета от всякакъв вид могат да бъдат направени и увеличени въз основа на това, което се изисква от индивида.
Реализация на двоично дърво в C
Следното е ръководство стъпка по стъпка за внедряване на a Двоично дърво в C.
Стъпка 1: Декларирайте двоично дърво за търсене
Създайте структурен възел, който има три типа данни, като данни, *left_child и *right_child, където данните могат да бъдат от целочислен тип и както *left_child, така и *right_child възли могат да бъдат декларирани като NULL или не.
структура възел{
вътр данни ;
структура възел * right_child ;
структура възел * ляво_дете ;
} ;
Стъпка 2: Създайте нови възли в двоично дърво за търсене
Създайте нов възел, като създадете функция, която приема цяло число като аргумент и предоставя указателя към новия възел, създаден с тази стойност. Използвайте функцията malloc() в C за динамично разпределение на паметта за създадения възел. Инициализирайте лявото и дясното дете на NULL и върнете nodeName.
структура възел * създавам ( данни за тип данни )
{
структура възел * име на възел = malloc ( размер на ( структура възел ) ) ;
име на възел -> данни = стойност ;
име на възел -> ляво_дете = име на възел -> right_child = НУЛА ;
връщане име на възел ;
}
Стъпка 3: Вмъкнете дясно и ляво дете в двоично дърво
Създайте функции insert_left и insert_right, които ще приемат два входа, които са стойността, която трябва да бъде вмъкната, и указателя към възела, към който ще бъдат свързани и двете деца. Извикайте функцията за създаване, за да създадете нов възел и да присвоите върнатия указател към левия указател на лявото дете или десния указател на дясното дете на основния родител.
структура възел * вмъкване_отляво ( структура възел * корен , данни за тип данни ) {корен -> наляво = създавам ( данни ) ;
връщане корен -> наляво ;
}
структура възел * вмъкване_надясно ( структура възел * корен , данни за тип данни ) {
корен -> точно = създавам ( данни ) ;
връщане корен -> точно ;
}
Стъпка 4: Показване на възли на двоично дърво с помощта на методи за преминаване
Можем да показваме дървета, като използваме три метода за обхождане в C. Тези методи за обхождане са:
1: Преминаване на предварителна поръчка
В този метод на преминаване ще преминем през възлите в посока от parent_node->left_child->right_child .
невалиден предварителна поръчка ( възел * корен ) {ако ( корен ) {
printf ( '%д \н ' , корен -> данни ) ;
показване_предварителна_поръчка ( корен -> наляво ) ;
показване_предварителна_поръчка ( корен -> точно ) ;
}
}
2: Преминаване след поръчка
В този метод на преминаване ще преминем през възлите в посока от ляво_дете->дясно_дете->родителски_възел-> .
невалиден покажи_пост_поръчка ( възел * корен ) {ако ( двоично_дърво ) {
покажи_пост_поръчка ( корен -> наляво ) ;
покажи_пост_поръчка ( корен -> точно ) ;
printf ( '%д \н ' , корен -> данни ) ;
}
}
3: Обхождане по ред
В този метод на преминаване ще преминем през възлите в посока от ляв_възел->корен_дете->дясно_дете .
невалиден дисплей_по_ред ( възел * корен ) {ако ( двоично_дърво ) {
дисплей_по_ред ( корен -> наляво ) ;
printf ( '%д \н ' , корен -> данни ) ;
дисплей_по_ред ( корен -> точно ) ;
}
}
Стъпка 5: Извършете изтриване в двоично дърво
Можем да изтрием създаденото Двоично дърво чрез изтриване на двете деца с функцията родителски възел в C, както следва.
невалиден delete_t ( възел * корен ) {ако ( корен ) {
delete_t ( корен -> наляво ) ;
delete_t ( корен -> точно ) ;
Безплатно ( корен ) ;
}
}
C програма за двоично дърво за търсене
Следното е пълното внедряване на двоично дърво за търсене в C програмиране:
#include#include
структура възел {
вътр стойност ;
структура възел * наляво , * точно ;
} ;
структура възел * възел1 ( вътр данни ) {
структура възел * tmp = ( структура възел * ) malloc ( размер на ( структура възел ) ) ;
tmp -> стойност = данни ;
tmp -> наляво = tmp -> точно = НУЛА ;
връщане tmp ;
}
невалиден печат ( структура възел * корен_възел ) // показване на възлите!
{
ако ( корен_възел != НУЛА ) {
печат ( корен_възел -> наляво ) ;
printf ( '%д \н ' , корен_възел -> стойност ) ;
печат ( корен_възел -> точно ) ;
}
}
структура възел * вмъкване_възел ( структура възел * възел , вътр данни ) // вмъкване на възли!
{
ако ( възел == НУЛА ) връщане възел1 ( данни ) ;
ако ( данни < възел -> стойност ) {
възел -> наляво = вмъкване_възел ( възел -> наляво , данни ) ;
} друго ако ( данни > възел -> стойност ) {
възел -> точно = вмъкване_възел ( възел -> точно , данни ) ;
}
връщане възел ;
}
вътр основен ( ) {
printf ( „C реализация на двоично дърво за търсене! \н \н ' ) ;
структура възел * родител = НУЛА ;
родител = вмъкване_възел ( родител , 10 ) ;
вмъкване_възел ( родител , 4 ) ;
вмъкване_възел ( родител , 66 ) ;
вмъкване_възел ( родител , Четири пет ) ;
вмъкване_възел ( родител , 9 ) ;
вмъкване_възел ( родител , 7 ) ;
печат ( родител ) ;
връщане 0 ;
}
В горния код първо декларираме a възел използвайки структура . След това инициализираме нов възел като „ възел1 ” и динамично разпределете памет с помощта на malloc() в C с данни и два указателя тип деца, използвайки декларирания възел. След това показваме възела от printf() функция и я извикайте в основен () функция. Тогава вмъкване_възел() се създава функция, където ако данните за възел са NULL, тогава възел1 е пенсиониран, в противен случай данните се поставят в възел (родител) на лявото и дясното дете. Програмата започва да се изпълнява от основен () функция, която генерира възел, използвайки няколко примерни възела като деца и след това използва методи за преминаване по ред, за да отпечата съдържанието на възела.
Изход
Заключение
Дърветата често се използват за съхраняване на данни в нелинейна форма. Двоични дървета са типове дървета, при които всеки възел (родител) има две потомци лявото дете и дясното дете. А двоично дърво е универсален метод за прехвърляне и съхранение на данни. Той е по-ефективен в сравнение със Linked-List в C. В горната статия видяхме концепцията за Двоично дърво с поетапното внедряване на a Двоично дърво за търсене в C.