Binaarne puu C-s
C-s a kahendpuu on puu andmestruktuuri eksemplar koos emasõlmega, millel võib olla maksimaalselt kaks alamsõlme; 0, 1 või 2 järglaste sõlme. Iga sõlm punktis a kahendpuu on oma väärtus ja kaks viidat oma lastele, üks osuti vasakpoolsele ja teine õigele lapsele.
Binaarse puu deklaratsioon
A kahendpuu saab deklareerida C-s, kasutades objekti nimega struktuur mis kujutab ühte puu sõlme.
struktuur sõlm {
andmetüüp var_nimi ;
struktuur sõlm * vasakule ;
struktuur sõlm * õige ;
} ;
Eespool on ühe deklaratsioon kahendpuu sõlme nimi sõlmena. Sellel on kolm väärtust; üks on andmete salvestamise muutuja ja teised kaks on viidad lapsele. (vanemsõlme vasak ja parem alam).
Faktid kahendpuu kohta
Isegi suurte andmehulkade puhul, kasutades a kahendpuu muudab otsimise lihtsamaks ja kiiremaks. Puuokste arv ei ole piiratud. Erinevalt massiivist saab teha ja kasvatada mis tahes puid vastavalt sellele, mida üksikisikult nõutakse.
Binaarse puu juurutamine C-s
Järgnev on samm-sammuline juhend a rakendamiseks Binaarne puu C-s.
1. samm: deklareerige binaarne otsingupuu
Looge struktuurisõlm, millel on kolme tüüpi andmed, näiteks andmed, *vasak_laps ja *parem_laps, kus andmed võivad olla täisarvu tüüpi ja nii *vasak_laps- kui ka *parem_lapssõlmed saab deklareerida NULL-i või mitte.
struktuur sõlm{
int andmeid ;
struktuur sõlm * õige_laps ;
struktuur sõlm * vasak_laps ;
} ;
2. samm: looge binaarses otsingupuus uued sõlmed
Looge uus sõlm, luues funktsiooni, mis aktsepteerib argumendina täisarvu ja annab kursori selle väärtusega loodud uuele sõlmele. Kasutage loodud sõlme dünaamilise mälu eraldamiseks C-s funktsiooni malloc(). Initsialiseerige vasak ja parem alam NULL ja tagastage nodeName.
struktuur sõlm * luua ( andmetüübi andmed )
{
struktuur sõlm * nodeName = malloc ( suurus ( struktuur sõlm ) ) ;
nodeName -> andmeid = väärtus ;
nodeName -> vasak_laps = nodeName -> õige_laps = NULL ;
tagasi nodeName ;
}
3. samm: sisestage binaarpuusse parem- ja vasakpoolsed lapsed
Looge funktsioonid insert_left ja insert_right, mis aktsepteerivad kahte sisendit, mis on sisestatav väärtus ja kursor sõlmele, millega mõlemad lapsed ühendatakse. Uue sõlme loomiseks kutsuge välja loomise funktsioon ja määrake tagastatud kursor vasakpoolse alamkursori või juurvanema parempoolse alamkursori jaoks.
struktuur sõlm * sisesta_vasak ( struktuur sõlm * juur , andmetüübi andmed ) {juur -> vasakule = luua ( andmeid ) ;
tagasi juur -> vasakule ;
}
struktuur sõlm * sisesta_parem ( struktuur sõlm * juur , andmetüübi andmed ) {
juur -> õige = luua ( andmeid ) ;
tagasi juur -> õige ;
}
4. samm: kuvage binaarpuu sõlmed läbimismeetodite abil
Me saame kuvada puid, kasutades C-s kolme läbimise meetodit. Need läbimismeetodid on järgmised:
1: eeltellimuse läbimine
Selle läbimismeetodi puhul läbime sõlmed suunas alates vanem_sõlm->vasak_laps->parem_laps .
tühine ette_tellimine ( sõlm * juur ) {kui ( juur ) {
printf ( '%d \n ' , juur -> andmeid ) ;
display_pre_order ( juur -> vasakule ) ;
display_pre_order ( juur -> õige ) ;
}
}
2: Tellimusejärgne läbimine
Selle läbimismeetodi puhul läbime sõlmed suunas alates vasak_laps->parem_laps->vanema_sõlm-> .
tühine kuva_postitustellimus ( sõlm * juur ) {kui ( binaarne_puu ) {
kuva_postitustellimus ( juur -> vasakule ) ;
kuva_postitustellimus ( juur -> õige ) ;
printf ( '%d \n ' , juur -> andmeid ) ;
}
}
3: tellimuse läbimine
Selle läbimismeetodi puhul läbime sõlmed suunas alates vasak_sõlm->juurlaps->parem_laps .
tühine kuva_järjekorras ( sõlm * juur ) {kui ( binaarne_puu ) {
kuva_järjekorras ( juur -> vasakule ) ;
printf ( '%d \n ' , juur -> andmeid ) ;
kuva_järjekorras ( juur -> õige ) ;
}
}
5. samm: tehke binaarpuus kustutamine
Saame loodud kustutada Binaarne puu kustutades mõlemad C-s vanemsõlme funktsiooniga lapsed järgmiselt.
tühine kustuta_t ( sõlm * juur ) {kui ( juur ) {
kustuta_t ( juur -> vasakule ) ;
kustuta_t ( juur -> õige ) ;
tasuta ( juur ) ;
}
}
C Binaarse otsingupuu programm
Järgmine on binaarse otsingupuu täielik rakendamine C-programmeerimises:
#include#include
struktuur sõlm {
int väärtus ;
struktuur sõlm * vasakule , * õige ;
} ;
struktuur sõlm * sõlm1 ( int andmeid ) {
struktuur sõlm * tmp = ( struktuur sõlm * ) malloc ( suurus ( struktuur sõlm ) ) ;
tmp -> väärtus = andmeid ;
tmp -> vasakule = tmp -> õige = NULL ;
tagasi tmp ;
}
tühine printida ( struktuur sõlm * juur_sõlm ) // sõlmede kuvamine!
{
kui ( juur_sõlm != NULL ) {
printida ( juur_sõlm -> vasakule ) ;
printf ( '%d \n ' , juur_sõlm -> väärtus ) ;
printida ( juur_sõlm -> õige ) ;
}
}
struktuur sõlm * sisesta_sõlm ( struktuur sõlm * sõlm , int andmeid ) // sõlmede sisestamine!
{
kui ( sõlm == NULL ) tagasi sõlm1 ( andmeid ) ;
kui ( andmeid < sõlm -> väärtus ) {
sõlm -> vasakule = sisesta_sõlm ( sõlm -> vasakule , andmeid ) ;
} muidu kui ( andmeid > sõlm -> väärtus ) {
sõlm -> õige = sisesta_sõlm ( sõlm -> õige , andmeid ) ;
}
tagasi sõlm ;
}
int peamine ( ) {
printf ( Binaarse otsingupuu C juurutamine! \n \n ' ) ;
struktuur sõlm * lapsevanem = NULL ;
lapsevanem = sisesta_sõlm ( lapsevanem , 10 ) ;
sisesta_sõlm ( lapsevanem , 4 ) ;
sisesta_sõlm ( lapsevanem , 66 ) ;
sisesta_sõlm ( lapsevanem , Neli, viis ) ;
sisesta_sõlm ( lapsevanem , 9 ) ;
sisesta_sõlm ( lapsevanem , 7 ) ;
printida ( lapsevanem ) ;
tagasi 0 ;
}
Ülaltoodud koodis deklareerime esmalt a sõlm kasutades struktuur . Seejärel lähtestame uue sõlme kui ' sõlm1 ” ja eraldada mälu dünaamiliselt kasutades malloc() C-vormingus andmete ja kahe osutiga sisestage deklareeritud sõlme kasutades lapsed. Pärast seda kuvame sõlme poolt printf() funktsiooni ja kutsuge see sisse peamine () funktsiooni. Siis insertion_node() luuakse funktsioon, kus kui sõlme andmed on NULL, siis sõlm1 on pensionile jäänud, muidu paigutatakse andmed kausta sõlm vasaku ja parema lapse (vanem). Programm alustab täitmist alates peamine () funktsioon, mis genereerib sõlme, kasutades lapsena mõnda näidissõlme, ja kasutab seejärel sõlme sisu printimiseks In-Order läbimise meetodeid.
Väljund
Järeldus
Andmete mittelineaarsel kujul hoidmiseks kasutatakse sageli puid. Binaarsed puud on puutüübid, kus igal sõlmel (vanemal) on kaks järglast, vasak laps ja parem laps. A kahendpuu on mitmekülgne meetod andmete edastamiseks ja salvestamiseks. See on tõhusam võrreldes lingitud loendiga C-s. Ülaltoodud artiklis oleme näinud kontseptsiooni Binaarne puu samm-sammulise rakendamisega a Binaarne otsingupuu C-s.