Бинарно дрво у Ц
У Ц, а бинарно дрво је инстанца структуре података у стаблу са родитељским чвором који може имати максималан број два подређена чвора; 0, 1 или 2 потомка чвора. Сваки појединачни чвор у а бинарно дрво има сопствену вредност и два показивача на своју децу, један показивач за лево дете, а други за десно дете.
Декларација бинарног стабла
А бинарно дрво може се декларисати у Ц-у помоћу објекта под називом струцт који приказује један од чворова у стаблу.
струцт чвор {
тип података име_варијанте ;
струцт чвор * лево ;
струцт чвор * јел тако ;
} ;
Изнад је једна декларација бинарно дрво име чвора као чвор. Садржи три вредности; једна је променљива за складиштење података, а друге две су показивачи на дете. (лево и десно дете родитељског чвора).
Чињенице о бинарном стаблу
Чак и за велике скупове података, користећи а бинарно дрво чини претрагу лакшим и бржим. Број грана дрвећа није ограничен. За разлику од низа, дрвеће било које врсте се може направити и повећати на основу онога што се захтева од појединца.
Имплементација бинарног стабла у Ц
Следи водич корак по корак за имплементацију а Бинарно дрво у Ц.
Корак 1: Декларишите стабло бинарног претраживања
Креирајте чвор структуре који има три типа података, као што су подаци, *лефт_цхилд и *ригхт_цхилд, где подаци могу бити целобројног типа, а и *лефт_цхилд и *ригхт_цхилд чворови могу бити декларисани као НУЛЛ или не.
струцт чвор{
инт података ;
струцт чвор * ригхт_цхилд ;
струцт чвор * лефт_цхилд ;
} ;
Корак 2: Креирајте нове чворове у стаблу бинарног претраживања
Креирајте нови чвор креирањем функције која прихвата цео број као аргумент и пружа показивач на нови чвор креиран са том вредношћу. Користите функцију маллоц() у Ц-у за динамичку алокацију меморије за креирани чвор. Иницијализујте лево и десно дете на НУЛЛ и вратите име чвора.
струцт чвор * Креирај ( дататипе дата )
{
струцт чвор * нодеНаме = маллоц ( величина ( струцт чвор ) ) ;
нодеНаме -> података = вредност ;
нодеНаме -> лефт_цхилд = нодеНаме -> ригхт_цхилд = НУЛА ;
повратак нодеНаме ;
}
Корак 3: Уметните десну и леву децу у бинарно стабло
Креирајте функције инсерт_лефт и инсерт_ригхт које ће прихватити два улаза, а то су вредност која се убацује и показивач на чвор на који ће оба детета бити повезана. Позовите функцију креирања да бисте креирали нови чвор и доделили враћени показивач левом показивачу левог детета или десном показивачу десног детета коренског родитеља.
струцт чвор * инсерт_лефт ( струцт чвор * корен , дататипе дата ) {корен -> лево = Креирај ( података ) ;
повратак корен -> лево ;
}
струцт чвор * инсерт_ригхт ( струцт чвор * корен , дататипе дата ) {
корен -> јел тако = Креирај ( података ) ;
повратак корен -> јел тако ;
}
Корак 4: Прикажите чворове бинарног стабла користећи методе преласка
Можемо приказати стабла користећи три методе преласка у Ц. Ове методе преласка су:
1: Пре-Ордер Траверсал
У овој методи преласка, пролазићемо кроз чворове у правцу од родитељ_чвор->лево_дете->десно_дете .
празнина пре_ордер ( чвор * корен ) {ако ( корен ) {
принтф ( „%д \н ' , корен -> података ) ;
дисплаи_пре_ордер ( корен -> лево ) ;
дисплаи_пре_ордер ( корен -> јел тако ) ;
}
}
2: Прелазак након поруџбине
У овој методи преласка, пролазићемо кроз чворове у правцу од лево_дете->десно_дете->родитељски_чвор-> .
празнина дисплаи_пост_ордер ( чвор * корен ) {ако ( бинарно_дрво ) {
дисплаи_пост_ордер ( корен -> лево ) ;
дисплаи_пост_ордер ( корен -> јел тако ) ;
принтф ( „%д \н ' , корен -> података ) ;
}
}
3: Прелазак по наруџбини
У овој методи преласка, пролазићемо кроз чворове у правцу од леви_чвор->коренско_дете->десно_дете .
празнина дисплаи_ин_ордер ( чвор * корен ) {ако ( бинарно_дрво ) {
дисплаи_ин_ордер ( корен -> лево ) ;
принтф ( „%д \н ' , корен -> података ) ;
дисплаи_ин_ордер ( корен -> јел тако ) ;
}
}
Корак 5: Извршите брисање у бинарном стаблу
Можемо избрисати креиране Бинарно дрво брисањем оба детета са функцијом родитељског чвора у Ц-у на следећи начин.
празнина делете_т ( чвор * корен ) {ако ( корен ) {
делете_т ( корен -> лево ) ;
делете_т ( корен -> јел тако ) ;
бесплатно ( корен ) ;
}
}
Ц Програм стабла бинарног претраживања
Следи комплетна имплементација стабла бинарног претраживања у Ц програмирању:
#инцлуде<стдио.х>#инцлуде<стдлиб.х>
струцт чвор {
инт вредност ;
струцт чвор * лево , * јел тако ;
} ;
струцт чвор * ноде1 ( инт података ) {
струцт чвор * тмп = ( струцт чвор * ) маллоц ( величина ( струцт чвор ) ) ;
тмп -> вредност = података ;
тмп -> лево = тмп -> јел тако = НУЛА ;
повратак тмп ;
}
празнина принт ( струцт чвор * роот_ноде ) // приказује чворове!
{
ако ( роот_ноде != НУЛА ) {
принт ( роот_ноде -> лево ) ;
принтф ( „%д \н ' , роот_ноде -> вредност ) ;
принт ( роот_ноде -> јел тако ) ;
}
}
струцт чвор * инсерт_ноде ( струцт чвор * чвор , инт података ) // убацивање чворова!
{
ако ( чвор == НУЛА ) повратак ноде1 ( података ) ;
ако ( података < чвор -> вредност ) {
чвор -> лево = инсерт_ноде ( чвор -> лево , података ) ;
} друго ако ( података > чвор -> вредност ) {
чвор -> јел тако = инсерт_ноде ( чвор -> јел тако , података ) ;
}
повратак чвор ;
}
инт главни ( ) {
принтф ( „Ц имплементација стабла бинарног претраживања! \н \н ' ) ;
струцт чвор * родитељ = НУЛА ;
родитељ = инсерт_ноде ( родитељ , 10 ) ;
инсерт_ноде ( родитељ , 4 ) ;
инсерт_ноде ( родитељ , 66 ) ;
инсерт_ноде ( родитељ , Четири, пет ) ;
инсерт_ноде ( родитељ , 9 ) ;
инсерт_ноде ( родитељ , 7 ) ;
принт ( родитељ ) ;
повратак 0 ;
}
У горњем коду прво декларишемо а чвор Користећи струцт . Затим иницијализујемо нови чвор као „ ноде1 ” и динамички додељује меморију користећи маллоц() у Ц са подацима и два показивача укуцајте децу користећи декларисани чвор. Након овога приказујемо чвор по принтф() функцију и позовите је у главни() функција. Затим инсертион_ноде() креира се функција, где ако су подаци о чвору НУЛЛ онда ноде1 је повучен, у супротном подаци се стављају у чвор (родитељ) левог и десног детета. Програм почиње да се извршава од главни() функција, која генерише чвор користећи неколико узоркованих чворова као деце, а затим користи методе преласка у поретку за штампање садржаја чвора.
Излаз
Закључак
Стабла се често користе за чување података у нелинеарном облику. Бинарно дрвеће су врсте стабала где сваки чвор (родитељ) има два потомка лево дете и десно дете. А бинарно дрво је свестран метод преноса и складиштења података. Ефикаснији је у поређењу са Линкед-Листом у Ц. У горњем чланку смо видели концепт Бинарно дрво уз имплементацију корак по корак а Бинарно стабло претраге у Ц.