|
Áèíaðíîå äåðåâî — ýòî äèíaìè÷åñêaя ñòðóêòóða äaííûõ, ñîñòîяùaя èç óçëîâ, êa- æäûé èç êîòîðûõ ñîäåðæèò, êðîìå äaííûõ, íå áîëåå äâóõ ññûëîê ía ðaçëè÷íûå áèíaðíûå äåðåâüя. Ía êaæäûé óçåë èìååòñя ðîâíî îäía ññûëêa. Ía÷aëüíûé óçåë íaçûâaåòñя nîðíåì äåðåâa.
Ía ðèñóíêå 3.3 ïðèâåäåí ïðèìåð áèíaðíîãî äåðåâa (êîðåíü îáû÷íî èçîáðaæaåòñя ñâåðõó, âïðî÷åì, êíèãó ìîæíî è ïåðåâåðíóòü)1. Óçåë, íå èìåþùèé ïîääåðåâüåâ, íaçûâaåòñя ëèñòîì. Èñõîäяùèå óçëû íaçûâaþòñя ïðåäêaìè, âõîäяùèå — ïîòîì- êaìè. Âûñîòa äåðåâa îïðåäåëяåòñя êîëè÷åñòâîì óðîâíåé, ía êîòîðûõ ðañïîëaãa- þòñя åãî óçëû.
Åñëè äåðåâî îðãaíèçîâaíî òaêèì îáðaçîì, ÷òî äëя êaæäîãî óçëa âñå êëþ÷è åãî ëå- âîãî ïîääåðåâa ìåíüøå êëþ÷a ýòîãî óçëa, a âñå êëþ÷è åãî ïðaâîãî ïîääåðåâa — áîëüøå, îíî íaçûâaåòñя äåðåâîì ïîèñna. Îäèíaêîâûå êëþ÷è íå äîïóñêaþòñя.  äåðåâå ïîèñêa ìîæíî íaéòè ýëåìåíò ïî êëþ÷ó2, äâèãaяñü îò êîðíя è ïåðåõîäя
1 Íóæíî íå çaáûâaòü î òîì, ÷òî â îïåðaòèâíîé ïaìяòè я÷åéêè ðañïîëîæåíû ëèíåéíî ïî âîçðañòaíèþ aäðåñîâ, a äåðåâî — ýòî òîëüêî ìåòîä ëîãè÷åñêîé îðãaíèçaöèè äaííûõ.
2 Äëя òaê íaçûâaåìîãî ñáaëaíñèðîâaííîãî äåðåâa, â êîòîðîì êîëè÷åñòâî óçëîâ ñïðaâa è ñëå- âa îòëè÷aåòñя íå áîëåå ÷åì ía åäèíèöó, âûñîòa äåðåâa ðaâía äâîè÷íîìó ëîãaðèôìó êîëè-
÷åñòâa óçëîâ. Ëèíåéíûé ñïèñîê ìîæíî ïðåäñòaâèòü êaê âûðîæäåííîå áèíaðíîå äåðåâî, â êîòîðîì êaæäûé óçåë èìååò íå áîëåå îäíîé ññûëêè. Äëя ñïèñêa ñðåäíåå âðåìя ïîèñêa ðaâíî ïîëîâèíå äëèíû ñïèñêa.
ía ëåâîå èëè ïðaâîå ïîääåðåâî â çaâèñèìîñòè îò çía÷åíèя êëþ÷a â êaæäîì óçëå. Òaêîé ïîèñê ãîðaçäî ýôôåêòèâíåå ïîèñêa ïî ñïèñêó, ïîñêîëüêó âðåìя ïîèñêa îïðåäåëяåòñя âûñîòîé äåðåâa, a îía ïðîïîðöèîíaëüía äâîè÷íîìó ëîãaðèôìó êî- ëè÷åñòâa óçëîâ.
Рис. 3.3. Бинарное дерево
Äåðåâî яâëяåòñя ðåêóðñèâíîé ñòðóêòóðîé äaííûõ, ïîñêîëüêó êaæäîå ïîääåðåâî òaêæå яâëяåòñя äåðåâîì. Äåéñòâèя ñ òaêèìè ñòðóêòóðaìè èçяùíåå âñåãî îïèñû- âaþòñя ñ ïîìîùüþ ðånóðñèâíûõ aëãîðèòìîâ. Íaïðèìåð, ôóíêöèþ îáõîäa âñåõ óç- ëîâ äåðåâa â îáùåì âèäå ìîæíî îïèñaòü òaê:
funCtiOn way_arOund ( äåðåâî ){ way_arOund ( ëåâîå ïîääåðåâî ) ïîñåùåíèå êîðíя
way_arOund ( ïðaâîå ïîääåðåâî )
}
Ìîæíî îáõîäèòü äåðåâî è â äðóãîì ïîðяäêå, íaïðèìåð, ñía÷aëa êîðåíü, ïîòîì ïîääåðåâüя, íî ïðèâåäåííaя ôóíêöèя ïîçâîëяåò ïîëó÷èòü ía âûõîäå îòñîðòèðî- âaííóþ ïîñëåäîâaòåëüíîñòü êëþ÷åé, ïîñêîëüêó ñía÷aëa ïîñåùaþòñя âåðøèíû ñ ìåíüøèìè êëþ÷aìè, ðañïîëîæåííûå â ëåâîì ïîääåðåâå. Ðåçóëüòaò îáõîäa äåðå- âa, èçîáðaæåííîãî ía ðèñ. 3.3:
1, 6, 8, 10, 20, 21, 25, 30
Åñëè â ôóíêöèè îáõîäa ïåðâîå îáðaùåíèå èäåò ê ïðaâîìó ïîääåðåâó, ðåçóëüòaò îáõîäa áóäåò äðóãèì:
30, 25, 21, 20, 10, 8, 6, 1
Òaêèì îáðaçîì, äåðåâüя ïîèñêa ìîæíî ïðèìåíяòü äëя ñîðòèðîâêè çía÷åíèé. Ïðè îáõîäå äåðåâa óçëû íå óäaëяþòñя.
Äëя áèíaðíûõ äåðåâüåâ îïðåäåëåíû îïåðaöèè:
âêëþ÷åíèя óçëa â äåðåâî;
ïîèñêa ïî äåðåâó;
îáõîäa äåðåâa;
óäaëåíèя óçëa.
Äëя êaæäîãî ðåêóðñèâíîãî aëãîðèòìa ìîæíî ñîçäaòü åãî íåðåêóðñèâíûé ýêâèâa- ëåíò.  ïðèâåäåííîé íèæå ïðîãðaììå ðåaëèçîâaía íåðåêóðñèâíaя ôóínöèя ïîèñ- na ïî äåðåâó ñ ânëþ÷åíèåì è ðåêóðñèâíaя ôóíêöèя îáõîäa äåðåâa. Ïåðâaя ôóíê- öèя îñóùåñòâëяåò ïîèñê ýëåìåíòa ñ çaäaííûì êëþ÷îì. Åñëè ýëåìåíò íaéäåí, îía âîçâðaùaåò óêaçaòåëü ía íåãî, a åñëè íåò — âêëþ÷aåò ýëåìåíò â ñîîòâåòñòâóþùåå ìåñòî äåðåâa è âîçâðaùaåò óêaçaòåëü ía íåãî. Äëя âêëþ÷åíèя ýëåìåíòa íåîáõîäè- ìî ïîìíèòü ïðîéäåííûé ïî äåðåâó ïóòü ía îäèí øaã íaçaä è çíaòü, âûïîëíяåòñя ëè âêëþ÷åíèå íîâîãî ýëåìåíòa â ëåâîå èëè ïðaâîå ïîääåðåâî åãî ïðåäêa1.
Ïðîãðaììa ôîðìèðóåò äåðåâî èç ìaññèâa öåëûõ ÷èñåë è âûâîäèò åãî ía ýêðaí.
inClude struCt NOde{
int d;
NOde *left;
NOde *right;
};
NOde * first(int d);
NOde * searCh_insert(NOde *rOOt, int d); vOid print_tree(NOde *rOOt, int l);
//------------------------------------------------
int main(){
int b[] = {10, 25, 20, 6, 21, 8, 1, 30};
NOde *rOOt = first(b[0]);
fOr (inti= 1; i<8; i++) searCh_insert(rOOt, b[i]); print_tree(rOOt, 0);
return 0;
}
//------------------------------------------------
// Ôîðìèðîâaíèå ïåðâîãî ýëåìåíòa äåðåâa NOde * first(int d){
NOde *pv = new NOde;
1 «Äîâîëüíî åñòåñòâåííî èñïûòûâaòü íåêîòîðîå íåäîâåðèå ê aëãîðèòìó ïîèñêa ïî äåðåâó ñ âêëþ÷åíèåì» — Í. Âèðò, aâòîð êëaññè÷åñêîé êíèãè «Àëãîðèòìû + ñòðóêòóðû äaííûõ = ïðîãðaììû» [8].
pv->d = d; pv->left = 0;
pv->right = 0; return pv;
}
//------------------------------------------------
// Ïîèñê ñ âêëþ÷åíèåì
NOde * searCh_insert(NOde *rOOt, int d){ NOde *pv= rOOt, *prev;
bOOl fOund = false; while (pv&& !fOund){
prev= pv;
if (d == pv->d) fOund = true; else if (d < pv->d) pv = pv->left;
else pv = pv->right;
}
if (fOund) return pv;
// Cîçäaíèå íîâîãî óçëa:
NOde *pnew = new NOde; pnew->d = d;
pnew->left = 0;
pnew->right = 0; if (d < prev->d)
// Ïðèñîåäèíåíèå ê ëåâîìó ïîääåðåâó ïðåäêa: prev->left = pnew;
else
// Ïðèñîåäèíåíèå ê ïðaâîìó ïîääåðåâó ïðåäêa: prev->right = pnew;
return pnew;
}
//------------------------------------------------
// Îáõîä äåðåâa
vOid print_tree(NOde *p, int level){ if (p){
print_tree(p->left, level + 1); // âûâîä ëåâîãî ïîääåðåâa fOr (inti= 0; iCOut << p->d << endl; // âûâîä êîðíя ïîääåðåâa print_tree(p->right, level + 1); // âûâîä ïðaâîãî ïîääåðåâa
}
}
Òåêóùèé óêaçaòåëü äëя ïîèñêa ïî äåðåâó îáîçía÷åí pv, óêaçaòåëü ía ïðåäêa pv
îáîçía÷åí prev, ïåðåìåííaя pnew èñïîëüçóåòñя äëя âûäåëåíèя ïaìяòè ïîä âêëþ-
÷aåìûé â äåðåâî óçåë. Ðåêóðñèè óäaëîñü èçáåæaòü, ñîõðaíèâ âñåãî îäíó ïåðåìåí- íóþ (prev) è ïîâòîðèâ ïðè âêëþ÷åíèè îïåðaòîðû, îïðåäåëяþùèå, ê êaêîìó ïîä- äåðåâó ïðèñîåäèíяåòñя íîâûé óçåë.
Ðåçóëüòaò ðaáîòû ïðîãðaììû äëя äåðåâa, èçîáðaæåííîãî ía ðèñ. 3.3:
1
6
8
10
20
21
25
30
Ðaññìîòðèì ïîäðîáíåå ôóínöèþ îáõîäa äåðåâa. Âòîðûì ïaðaìåòðîì â íåå ïåðåäa- åòñя öåëaя ïåðåìåííaя, îïðåäåëяþùaя, ía êaêîì óðîâíå íaõîäèòñя óçåë. Êîðåíü íaõîäèòñя ía óðîâíå 0. Äåðåâî ïå÷aòaåòñя ïî ãîðèçîíòaëè òaê, ÷òî êîðåíü íaõî- äèòñя ñëåâa (ïîñìîòðèòå ía ðåçóëüòaò ðaáîòû ïðîãðaììû, íaêëîíèâ ãîëîâó âëå- âî, è ñðaâíèòå ñ ðèñ. 3.3). Ïåðåä çía÷åíèåì óçëa äëя èìèòaöèè ñòðóêòóðû äåðåâa âûâîäèòñя êîëè÷åñòâî ïðîáåëîâ, ïðîïîðöèîíaëüíîå óðîâíþ óçëa. Åñëè çaêîì- ìåíòèðîâaòü öèêë ïå÷aòè ïðîáåëîâ, îòñîðòèðîâaííûé ïî âîçðañòaíèþ ìaññèâ áó- äåò âûâåäåí â ñòîëáèê. Çaìåòüòå, ÷òî ôóíêöèя îáõîäa äåðåâa äëèíîé âñåãî â íå- ñêîëüêî ñòðîê ìîæåò íaïå÷aòaòü äåðåâî ëþáîãî ðaçìåða — âaæíî òîëüêî ñëåäèòü,
÷òîáû ðåêóðñèâíûå âûçîâû íå ïåðåïîëíèëè ñòåê.
Óäaëåíèå óçëa èç äåðåâa ïðåäñòaâëяåò ñîáîé íå òaêóþ ïðîñòóþ çaäa÷ó, ïîñêîëüêó óäaëяåìûé óçåë ìîæåò áûòü êîðíåâûì, ñîäåðæaòü äâå, îäíó èëè íè îäíîé ññûëêè ía ïîääåðåâüя. Äëя óçëîâ, ñîäåðæaùèõ ìåíüøå äâóõ ññûëîê, óäaëåíèå òðèâèaëü- íî. ×òîáû ñîõðaíèòü óïîðяäî÷åííîñòü äåðåâa ïðè óäaëåíèè óçëa ñ äâóìя ññûëêa- ìè, åãî çaìåíяþò ía óçåë ñ ñaìûì áëèçêèì ê íåìó êëþ÷îì. Ýòî ìîæåò áûòü ña- ìûé ëåâûé óçåë åãî ïðaâîãî ïîääåðåâa èëè ñaìûé ïðaâûé óçåë ëåâîãî ïîääåðåâa (íaïðèìåð, ÷òîáû óäaëèòü èç äåðåâa ía ðèñ. 3.3 óçåë ñ êëþ÷îì 25, åãî íóæíî çaìå- íèòü ía 21 èëè 30, óçåë 10 çaìåíяåòñя ía 20 èëè 8, è ò. ä.). Ðåaëèçaöèя ôóíêöèè óäaëåíèя èç äåðåâa îñòaâëåía ÷èòaòåëþ äëя ñaìîñòîяòåëüíîé ðaáîòû.
Do'stlaringiz bilan baham: |
