సి లో బైనరీ ట్రీ
C లో, a బైనరీ చెట్టు గరిష్ట సంఖ్యలో రెండు చైల్డ్ నోడ్లను కలిగి ఉండే పేరెంట్ నోడ్తో ట్రీ డేటా స్ట్రక్చర్ యొక్క ఉదాహరణ; 0, 1, లేదా 2 సంతానం నోడ్లు. a లోని ప్రతి ఒక్క నోడ్ బైనరీ చెట్టు దాని స్వంత విలువను కలిగి ఉంది మరియు దాని పిల్లలకు రెండు పాయింటర్లు ఉన్నాయి, ఎడమ పిల్లవాడికి ఒక పాయింటర్ మరియు మరొకటి కుడి పిల్లవాడికి.
బైనరీ ట్రీ డిక్లరేషన్
ఎ బైనరీ చెట్టు అనే వస్తువును ఉపయోగించి C లో ప్రకటించవచ్చు నిర్మాణం అది చెట్టులోని నోడ్లలో ఒకదానిని వర్ణిస్తుంది.
నిర్మాణం నోడ్ {
డేటాటైప్ var_name ;
నిర్మాణం నోడ్ * వదిలేశారు ;
నిర్మాణం నోడ్ * కుడి ;
} ;
పైన ఒక డిక్లరేషన్ ఉంది బైనరీ చెట్టు నోడ్ పేరు నోడ్గా. ఇది మూడు విలువలను కలిగి ఉంది; ఒకటి డేటా-స్టోరింగ్ వేరియబుల్ మరియు ఇతర రెండు పిల్లలకి పాయింటర్లు. (పేరెంట్ నోడ్ యొక్క ఎడమ మరియు కుడి చైల్డ్).
బైనరీ ట్రీ యొక్క వాస్తవాలు
పెద్ద డేటా సెట్ల కోసం కూడా, aని ఉపయోగించడం బైనరీ చెట్టు శోధనను సులభంగా మరియు వేగంగా చేస్తుంది. చెట్ల కొమ్మల సంఖ్య పరిమితం కాదు. శ్రేణికి విరుద్ధంగా, ఒక వ్యక్తికి అవసరమైన వాటి ఆధారంగా ఏ రకమైన చెట్లను అయినా తయారు చేయవచ్చు మరియు పెంచవచ్చు.
సి లో బైనరీ ట్రీ ఇంప్లిమెంటేషన్
అమలు చేయడానికి క్రింది దశల వారీ మార్గదర్శిని బైనరీ ట్రీ C లో
దశ 1: బైనరీ శోధన చెట్టును ప్రకటించండి
డేటా, *left_child మరియు *right_child వంటి మూడు రకాల డేటాను కలిగి ఉండే స్ట్రక్ట్ నోడ్ను సృష్టించండి, ఇక్కడ డేటా పూర్ణాంకం రకంగా ఉంటుంది మరియు *left_child మరియు *right_child నోడ్లు రెండూ NULLగా లేదా ప్రకటించబడవు.
నిర్మాణం నోడ్{
int సమాచారం ;
నిర్మాణం నోడ్ * కుడి_బిడ్డ ;
నిర్మాణం నోడ్ * ఎడమ_బిడ్డ ;
} ;
దశ 2: బైనరీ సెర్చ్ ట్రీలో కొత్త నోడ్లను సృష్టించండి
పూర్ణాంకాన్ని ఆర్గ్యుమెంట్గా అంగీకరించే ఫంక్షన్ను సృష్టించడం ద్వారా కొత్త నోడ్ను సృష్టించండి మరియు ఆ విలువతో సృష్టించబడిన కొత్త నోడ్కు పాయింటర్ను అందిస్తుంది. సృష్టించబడిన నోడ్ కోసం డైనమిక్ మెమరీ కేటాయింపు కోసం C లో malloc() ఫంక్షన్ని ఉపయోగించండి. ఎడమ మరియు కుడి చైల్డ్ని NULLకి ప్రారంభించి, nodeNameని తిరిగి ఇవ్వండి.
నిర్మాణం నోడ్ * సృష్టించు ( డేటాటైప్ డేటా )
{
నిర్మాణం నోడ్ * నోడ్ పేరు = malloc ( పరిమాణం ( నిర్మాణం నోడ్ ) ) ;
నోడ్ పేరు -> సమాచారం = విలువ ;
నోడ్ పేరు -> ఎడమ_బిడ్డ = నోడ్ పేరు -> కుడి_బిడ్డ = శూన్య ;
తిరిగి నోడ్ పేరు ;
}
దశ 3: బైనరీ ట్రీలో కుడి మరియు ఎడమ పిల్లలను చొప్పించండి
రెండు ఇన్పుట్లను ఆమోదించే ఇన్సర్ట్_లెఫ్ట్ మరియు ఇన్సర్ట్_రైట్ ఫంక్షన్లను సృష్టించండి, అవి చొప్పించాల్సిన విలువ మరియు ఇద్దరు పిల్లలు కనెక్ట్ చేయబడే నోడ్కి పాయింటర్. కొత్త నోడ్ని సృష్టించడానికి క్రియేట్ ఫంక్షన్కు కాల్ చేయండి మరియు రిటర్న్ చేసిన పాయింటర్ని ఎడమ చైల్డ్ ఎడమ పాయింటర్కి లేదా రూట్ పేరెంట్ యొక్క కుడి చైల్డ్ కుడి పాయింటర్కి కేటాయించండి.
నిర్మాణం నోడ్ * ఇన్సర్ట్_ఎడమ ( నిర్మాణం నోడ్ * రూట్ , డేటాటైప్ డేటా ) {రూట్ -> వదిలేశారు = సృష్టించు ( సమాచారం ) ;
తిరిగి రూట్ -> వదిలేశారు ;
}
నిర్మాణం నోడ్ * ఇన్సర్ట్_కుడి ( నిర్మాణం నోడ్ * రూట్ , డేటాటైప్ డేటా ) {
రూట్ -> కుడి = సృష్టించు ( సమాచారం ) ;
తిరిగి రూట్ -> కుడి ;
}
దశ 4: ట్రావర్సల్ మెథడ్స్ ఉపయోగించి బైనరీ ట్రీ నోడ్లను ప్రదర్శించండి
C లో ట్రావర్సల్ యొక్క మూడు పద్ధతులను ఉపయోగించడం ద్వారా మేము చెట్లను ప్రదర్శించవచ్చు. ఈ ట్రావర్సల్ పద్ధతులు:
1: ప్రీ-ఆర్డర్ ట్రావర్సల్
ఈ ట్రావర్సల్ పద్ధతిలో, మేము నోడ్స్ నుండి ఒక దిశలో వెళ్తాము parent_node->left_child->right_child .
శూన్యం ముందస్తు ఉత్తర్వులు ( నోడ్ * రూట్ ) {ఉంటే ( రూట్ ) {
printf ( '%d \n ' , రూట్ -> సమాచారం ) ;
display_pre_order ( రూట్ -> వదిలేశారు ) ;
display_pre_order ( రూట్ -> కుడి ) ;
}
}
2: పోస్ట్-ఆర్డర్ ట్రావర్సల్
ఈ ట్రావర్సల్ పద్ధతిలో, మేము నోడ్ల ద్వారా ఒక దిశలో వెళ్తాము left_child->right_child->parent_node-> .
శూన్యం display_post_order ( నోడ్ * రూట్ ) {ఉంటే ( బైనరీ_చెట్టు ) {
display_post_order ( రూట్ -> వదిలేశారు ) ;
display_post_order ( రూట్ -> కుడి ) ;
printf ( '%d \n ' , రూట్ -> సమాచారం ) ;
}
}
3: ఇన్-ఆర్డర్ ట్రావర్సల్
ఈ ట్రావర్సల్ పద్ధతిలో, మేము నోడ్స్ నుండి ఒక దిశలో వెళ్తాము left_node->root_child->right_child .
శూన్యం డిస్ప్లే_ఇన్_ఆర్డర్ ( నోడ్ * రూట్ ) {ఉంటే ( బైనరీ_చెట్టు ) {
డిస్ప్లే_ఇన్_ఆర్డర్ ( రూట్ -> వదిలేశారు ) ;
printf ( '%d \n ' , రూట్ -> సమాచారం ) ;
డిస్ప్లే_ఇన్_ఆర్డర్ ( రూట్ -> కుడి ) ;
}
}
దశ 5: బైనరీ ట్రీలో తొలగింపును జరుపుము
మేము సృష్టించిన వాటిని తొలగించవచ్చు బైనరీ ట్రీ C లో పేరెంట్ నోడ్ ఫంక్షన్తో పిల్లలిద్దరినీ ఈ క్రింది విధంగా తొలగించడం ద్వారా.
శూన్యం delete_t ( నోడ్ * రూట్ ) {ఉంటే ( రూట్ ) {
delete_t ( రూట్ -> వదిలేశారు ) ;
delete_t ( రూట్ -> కుడి ) ;
ఉచిత ( రూట్ ) ;
}
}
బైనరీ శోధన చెట్టు యొక్క సి ప్రోగ్రామ్
సి ప్రోగ్రామింగ్లో బైనరీ సెర్చ్ ట్రీ యొక్క పూర్తి అమలు క్రింది విధంగా ఉంది:
#include#include
నిర్మాణం నోడ్ {
int విలువ ;
నిర్మాణం నోడ్ * వదిలేశారు , * కుడి ;
} ;
నిర్మాణం నోడ్ * నోడ్1 ( int సమాచారం ) {
నిర్మాణం నోడ్ * tmp = ( నిర్మాణం నోడ్ * ) malloc ( పరిమాణం ( నిర్మాణం నోడ్ ) ) ;
tmp -> విలువ = సమాచారం ;
tmp -> వదిలేశారు = tmp -> కుడి = శూన్య ;
తిరిగి tmp ;
}
శూన్యం ముద్రణ ( నిర్మాణం నోడ్ * రూట్_నోడ్ ) // నోడ్లను ప్రదర్శిస్తోంది!
{
ఉంటే ( రూట్_నోడ్ != శూన్య ) {
ముద్రణ ( రూట్_నోడ్ -> వదిలేశారు ) ;
printf ( '%d \n ' , రూట్_నోడ్ -> విలువ ) ;
ముద్రణ ( రూట్_నోడ్ -> కుడి ) ;
}
}
నిర్మాణం నోడ్ * ఇన్సర్ట్_నోడ్ ( నిర్మాణం నోడ్ * నోడ్ , int సమాచారం ) // నోడ్లను చొప్పించడం!
{
ఉంటే ( నోడ్ == శూన్య ) తిరిగి నోడ్1 ( సమాచారం ) ;
ఉంటే ( సమాచారం < నోడ్ -> విలువ ) {
నోడ్ -> వదిలేశారు = ఇన్సర్ట్_నోడ్ ( నోడ్ -> వదిలేశారు , సమాచారం ) ;
} లేకపోతే ఉంటే ( సమాచారం > నోడ్ -> విలువ ) {
నోడ్ -> కుడి = ఇన్సర్ట్_నోడ్ ( నోడ్ -> కుడి , సమాచారం ) ;
}
తిరిగి నోడ్ ;
}
int ప్రధాన ( ) {
printf ( 'బైనరీ సెర్చ్ ట్రీ యొక్క సి అమలు! \n \n ' ) ;
నిర్మాణం నోడ్ * తల్లిదండ్రులు = శూన్య ;
తల్లిదండ్రులు = ఇన్సర్ట్_నోడ్ ( తల్లిదండ్రులు , 10 ) ;
ఇన్సర్ట్_నోడ్ ( తల్లిదండ్రులు , 4 ) ;
ఇన్సర్ట్_నోడ్ ( తల్లిదండ్రులు , 66 ) ;
ఇన్సర్ట్_నోడ్ ( తల్లిదండ్రులు , నాలుగు ఐదు ) ;
ఇన్సర్ట్_నోడ్ ( తల్లిదండ్రులు , 9 ) ;
ఇన్సర్ట్_నోడ్ ( తల్లిదండ్రులు , 7 ) ;
ముద్రణ ( తల్లిదండ్రులు ) ;
తిరిగి 0 ;
}
పై కోడ్లో, మేము మొదట a అని ప్రకటిస్తాము నోడ్ ఉపయోగించి నిర్మాణం . అప్పుడు మేము కొత్త నోడ్ని ప్రారంభిస్తాము ' నోడ్1 ” మరియు డైనమిక్గా ఉపయోగించి మెమరీని కేటాయించండి malloc() డేటా మరియు రెండు పాయింటర్లతో సిలో డిక్లేర్డ్ నోడ్ని ఉపయోగించి పిల్లలను టైప్ చేయండి. దీని తరువాత, మేము నోడ్ని ప్రదర్శిస్తాము printf() ఫంక్షన్ మరియు కాల్ ప్రధాన () ఫంక్షన్. అప్పుడు ది ఇన్సర్షన్_నోడ్() ఫంక్షన్ సృష్టించబడుతుంది, ఇక్కడ నోడ్ డేటా NULL అయితే నోడ్1 పదవీ విరమణ పొందారు, లేకపోతే డేటాలో ఉంచబడుతుంది నోడ్ (తల్లిదండ్రులు) ఎడమ మరియు కుడి పిల్లల. కార్యక్రమం నుండి అమలు ప్రారంభమవుతుంది ప్రధాన () ఫంక్షన్, ఇది పిల్లలుగా కొన్ని నమూనా నోడ్లను ఉపయోగించి నోడ్ను ఉత్పత్తి చేస్తుంది మరియు నోడ్ కంటెంట్లను ప్రింట్ చేయడానికి ఇన్-ఆర్డర్ ట్రావర్సల్ పద్ధతులను ఉపయోగిస్తుంది.
అవుట్పుట్
ముగింపు
డేటాను నాన్-లీనియర్ రూపంలో ఉంచడానికి చెట్లను తరచుగా ఉపయోగిస్తారు. బైనరీ చెట్లు ప్రతి నోడ్ (తల్లిదండ్రులు) ఎడమ బిడ్డ మరియు కుడి బిడ్డ ఇద్దరు సంతానం కలిగి ఉన్న చెట్ల రకాలు. ఎ బైనరీ చెట్టు డేటాను బదిలీ చేయడానికి మరియు నిల్వ చేయడానికి ఒక బహుముఖ పద్ధతి. C లోని లింక్డ్-లిస్ట్తో పోలిస్తే ఇది మరింత ప్రభావవంతంగా ఉంటుంది. పై కథనంలో, మేము ఒక భావనను చూశాము. బైనరీ ట్రీ ఒక దశల వారీ అమలుతో బైనరీ శోధన చెట్టు C లో