[Powered by Google Translate] [7 વિભાગ] [ઓછી સાધારણ] [Nate Hardison] [હાર્વર્ડ યુનિવર્સિટી] [આ CS50 છે.] [CS50.TV] 

7 વિભાગ પર આપનું સ્વાગત છે. હરિકેન સેન્ડી માટે આભાર, તેના બદલે એક સામાન્ય વિભાગમાં આ અઠવાડિયે કર્યા છે, અમે આ કરી રહ્યા વોક દ્વારા પ્રશ્નો ના વિભાગ મારફત. હું સાથે સમસ્યા સાથે નીચેના કરી 6 સ્પષ્ટીકરણ સેટ કરો જાઉં છું, અને આ બધા પ્રશ્નોના પસાર થઇ પ્રશ્નો વિભાગમાં એક વિભાગ. જો ત્યાં કોઈપણ પ્રશ્નો છે, CS50 ચર્ચા પર પોસ્ટ કરો. 

ઓલરાઇટ. ચાલો શરૂ કરો. હમણાં હું સમસ્યા સેટ સ્પષ્ટીકરણ ઓફ પાનું 3 જોઈ રહ્યો છું. અમે પ્રથમ દ્વિસંગી વૃક્ષો વિશે વાત શરૂ જઈ રહ્યાં છો કારણ કે તે આ સપ્તાહ સમસ્યા સમૂહ અનુરૂપતા ઘણો હોય - આ હફમેનના વૃક્ષ એન્કોડિંગ. પહેલીવાર માહિતી બંધારણોની અમે CS50 પર વિશે વાત કરી એક એરે હતી. યાદ રાખો કે એક એરે તત્વોની શ્રેણી છે - આ જ પ્રકારની બધી - મેમરીનો એકબીજાની બાજુમાં સંગ્રહ થાય છે. જો હું પૂર્ણાંક એરે કે હું આ શૈલી બોક્સ-નંબરો-પૂર્ણાંકો મદદથી ડ્રો કરી શકો છો - હવે કહો કે હું પ્રથમ બોક્સમાં 5 હોય છે, હું બીજા 7 હોય, પછી હું 8, 10, અને અંતિમ બોક્સમાં 20 હોય છે. આ એરે વિશે યાદ રાખો, બે ખરેખર સારા વસ્તુઓ છે કે જે આપણે આ સતત સમય કોઇ ખાસ તત્વ વપરાશ હોય છે  એરે માં જો આપણે તેના અનુક્રમણિકા છો. ઉદાહરણ તરીકે, જો હું એરે ત્રીજા તત્વ ગ્રેબ માંગો છો - અનુક્રમણિકા પર 2 અમારી ઈન્ડેક્સીંગ શૂન્ય આધારિત સિસ્ટમ વાપરી - હું શાબ્દિક માત્ર એક સરળ ગાણિતિક ગણતરી કરવા હોય, એરે કે સ્થિતિમાં હોપ, આઉટ 8 કે ત્યાં સંગ્રહિત થાય છે ખેંચે છે, અને હું જવા માટે છું. 

આ એરે વિશે ખરાબ વસ્તુઓ એક - કે અમે વિશે વાત કરી જ્યારે અમે સાથે લિંક યાદીઓ ચર્ચા - કે જો હું આ એરે માં એક તત્વ સામેલ કરવા માંગો છો, હું કેટલાક આસપાસ ફરતું હોય તો જાઉં છું. ઉદાહરણ તરીકે, આ અધિકાર અહીં એરે ક્રમમાં છે - ચડતા ક્રમમાં સોર્ટ - 5, 7, તો પછી તે પછી 8, પછી 10, અને તે પછી 20 - પરંતુ જો હું આ એરે માં 9 નંબર દાખલ કરવા માંગો છો, હું તત્વો કેટલાક પાળી કરવા માટે જગ્યા કરવા હોય જાઉં છું. અમે આ દોરવા અહીં કરી શકો છો. હું 5 એ, 7 ના ખસેડવાનો જાઉં છું, અને પછી 8 ના; એક તફાવત જ્યાં હું 9 તે મૂકી શકો છો બનાવવા માટે, અને પછી 10 અને 20 9 નું અધિકાર જઈ શકો છો. આ એક પ્રકારની પીડા છે કારણ કે દૃશ્ય ખરાબ કિસ્સામાં - જ્યારે અમે સામેલ રહી છે, ક્યાં તો શરૂઆતમાં અથવા ઓવરને અંતે એરે ની, અમે કેવી રીતે તેના પર આધાર રાખીને સ્થળાંતર કરી રહ્યા છીએ - અમે અંત કરવા માટે બધા તત્વો પાળી રહી શકે છે કે અમે હાલમાં એરે માં સ્ટોર કરી રહ્યાં છે. 

તેથી, આ આસપાસ જે રીતે શું હતું? આ આસપાસ જે રીતે અમારી યાદી સાથે જોડાયેલી પદ્ધતિ જ્યાં જાઓ હતી - ને બદલે 5 તત્વો, 7, 8, 10, અને 20 બધી મેમરીનો એકબીજા માટે આગામી સ્ટોર કરવાનો - અમે શું તેના બદલે તેમને હતી સંગ્રહિત નહોતો ત્યાં અમે તેમનો સંગ્રહ કરવા માટે ઇચ્છતા પ્રકારની આ સાથે જોડાયેલી યાદી ગાંઠો જે હું ચિત્રકામ છું અહીં, તદર્થ પ્રકારની. અને પછી અમે તેમને એકસાથે જોડાયેલ આ આગામી પોઇંટરો મદદથી. હું 5 થી 7 માટે એક નિર્દેશક હોઇ શકે છે, આ 7 થી 8 એક નિર્દેશક, 8 થી 10 ના એક નિર્દેશક, અને છેલ્લે, 10 થી 20 માટે એક નિર્દેશક, અને પછી 20 ના અંતે એક નલ નિર્દેશક જે દર્શાવે છે કે ત્યાં ડાબી કશું જ નથી. વેપાર બોલ કે અમે અહીં છે કે હવે જો અમે અમારા છટણી યાદી માં 9 નંબર દાખલ કરવા માંગો છો, તમામ અમે શું હોય છે 9 સાથે નવા નોડ બનાવવા માટે, તે WIRE અપ કરવા માટે યોગ્ય સ્થળ નિર્દેશ, અને પછી ફરી વાયર 8 ડાઉન 9 કરવા માટે નિર્દેશ છે. કે ખૂબ ઝડપી છે, ધારી રહ્યા છીએ કે અમે બરાબર ખબર જ્યાં અમે 9 તે સામેલ કરવા માંગો છો. પરંતુ આ માટે વિનિમય વેપાર બોલ એ છે કે આપણે હવે પ્રવેશ સતત સમય ગુમાવ્યું છે અમારી માહિતી માળખામાં કોઇ ખાસ તત્વ છે. ઉદાહરણ તરીકે, જો હું આ સંલગ્ન યાદીમાં ચોથા તત્વ શોધવા માંગો છો, હું યાદીમાં ખૂબ શરૂઆતમાં શરૂ હોય જાઉં છું અને નોડ બાય નોડ ગણતરી મારફતે મારા માર્ગ કામ ત્યાં સુધી હું ચોથા એક શોધો. 

યોગ્ય રીતે એક કડી થયેલ યાદી કરતાં વપરાશ કામગીરી વિચાર - પણ લાભ કે આપણે અમુક જાળવી નિવેશ સમય એક કડી થયેલ યાદીમાંથી દ્રષ્ટિએ - દ્વિસંગી વૃક્ષ માટે થોડો વધારે મેમરીનો ઉપયોગ કરવાની જરૂર રહ્યું છે. ખાસ કરીને, તેના બદલે માત્ર દ્વિસંગી વૃક્ષ નોડ એક નિર્દેશક હોવાની - આ યાદી સાથે જોડાયેલી છે જેમ કે ગાંઠ કરે છે - અમે દ્વિસંગી વૃક્ષ નોડ બીજી નિર્દેશક ઉમેરવા જઈ રહ્યાં છો. બદલે માત્ર આગામી તત્વ માટે એક નિર્દેશક હોય, અમે ડાબી બાળક અને એક યોગ્ય બાળક માટે નિર્દેશક હોય રહ્યા છીએ. 

ચાલો એક ચિત્ર દોરવા શું છે કે જે વાસ્તવમાં જેવો દેખાય છે. ફરીથી, હું આ બોક્સ અને તીરો ઉપયોગ જાઉં છું. એક દ્વિસંગી વૃક્ષ નોડ બોલ ફક્ત સાદા બોક્સ સાથે શરૂ થશે. તે કિંમત માટે એક જગ્યા હોય ચાલી રહ્યું છે, અને પછી તેને પણ ડાબી બાળક અને જમણી બાળક માટે જગ્યા હોય બનશે. હું તેમને અહીં લેબલ જાઉં છું. અમે ડાબી બાળક હોય જઈ રહ્યાં છો, અને પછી અમે અધિકાર બાળક હોય રહ્યા છીએ. આ કરવાથી ઘણા જુદા જુદા માર્ગો છે. ક્યારેક જગ્યા અને સગવડ માટે, હું ખરેખર તે દોરે છે કે હું અહીં નીચે કરી રહ્યો છું પડશે , જ્યાં હું ટોચ પર હોય જાઉં છું અને પછી નીચે જમણા પર યોગ્ય બાળક, અને નીચે ડાબી પર ડાબી બાળક. આ ટોચ રેખાકૃતિ પાછા જવાનું, અમે ખૂબ જ ટોચ પર કિંમત હોય છે, પછી અમે નિર્દેશક ડાબા બાળક હોય છે, અને તે પછી અમે નિર્દેશક જમણી બાળક હોય છે. 

સમસ્યા સેટ સ્પષ્ટીકરણ માં, અમે નોડ કે જે 7 મૂલ્ય છે ચિત્રકામ વિશે વાત અને પછી નિર્દેશક ડાબા બાળક કે નલ છે, અને નિર્દેશક જમણી બાળક કે નલ છે. અમે ક્યાં તો જગ્યા માટે મૂડી NULL લખી શકો છો બંને ડાબી બાળક અને જમણી બાળક, અમે અથવા આ વિકર્ણ સ્લેશ ડ્રો કરી શકો છો બોક્સ દરેક મારફતે તે દર્શાવવા માટે તેને નલ છે. હું શું કે જે હમણાં જ કારણ કે સરળ છે જાઉં છું. તમે અહીં જોઈ શું ખૂબ સરળ દ્વિસંગી વૃક્ષ નોડ diagramming બે માર્ગો છે જ્યાં અમે 7 કિંમત અને નલ બાળક પોઇન્ટર છે. 

અમારી સાથે લિંક યાદીઓ સાથે કેવી રીતે સ્પષ્ટીકરણ મંત્રણા બીજા ભાગ - યાદ રાખો, અમે માત્ર પ્રથમ તત્વ માટે યાદીમાં પકડી હતી સમગ્ર યાદી યાદ - અને તેવી જ રીતે, એક દ્વિસંગી વૃક્ષ સાથે, અમે માત્ર એક નિર્દેશક પર વૃક્ષ પકડી છે ક્રમમાં સમગ્ર માહિતી બંધારણ પર નિયંત્રણ જાળવી છે. વૃક્ષ આ ખાસ તત્વ વૃક્ષના રુટ નોડ કહે છે. ઉદાહરણ તરીકે, જો આ એક નોડ - આ 7 કિંમત સમાવતી નોડ નલ ડાબી અને જમણી બાળક પોઇન્ટર સાથે - અમારા વૃક્ષ માત્ર કિંમત હતા, તો પછી આ અમારી રુટ નોડ હશે. તે અમારી વૃક્ષ ખૂબ જ શરૂઆત છે. અમે આ થોડો વધુ સ્પષ્ટ રીતે જોઈ એકવાર અમે અમારી વૃક્ષ વધુ ગાંઠો ઉમેરી રહ્યા શરૂ કરી શકો છો. દો મને એક નવું પાનું ખેંચો. 

હવે અમે એક વૃક્ષ કે જે રુટ અંતે 7 ધરાવે છે દોરવા જઈ રહ્યાં છો, અને ડાબી બાળક, અને જમણી બાળક 9 ઇનસાઇડ 3 અંદર. ફરીથી, આ ખૂબ સરળ છે. અમે 7 મળી છે, 3 માટે નોડ, 9 માટે નોડ આલેખન અને હું 7 ના નિર્દેશક ડાબા બાળક 3 સમાવતી નોડ માટે નિર્દેશ સેટ જાઉં છું, અને 9 સમાવતી નોડ માટે 7 સમાવતી નોડને નિર્દેશક જમણી બાળક. હવે, 3 થી 9 અને કોઇ પણ બાળકો ન હોય, અમે તેમના બાળક પોઇંટરો તમામ સુયોજિત કરવા માટે નલ હોઈ રહ્યા છીએ. અહીં, અમારા વૃક્ષની રુટ જે નંબર 7 સમાવતી નોડ અનુલક્ષે છે. કે જે તમને શું તમામ અમે હોય કે જે રુટ નોડ માટે નિર્દેશક છે, અમે પછી અમારી વૃક્ષ લઈ જવામાં કરી શકો છો અને બંને બાળક ગાંઠો ઍક્સેસ - 3 બન્ને અને 9. કોઈ વૃક્ષ પર દરેક એક નોડ માટે પોઇંટરો જાળવવા જરૂર છે. ઓલરાઇટ. હવે અમે આ રેખાકૃતિ બીજા ગાંઠ ઉમેરી રહ્યા છીએ. અમે 6 સમાવતી નોડ ઉમેરવા જઈ રહ્યાં છો, અને અમે 3 સમાવતી નોડ જમણી બાળક તરીકે ઉમેરી રહ્યા છીએ. કે કરવા માટે, હું 3-નોડ કે નલ નિર્દેશક ભૂંસવું જાઉં છું અને તે તાર અપ ટુ 6 સમાવતી નોડ માટે નિર્દેશ કરે છે. ઓલરાઇટ. 

આ બિંદુએ, ચાલો પરિભાષા એક થોડો પર જાઓ. શરૂ કરવા માટે, કારણ કે આ ખાસ કરીને એક દ્વિસંગી વૃક્ષ કહે છે છે કે તે બે બાળક પોઇન્ટર છે. ત્યાં વૃક્ષો કે જે વધુ બાળક પોઇન્ટર હોય અન્ય પ્રકારના હોય છે. ખાસ કરીને, તમે એક પ્રોબ્લેમ 5 સમૂહ માં 'પ્રયાસ' કર્યું. કે જે તમને પ્રયાસમાં કે નોટિસ પડશે, તમે 27 અલગ અલગ બાળકો માટે વિવિધ પોઇંટરો હતી - એક ઇંગલિશ મૂળાક્ષર માં 26 અક્ષરો દરેક માટે, અને પછી એપોસ્ટ્રોફી માટે 27 - તેથી, કે વૃક્ષ એક પ્રકાર માટે સમાન છે. પરંતુ અહીં, તે બાઈનરી થી, અમે માત્ર બે બાળક પોઇન્ટર છે. 

આ રુટ નોડ કે અમે વિશે વાત કરવા ઉપરાંત, અમે પણ આ શબ્દનો આસપાસ કર્યું છે ફેંકવાની કરવામાં 'બાળક.' તે શું માટે એક નોડ અન્ય નોડ એક બાળક હોઈ અર્થ છે? તેનો શબ્દશ: અર્થ એ થાય કે બાળક નોડ અન્ય નોડ એક બાળક છે જો કે અન્ય નોડ એક તેના બાળક માટે કે નોડ માટે નિર્દેશ સેટ પોઇંટરો ધરાવે છે. વધુ કોંક્રિટ શરતો આ મૂકવા, જો 3 થી 7 ના એક બાળક પોઇંટરો દ્વારા નિર્દેશ છે, તો પછી 3 7 એક બાળક છે. જો અમે બહાર આકૃતિ 7 ના બાળકો શું છે હતા - સાથે સાથે, અમે જુઓ કે 7 3 માટે નિર્દેશક અને 9 માટે નિર્દેશક ધરાવે છે, 9 તેથી અને 3 7 બાળકો છે. નવ કોઈ બાળકો છે કારણ કે તેના બાળક પોઇંટરો નલ છે, અને 3 માત્ર એક બાળક, 6 ધરાવે છે. છ પણ કોઈ બાળકો છે કારણ કે તેની પોઇંટરો બંને નલ, જે અમે હમણાં દોરવા પડશે છે. 

વધુમાં, અમે પણ ચોક્કસ નોડને માતા - પિતા વિશે વાત અને આ છે, કારણ કે તમે અપેક્ષા હો, તો આ બાળ વર્ણન ના રિવર્સ. બે ના બદલે તરીકે તમે માનવીઓ સાથે આશા રાખી શકે છે - દરેક નોડ માત્ર એક માવતર છે. ઉદાહરણ તરીકે, 3 પિતૃ 7 છે. 9 ના પિતૃ પણ 7, અને 6 ની પિતૃ 3 છે. તેને ખૂબ. અમે પણ દાદા દાદી અને પૌત્ર વિશે વાત શરતો હોય છે, અને વધુ સામાન્ય અમે પૂર્વજો વિશે વાત અને એક ખાસ નોડ વંશજો છે. નોડ પૂર્વજ - અથવા પૂર્વજો બદલે એક ગાંઠની - પાનાંઓ કે જે રુટ કે નોડ પાથ પર આવેલા તમામ છે. ઉદાહરણ તરીકે, જો હું નોડ 6 જોઈ રહ્યો છું, પછી પૂર્વજોને 3 બન્ને અને 7 હશે આવે છે. 9 પૂર્વજો, ઉદાહરણ તરીકે, છે - જો હું નોડ 9 જોઈ રહ્યો છું - પછી 9 ના પૂર્વજ ફક્ત 7. અને વંશજો બરાબર વિપરીત છે. જો, હું 7 વંશજો તમામ જોવા માંગો છો પછી હું તેને નીચે ગાંઠો બધી જોવા મળે છે. તેથી, હું 3, 9, અને 6 7 વંશજો તરીકે બધા હોય છે. 

અંતિમ શબ્દ કે અમે વિશે વાત કરીશું પિતરાઈ હોવાથી આ કલ્પના છે. આ કુટુંબ શરતો પર સાથે નીચેના પ્રકારની - બહેન - ગાંઠો કે વૃક્ષ એજ સ્તર પર છે. તેથી, 3 અને 9 બહેન છે કારણ કે તેઓ વૃક્ષ એજ સ્તર પર છે. તેઓ બંને એક જ પિતૃ, 7 છે. આ 6 કોઈ બહેન છે કારણ કે 9 કોઈપણ બાળકો નથી. અને 7 કોઈપણ બહેન નથી કારણ કે તે અમારી વૃક્ષની રુટ છે થતું નથી, અને ત્યાં ક્યારેય માત્ર 1 રુટ છે. માટે 7 બહેન હોય ત્યાં થી 7 ઉપર નોડ હોવો જોઈએ. ત્યાં થી 7 ની પિતૃ, 7, કે જે કિસ્સામાં લાંબા સમય સુધી વૃક્ષની રુટ હશે હોવો જોઈએ. પછી 7 ની છે કે જે નવી પિતૃ પણ એક બાળક હોય હોવી જોઈએ, અને જે બાળક પછી 7 ના ભાઈ હશે. 

ઓલરાઇટ. પર ખસેડી રહ્યા છીએ. , જ્યારે અમે દ્વિસંગી વૃક્ષો અમારી ચર્ચા શરૂ અમે કેવી રીતે અમે તેમને વાપરવા માટે જતા હતા તે અંગે વાત કરી બન્ને એરે અને સંલગ્ન યાદીઓ પર એક ફાયદો મેળવે છે. અને જે રીતે અમે તે કરવા જઈ રહ્યાં છો તો આ ક્રમમાં મિલકત સાથે છે. અમે કહે છે કે દ્વિસંગી વૃક્ષ આદેશ આપ્યો છે સ્પષ્ટીકરણ અનુસાર, જો અમારા વૃક્ષમાં દરેક નોડ માટે, ડાબી બાજુએ તેના અનુગામીઓ તમામ - ડાબી બાળક અને ડાબી બાળકની વંશજો તમામ - ઓછા મૂલ્યો, અને જમણે પર ગાંઠો બધી - જમણી બાળક અને જમણી બાળકની વંશજો તમામ - વર્તમાન નોડ મૂલ્ય કે અમે અંતે શોધી રહ્યાં છો તે કરતાં વધારે ગાંઠો હોય છે. જસ્ટ સરળતા માટે, અમે ધારે છે કે ત્યાં અમારી વૃક્ષ કોઈપણ ડુપ્લિકેટ ગાંઠો નથી જઈ રહ્યાં છો. ઉદાહરણ તરીકે, આ વૃક્ષ અમે કેસ સાથે વ્યવહાર નથી જઈ રહ્યાં છો જ્યાં અમે રુટ ખાતે 7 કિંમત હોય છે  અને પછી અમે પણ મૂલ્ય 7 વૃક્ષ અન્યત્ર હોય છે. આ કિસ્સામાં, તમે નોટિસ પડશે કે આ વૃક્ષ ખરેખર આદેશ આપ્યો છે. અમે રુટ ખાતે 7 કિંમત હોય છે. 7 ડાબી બધું - જો હું આ થોડું ગુણ બધા અહીં પૂર્વવત્ - 7 ડાબી બધું - 3 અને 6 ના - તે કિંમતો બંને છે 7 કરતા ઓછું, અને જમણી બધું - જે ફક્ત 9 આ - 7 કરતા વધારે છે. 

આ માત્ર આદેશ આપ્યો આ કિંમતો સમાવતી વૃક્ષ નથી, દો પરંતુ થોડા વધુ દોરે છે. ત્યાં ખરેખર રીતે કે અમે આ કરી શકો છો સંપૂર્ણ સમૂહ છે. હું એક લઘુલિપિ ઉપયોગ ફક્ત વસ્તુઓ જ્યાં સરળ રાખવા માટે જાઉં છું - તેના બદલે બહાર બોક્સ અને તીરો સમગ્ર ચિત્રકામ કરતાં - હું માત્ર નંબરો દોરવા અને તેમને જોડાઈ તીરો ઉમેરવા જાઉં છું. શરૂ કરવા માટે, અમે અમારા મૂળ વૃક્ષ ફરીથી લખી શકશો જ્યાં અમે 7 હતી, અને તે પછી 3 એ, અને પછી 3 6 અધિકાર પાછા જણાવ્યું, અને 7 અધિકાર બાળક જે 9 હતી. ઓલરાઇટ. બીજી રીતે કે જે આપણે આ વૃક્ષ લખી શકે શું છે? બદલે 3 કર્યા 7 ડાબી બાળક હોઈ શકે, અમે પણ 6 એ 7 ડાબી બાળક હોઈ શકે, અને પછી 3 6 ડાબી બાળક છે. કે આ વૃક્ષ જેવી અહીં જોવા જ્યાં હું 7 મળી છે કરશે, 6 પછી, પછી 3, અને એક જમણી બાજુ પર 9. અમે પણ 7 અમારી રુટ નોડ તરીકે પાસે નથી. અમે પણ અમારા રુટ નોડ તરીકે 6 હોઇ શકે છે. શું છે કે જેમ દેખાય છે? જો અમે આ આદેશ આપ્યો મિલકત જાળવવા જઈ રહ્યાં છો, આ 6 ડાબી બધું તેને કરતાં ઓછી હોવી જોઇએ. ત્યાં માત્ર એક શક્યતા છે, અને તે 3 છે. પરંતુ તે પછી 6 જમણી બાળક તરીકે, અમે બે શક્યતાઓ હોય છે. પ્રથમ, અમે 7 હોય અને પછી શકે 9 એ, અથવા તો અમે તેને ડ્રો કરી શકી - જેમ હું વિશે અહીં કરવું છું - , જ્યાં અમે 6 ના અધિકાર બાળક તરીકે 9 ના હોય અને પછી 9 નું ડાબી બાળક તરીકે 7. 

હવે, 7 અને 6 રુટ માટે માત્ર એક જ શક્ય કિંમતો નથી. અમે પણ 3 રૂટ પર હોઇ શકે છે. તો શું થાય 3 રૂટ પર છે? અહીં, વસ્તુઓ થોડો રસપ્રદ છે. ત્રણ કોઈપણ કિંમતો કે જે તે કરતાં ઓછી છે નથી, જેથી વૃક્ષ કે સમગ્ર ડાબી બાજુ માત્ર નલ પ્રયત્ન રહ્યું છે. ત્યાં કશું ત્યાં નથી જઈ રહ્યા છે. જમણી બાજુએ, અમે ચડતા ક્રમમાં વસ્તુઓ યાદી શકે છે. અમે 3, પછી 6, પછી 7, પછી 9 કરી શકે છે. અથવા, અમે 3 નહિં, તો શકે 6, પછી 9, 7 પછી. અથવા, અમે 3 નહિં, તો કરી શકે 7, પછી 6, 9, પછી. અથવા, 3, 7 - વાસ્તવમાં આ બોલ પર કોઈ, અમે 7 એક કંઈ પણ કરી શકે છે. તે અમારી એક વસ્તુ ત્યાં છે. અમે 9 કરવા માટે, અને પછી 9 થી અમે 6 કરવું અને પછી કરી શકો છો 7. અથવા, અમે 3 નહિં, તો કરી શકો છો 9, પછી 7, અને પછી 6. 

એક અહીં તમારું ધ્યાન દોરવા વસ્તુ છે કે આ વૃક્ષો થોડો વિચિત્ર દેખાતી હોય છે. ખાસ કરીને, જો આપણે જમણી બાજુ પર 4 વૃક્ષો જોવા - હું તેમને વર્તુળ, અહીં કરીશું - આ વૃક્ષો એક કડી થયેલ યાદી જેમ લગભગ બરાબર દેખાય છે. દરેક નોડને માત્ર એક બાળક છે, અને તેથી અમે આ માળખું વૃક્ષ જેવા કે અમે જુઓ કોઇ ઉદાહરણ તરીકે ન હોય તો,  આ એક તળિયે ડાબી પર અહીં પર એકલા વૃક્ષ છે. આ વૃક્ષો ખરેખર દ્વિસંગી વૃક્ષો પતિત કહેવાય છે, અને અમે આ વિશે વધુ ભવિષ્યમાં વાત કરીશું - ખાસ કરીને જો તમે પર જવા માટે અન્ય કોમ્પ્યુટર વિજ્ઞાન અભ્યાસક્રમો લે છે. આ વૃક્ષો પતિત છે. તેઓ ખૂબ ઉપયોગી છે, કારણ કે ખરેખર, આ માળખું પૂરું પાડે પોતે નથી  એક કડી થયેલ યાદી છે કે જે સમાન વખત લુકઅપ. અમે વધારે મેમરી લાભ લેવા નથી - આ વધારાના નિર્દેશક - કારણ કે અમારી માળખું આ રીતે ખરાબ છે. બદલે પર જાઓ અને બાઈનરી વૃક્ષો કે જે રુટ અંતે 9 હોય આલેખન જે અંતિમ કેસ છે કે અમે હશે છે, અમે બદલે કરશો, આ સમયે, આ અન્ય શબ્દ વિશે થોડુંક વાત જવા કે અમે વાપરો જ્યારે વૃક્ષો, કે જે ઊંચાઇ કહેવાય છે તે વિશે વાત કરી. 

એક વૃક્ષની ઊંચાઇ રુટ ના નોડ સૌથી દૂરના અંતર છે, અથવા બદલે અંતરોની નંબર કે જેની તમે બનાવવા માટે હોય છે કરવા માટે કરશે રુટ શરૂ કરો અને પછી વૃક્ષ નોડ સૌથી દૂરના અંતે અંત. જો અમે આ વૃક્ષો કેટલાક કે અમે અહીં દોરવામાં કર્યું છે અંતે, જુઓ અમે કે જો અમે ટોચે ડાબા ખૂણે આ વૃક્ષ લેવા અને અમે શરૂ 3 અહીં જોઈ શકો છો, પછી અમે 1 હોપ થી 6 માટે વિચાર, એક બીજા થી 7 માટે વિચાર હોપ બનાવવા હોય તો, અને ત્રીજા હોપ 9 તે મેળવવા માટે. તેથી, આ વૃક્ષની ઊંચાઇ 3 છે. અમે અન્ય આ લીલા સાથે દર્શાવેલ વૃક્ષો માટે તે જ કસરત કરી શકો છો, અને અમે જુઓ કે આ વૃક્ષો બધી ઊંચાઇ પણ ખરેખર છે 3. કે શું બનાવે છે તેમને ડિજનરેટ ભાગ છે - કે તેમના ઊંચાઇ માત્ર એક જ સમગ્ર વૃક્ષમાં ગાંઠો સંખ્યા કરતાં ઓછી છે. જો અમે આ અન્ય બીજી બાજુ પર લાલ સાથે ઘેરાયેલો છે વૃક્ષ, જુઓ, અમે જુઓ કે સૌથી દૂરના પર્ણ ગાંઠો 6 અને 9 ની છે - તે નોડ કે જે કોઈ બાળકો હોય છે નહીં. તેથી, ક્રમમાં રુટ નોડ માંથી ક્યાંતો 6 અથવા 9 કરવા માટે વિચાર, અમે એક હોપ બનાવવા માટે 7 માટે વિચાર છે અને પછી બીજા 9 કરવા માટે વિચાર હોપ, અને તેવી જ રીતે, માત્ર 7 થી બીજા હોપ 6 એ મેળવવા માટે. તેથી, અહીં પર આ વૃક્ષની ઊંચાઇ માત્ર 2 છે. તમે પાછા જાઓ અને અન્ય વૃક્ષો બધા માટે તે આમ કરે છે કે અમે અગાઉ ચર્ચા કરી શકો છો 7 અને 6 સાથે શરૂ કરીને, અને તમને તે વૃક્ષો બધા ની ઊંચાઇ પણ છે 2. 

કારણ કે અમે વિશે વાત કરી દ્વિસંગી વૃક્ષો આદેશ આપ્યો અને તેઓ કૂલ છો શા માટે છે કારણ કે તમે તેમના મારફતે શોધ કરી શકે છે ખૂબ સમાન એક છટણી એરે પર શોધ કરવા માટે રસ્તો. આ તે છે જ્યાં અમે સુધારેલાં લૂકઅપ સમય વિશે વાત સરળ યાદીની લિંક પર. એક કડી થયેલ યાદી સાથે - જો તમે ચોક્કસ તત્વ શોધવા માંગો છો - તમે શ્રેષ્ઠ રેખીય શોધ અમુક પ્રકારની કરવા જઇ અંતે છો તમે જ્યાં યાદી અને એક દ્વારા એક હોપ શરૂઆતમાં શરૂ - એક નોડ દ્વારા એક નોડ - સમગ્ર યાદી ત્યાં સુધી તમે શોધવા ગમે તમે શોધી રહ્યાં છો બનાવ્યા. જ્યારે, જો તમે એક દ્વિસંગી વૃક્ષ કે આ સરસ બંધારણમાં માં સંગ્રહિત હોય છે, તમે ખરેખર એક દ્વિસંગી રહ્યું શોધ વધુ મેળવી શકો છો જ્યાં તમે વિભાજિત અને જીતી અને દરેક પગલે વૃક્ષ યોગ્ય અડધા મારફતે શોધ. ચાલો કેવી રીતે કામ કરે છે જુઓ. 

જો અમે હોય - ફરી, અમારા મૂળ વૃક્ષ પર પાછા જવાનું - અમે 7 શરૂ થાય છે, અમે ડાબી પર 3 હોય છે, જમણી બાજુ પર 9, અને 3 નીચે અમે 6 હોય છે. જો અમે આ વૃક્ષ 6 નંબર શોધવા માટે કરવા માંગો છો, અમે રુટ શરૂ છો. અમે કિંમત અમે 6 કહેવું, શોધી રહ્યાં છો તે તુલના હો, આ નોડ કે અમે હાલમાં અંતે, 7 શોધી રહ્યાં છો તે સંગ્રહાયેલ કિંમત છે, લાગે છે કે 6 ખરેખર છે 7 કરતાં ઓછી છે, તેથી અમે ડાબી ખસેડવા માંગો છો. જો 6 ની કિંમત 7 કરતા વધારે હતી, અમે બદલે જમણી તરફ હશે. કારણ કે આપણે જાણીએ છીએ કે - અમારા આદેશ આપ્યો દ્વિસંગી વૃક્ષ સંરચનાને કારણે - આ 7 કરતા ઓછું કિંમતો બધી 7 ડાબી સંગ્રહિત કરવામાં જવું છે, કોઇ પણ વૃક્ષ જમણી બાજુ મારફતે શોધી સંતાપ જરૂર નથી. એકવાર અમે ડાબી ખસેડવા અને અમે 3 સમાવતી ગાંઠ પર હવે કરશો, અમે તે જ સરખામણી ફરી કરવું જ્યાં અમે 3 અને 6 એ તુલના કરી શકો છો. અને અમે શોધી છે કે જ્યારે 6 - મૂલ્ય અમે શોધી રહ્યાં છો - 3 કરતાં વધુ હોય છે, અમે 3 સમાવતી નોડ જમણી બાજુ જઈ શકો છો. ત્યાં કોઈ ડાબી બાજુ અહીં, જેથી અમે તે અવગણવામાં કરી શકે. પરંતુ અમે માત્ર ખબર છે કે કારણ કે અમે વૃક્ષ પોતે જોઈ રહ્યાં છો, અને અમે જોઈ શકો છો કે જે વૃક્ષ કોઈ બાળકો હોય છે. 

તે પણ ખૂબ સરળ કરવા માટે આ વૃક્ષ 6 જુઓ જો અમે તેને જાતને કરી રહ્યા માનવીઓ તરીકે, દો પરંતુ કમ્પ્યૂટર જેવી આ પ્રક્રિયા યાંત્રિક અનુસરી શકે કરવું ખરેખર અલ્ગોરિધમનો સમજો. આ બિંદુએ, અમે હવે એક નોડ કે જે 6 સમાવે જોઈ રહ્યાં છો, અને અમે 6 કિંમત શોધી રહ્યાં છો, તેથી, ખરેખર, અમે યોગ્ય નોડ મળ્યાં છે. અમે અમારા વૃક્ષ 6 કિંમત મળી છે અને અમે અમારા શોધ બંધ કરી શકો છો. આ બિંદુએ, શું થઈ રહ્યું છે તે પર આધાર રાખીને, અમે કહી શકો છો, હા, અમે 6 કિંમત મળી છે, તે અમારા વૃક્ષ હાજર હોય. અથવા, જો અમે નોડ સામેલ અથવા કંઈક આયોજન કરી રહ્યાં છો, તો અમે આ સમયે આ કરી શકે. 

ચાલો એક દંપતી વધુ લુકઅપો કરી ફક્ત આ કેવી રીતે કામ કરે છે તે જોવા માટે. ચાલો શું થાય જો આપણે પ્રયત્ન અને જે 10 કિંમત જોવા હતા જુઓ. જો અમે સુધી 10 કિંમત જોવા હતા, અમે રૂટ પર શરૂ કરશે. અમે તે 10 7 કરતાં વધારે હોય છે, જુઓ જેથી છો અમે અધિકાર ખસેડવા માંગો છો. અમે 9 કરવા માટે વિચાર અને 10 માટે 9 સરખાવવા છો અને જુઓ કે 9 ખરેખર છે 10 કરતા પણ ઓછા. તેથી ફરી, અમે અધિકાર ખસેડવા પ્રયાસ કરશો. પરંતુ આ સમયે, અમે નોટિસ છો કે અમે નલ ગાંઠ પર છો. ત્યાં કંઇ ત્યાં છે. ત્યાં કંઇ જ્યાં 10 એ પ્રયત્ન કરીશું છે. આ તે છે જ્યાં અમે નિષ્ફળતા જાણ કરી શકો છો - એટલે કે ત્યાં ખરેખર કોઈ વૃક્ષ માં 10. અને છેલ્લે, ચાલો કિસ્સામાં જ્યાં અમે સુધી વૃક્ષ 1 જોવા પ્રયાસ કરી રહ્યા છો પસાર થાય છે. આ શું જો અમે 10 જોવા બદલે જમણી જવાની સિવાય, આવું થાય છે માટે જ છે, અમે ડાબી પર જાઓ રહ્યા છીએ. અમે 7 તે સમયે શરૂ કરો અને જુઓ કે 1 7 કરતા ઓછું હોય છે, તેથી અમે ડાબી ખસેડો. અમે 3 માટે વિચાર અને જુઓ કે 1 3 કરતાં ઓછી હોય છે, તેથી ફરી અમે ડાબી ખસેડવા પ્રયાસ કરો. આ બિંદુએ અમે નલ નોડ હોય છે, તેથી ફરી અમે નિષ્ફળતા જાણ કરી શકો છો. 

જો તમે બાઈનરી વૃક્ષો વિશે વધુ જાણવા ઇચ્છતા હોવ તો, ત્યાં મજા થોડી સમસ્યાઓ છે કે તમે તેમની સાથે કરી શકો છો સંપૂર્ણ ઝુમખું પણ છે. હું રેખાંકન પ્રેક્ટિસ સૂચન આ એક બાય એક ડાયાગ્રામ બહાર અને વિવિધ પગલાં બધા મારફતે અનુસરી, કારણ કે આ સુપર હાથમાં આવશે માત્ર જ્યારે તમે હફમેનના એન્કોડિંગ સમસ્યા સેટ કરી રહ્યા છીએ પણ ભવિષ્યમાં અભ્યાસક્રમો પરંતુ - માત્ર શીખવાની કેવી રીતે આ માહિતી માળખાં દોરવા અને સમસ્યાઓ લાગે સાથે પેન અને કાગળ અથવા, આ કિસ્સામાં iPad, અને stylus. 

જોકે આ બિંદુએ, અમે પર ખસેડો કેટલાક કોડિંગ અભ્યાસ કરવા જઈ રહ્યાં છો અને ખરેખર આ દ્વિસંગી વૃક્ષો સાથે રમવા અને જુઓ. હું મારું કમ્પ્યુટર પર પાછા સ્વિચ જાઉં છું. CS50 ચલાવો અથવા CS50 સ્પેસીસ મદદથી બદલે કલમ, આ ભાગ માટે, હું સાધન વાપરવા માટે જાઉં છું. 

સમસ્યા સેટ સ્પષ્ટીકરણ સાથે પગલે, હું જોઈ કે હું જે ઉપકરણ ખોલવાની યોજના છું, મારા ડ્રૉપબૉક્સ ફોલ્ડર પર જાઓ, 7 વિભાગ કહેવાય ફોલ્ડર બનાવવા માટે, અને પછી binary_tree.c તરીકે ઓળખાતી ફાઈલ બનાવો. અહીં અમે જાઓ. હું સાધન પહેલાથી જ ઓપન મેળવ્યા છે. હું ટર્મિનલ ખેંચી જઇ રહ્યો છું. હું ડ્રૉપબૉક્સ ફોલ્ડર પર જાઓ જાઉં છું, એક section7 કહેવાય ડિરેક્ટરી બનાવવા માટે, જુઓ અને તે સંપૂર્ણપણે ખાલી છે. હવે હું અપ binary_tree.c ખોલવા જઈ રહ્યો છું. ઓલરાઇટ. ખાલી ફાઈલ - અહીં અમે જાઓ. 

ચાલો આ સ્પષ્ટીકરણ પર પાછા જાઓ. આ સ્પષ્ટીકરણ એક નવો પ્રકાર વ્યાખ્યા બનાવવા પૂછે છે દ્વિસંગી વૃક્ષ પૂર્ણાંક કિંમતો સમાવતી નોડ માટે - ફક્ત કિંમતો છે કે અમે અમારી પહેલાં diagramming બહાર દોર્યું જેવા હોય છે. અમે આ boilerplate typedef કે અમે અહીં કર્યું છે ઉપયોગ જઈ રહ્યાં છો કે તમે પ્રોબ્લેમ 5 સમૂહ માંથી ઓળખી જોઇએ - જો તમે આ વિજય સ્પેલર કાર્યક્રમ હેશ ટેબલ માર્ગ હતી. તમને પણ તે ગયા અઠવાડિયે વિભાગ માંથી ઓળખી જોઈએ જ્યાં અમે કડી થયેલ યાદીઓ વિશે વાત કરી. અમે સ્ટ્રક્ટ નોડ આ typedef મળી છે, અને અમે આ સ્ટ્રક્ટ નોડ સ્ટ્રક્ટ નોડ આ પહેલાંથી નામ આપી છે તેથી અમે પછી તે સંદર્ભ લો ત્યારથી અમે સ્ટ્રક્ટ નોડ પોઇંટરો માંગો છો શકો છો અમારા સ્ટ્રક્ટ ભાગ તરીકે, પણ અમે તો પછી આ ઘેરી કર્યું છે - એક typedef માં - અથવા બદલે, આ બંધ જેથી, કોડ પાછળથી, અમે માત્ર એક સ્ટ્રક્ટ નોડ બદલે નોડ તરીકે આ સ્ટ્રક્ટ ઉલ્લેખ કરી શકે છે. 

આ ખૂબ યાદી singly સાથે જોડાયેલી વ્યાખ્યા જેવી જ છે કે અમે ગયા સપ્તાહે જોયું હશે છે. આ કરવા માટે, ચાલો માત્ર બહાર boilerplate લખીને શરૂ કરો. અમે જાણીએ છીએ કે અમે પૂર્ણાંક કિંમત હોય છે, તેથી અમે પૂર્ણાંક કિંમત મૂકવા, અને પડશે પછી તેના બદલે આગામી તત્વ માટે માત્ર એક નિર્દેશક હોવાની - અમે singly સાથે જોડાયેલી યાદીઓ સાથે હતી - અમે ડાબી અને જમણી બાળક પોઇન્ટર હોય રહ્યા છીએ. કે ખૂબ સરળ પણ છે - સ્ટ્રક્ટ નોડ * ડાબી બાળક; ; અને સ્ટ્રક્ટ નોડ * અધિકાર બાળક. સરસ. કે એક સુંદર સારી શરૂઆત જેવો દેખાય છે. ચાલો આ સ્પષ્ટીકરણ પર પાછા જાઓ. 

હવે અમે એક વૃક્ષની રુટ માટે વૈશ્વિક નોડ * ચલ જાહેર કરવાની જરૂર છે. અમે આ વૈશ્વિક જેમ અમે અમારી સાથે લિંક પણ વૈશ્વિક યાદીમાં પ્રથમ નિર્દેશક બનાવવામાં કરી રહ્યા છીએ. આ જેથી હતી વિધેયો કે અમે લખી માં અમે આ રુટ ની આસપાસ પસાર રાખવા નથી - જોકે અમે જોશો કે જો તમે આ વિધેયો recursively લખવા માંગો છો, તે સારી રીતે પ્રથમ સ્થાને તેને પણ નથી વૈશ્વિક તરીકે આસપાસ પસાર થઇ શકે છે અને તેના બદલે તે સ્થાનિક રીતે પ્રારંભ તમારા મુખ્ય કાર્ય છે. પરંતુ, અમે તેને વૈશ્વિક કરવું શરૂ કરી શકશો. ફરીથી, અમે જગ્યાઓ એક દંપતી આપે છે, અને પડશે હું નોડ * રુટ જાહેર જાઉં છું. જસ્ટ ખાતરી કરો કે હું છોડી શકું આ uninitialized બનાવવા માટે, હું તેને સમાન સેટ જાઉં છું માટે null. હવે, મુખ્ય કાર્ય માં - જે અમે ખરેખર ઝડપથી અહીં લખી કરીશું - પૂર્ણાંક મુખ્ય (પૂર્ણાંક argc, const ઘરનાં પરચૂરણ કામો * argv []) - અને હું const તરીકે મારા argv એરે જાહેર શરૂ જાઉં છું એ જ છે કે હું જાણું છું તે દલીલો દલીલો કે હું કદાચ સુધારવા નથી માંગતા હોય છે. જો હું તેમને સુધારવા માંગો છો હું કદાચ તેમને નકલો બનાવવા જોઈએ. તમે કોડ માં ઘણો આ જોશો. તે દંડ ક્યાં રીત છે. તે દંડ કરવા માટે તેને રજા - એ const ભૂલી જવું જો તમે ગમશે. હું ખાસ તે મૂકવામાં માત્ર કે જેથી હું મારી જાતને યાદ  કે હું કદાચ તે દલીલો સુધારવા નથી માંગતા. 

હંમેશની જેમ, હું મુખ્ય ઓવરને અંતે આ વળતર 0 લીટી સમાવેશ જાઉં છું. અહીં, હું મારા રુટ નોડ પ્રારંભ થશે. કારણ કે તે હમણાં છે, હું એક નિર્દેશક કે null સેટ છે મળ્યો છે, તેથી તે કશું તરફ સંકેત કરે છે. ક્રમમાં વાસ્તવમાં નોડ નિર્માણ કરવાનું શરૂ કરવા માટે, હું પ્રથમ તે માટે મેમરીને ફાળવવા કરવાની જરૂર છે. હું malloc મદદથી ઢગલો પર મેમરી કરીને કે તે કરવા જાઉં છું. હું malloc પરિણામ માટે સમાન રુટ સુયોજિત જાઉં છું, અને હું sizeof ઓપરેટર વાપરવા માટે નોડ કદ ગણતરી જાઉં છું. કારણ કે હું sizeof નોડ વાપરો વિરોધ કહે છે, malloc (4 + +4 4) અથવા 12 malloc - આ કંઈક કરી - કારણ એ છે કે હું મારી કોડ તરીકે શક્ય તરીકે સુસંગત કરવા માંગો છો. હું આ સી. ફાઈલ લેવા કરવાનો પ્રયત્ન કરવા માંગો છો, તે ઉપકરણ પર કમ્પાઇલ, અને પછી તેને મારા 64-bit Mac પર કમ્પાઇલ - અથવા સંપૂર્ણપણે અલગ આર્કીટેક્ચર પર - અને હું આ બધા જ કામ કરવા માંગો છો. 

જો હું ચલો માપ વિશે ધારણા બનાવવા છું - પૂર્ણાંક અથવા નિર્દેશક કદ માપ - પછી હું પણ આર્કિટેક્ચરના પ્રકારના વિશે છું ધારણા બનાવે છે જેના પર મારો કોડ સફળતાપૂર્વક જ્યારે ચલાવો ત્યારે કમ્પાઇલ કરી શકો છો. હંમેશા sizeof વાપરો જાતે સ્ટ્રક્ટ ક્ષેત્રો એકત્ર કરવા માટે વિરોધ કર્યો હતો. અન્ય કારણ એ છે કે ત્યાં પણ ગાદી કે કમ્પાઇલરનું સ્ટ્રક્ટ માં મૂકે હોઈ શકે છે. પણ માત્ર વ્યક્તિગત ક્ષેત્રો એકત્ર કંઈક છે જે તમે સામાન્ય રીતે કરવા માંગો છો નથી, તેથી, તે લીટી કાઢી નાંખો. હવે, ખરેખર આ રુટ નોડ પ્રારંભ કરવા માટે, હું તેના વિવિધ ક્ષેત્રો દરેક માટે કિંમતો પ્લગ હોય જાઉં છું. ઉદાહરણ તરીકે, હું કિંમત જાણી હું 7 થી પ્રારંભ કરવા માંગો છો, અને હવે હું ડાબી બાળક નલ હોઈ સુયોજિત જાઉં છું અને જમણી બાળક પણ નલ છે. સરસ! અમે સ્પેકનું કે ભાગ કર્યું છે. 

પાનું 3 ના તળિયે સ્પષ્ટીકરણ નીચે મને પૂછે છે માટે વધુ ત્રણ ગાંઠો બનાવો - એક 9 સાથે 3, એક 6 સમાવે છે, અને એક સમાવતી - અને પછી તેમને WIRE જેથી તે અમારી વૃક્ષ રેખાકૃતિ જેવી જ લાગે છે કે અમે લગભગ અગાઉ વાત કરવામાં આવી હતી. ચાલો કે ખૂબ ઝડપથી અહીં કરો. તમે ખરેખર ઝડપથી જુઓ કે હું નકલી કોડ સમૂહ લખવાનું શરૂ જાઉં છું પડશે. હું એક નોડ * બનાવવા જઇ રહ્યો છું અને હું તેને ત્રણ કૉલ જાઉં છું. હું તેને malloc (sizeof (નોડ)) માટે સમાન સેટ જાઉં છું. હું ત્રણ-> કિંમત = 3 સેટ જાઉં છું. ત્રણ -> left_child = NULL; ત્રણ -> અધિકાર _child = NULL; તેમજ. કે સુંદર રુટ પ્રારંભ જેવું જ દેખાય છે, અને તે બરાબર શું છે હું કરવા માટે જો હું 6 અને 9 તેમજ પ્રારંભ શરૂ હોય જાઉં છું. હું કે ખરેખર ઝડપથી અહીં કરીશ - વાસ્તવમાં, હું થોડો કૉપિ અને પેસ્ટ કરવા જાઉં છું, ઓલરાઇટ - અને ખાતરી કરો કે હું બનાવે છે.  હવે, હું તેને મળ્યો નકલ કરી છે અને હું આગળ જાઓ અને 6 આ સમાન સેટ કરી શકો છો. તમે જોઈ શકો છો કે આ ક્ષણભર લે છે અને સુપર કાર્યક્ષમ નથી. માત્ર થોડો, અમે એક કાર્ય છે કે અમારા માટે આ શું કરશે લખી શકશો. હું 9 એક સાથે આ બદલવા માગો છો, 6 એક સાથે બદલો. 

હવે અમે અમારા ગાંઠો તમામ બનાવનાર અને આરંભ મેળવ્યા છે. અમે મળી છે અમારા રુટ 7 સમાન સુયોજિત કરો, અથવા 7 કિંમત સમાવે છે, અમારા 3 સમાવતી નોડ, અમારા 6 સમાવતી નોડ, અને અમારા નોડ 9 છે. આ બિંદુએ, બધા અમે હોય તો વાયર અપ બધું છે. કારણ હું તમામ પોઇંટરો આરંભ કરવા માટે null છે એ જ કે હું કે ખાતરી કરો હું ત્યાં કોઈપણ uninitialized પોઇંટરો અકસ્માત દ્વારા નથી. અને ત્યારથી પણ, આ બિંદુએ, હું જ વાસ્તવમાં દરેક અન્ય માટે ગાંઠો કનેક્ટ હોય - જેના કે તેઓ વાસ્તવમાં સાથે જોડાયેલ કરી રહ્યા છીએ - હું પસાર કરી ન હોય તો ખાતરી કરો કે બધા nulls યોગ્ય સ્થળોએ ત્યાં છે. 

રુટ શરૂ મને ખબર છે કે જે રુટ ડાબી બાળક 3 છે. મને ખબર છે કે જે રુટ અધિકાર બાળક 9 છે. કે પછી, માત્ર અન્ય બાળક કે હું ચિંતા છોડી ગયા છે માતાનો 3 અધિકાર બાળક છે, કે જે 6 છે. આ બિંદુએ, તો તે બધા ખૂબ સારું લાગે છે. અમે આ રેખાઓ કેટલાક કાઢી નાખવા પડશે. હવે બધું ખૂબ સારી દેખાય છે. ચાલો અમારી સ્પષ્ટીકરણ પર પાછા જાઓ અને જુઓ અમે શું કરીએ આગામી કરો. 

આ બિંદુએ, અમે લખી કહેવાય કાર્ય 'સમાવે છે' હોય છે 'bool (પૂર્ણાંક કિંમત છે) સમાવે છે' એક પ્રોટોટાઈપ. અને આ સમાવે કાર્ય માટે સાચું પાછા જવાની છે  જો વૃક્ષ અમારી વૈશ્વિક રુટ ચલ દ્વારા માટે નિર્દેશ  આ કાર્ય અને ખોટા અન્યથા પસાર કરવામાં કિંમત સમાવે છે. ચાલો આગળ વધો અને તે કામ કરે છે. આ લૂકઅપ કે અમે માત્ર થોડો પહેલા iPad પર હાથ દ્વારા ગમતો બરાબર હોવું રહ્યું છે. ચાલો થોડો ફરી ઝૂમ અને ઉપર સ્ક્રોલ કરો. અમે અમારી મુખ્ય કાર્ય ઉપર અધિકાર આ કાર્ય મૂકી રહ્યા છીએ તેથી અમે prototyping કોઇ પણ પ્રકારની કરતા નથી. તેથી, bool ધરાવે છે (પૂર્ણાંક કિંમત). ત્યાં અમે જાઓ. ત્યાં અમારા boilerplate ઘોષણા છે. જસ્ટ ખાતરી કરો કે આ કમ્પાઇલ આવશે બનાવવા માટે, હું આગળ જાઓ અને માત્ર સમાન સુયોજિત કરવા માટે ખોટા પાછા જઈ રહ્યો છું. હમણાં આ કાર્ય માત્ર કંઈપણ નથી અને હંમેશા કે જાણ કરશે કિંમત છે કે અમે શોધી રહ્યાં છો તે વૃક્ષ નથી. 

આ બિંદુએ, તે કદાચ સારો વિચાર છે - કારણ કે અમે કોડ સંપૂર્ણ સમૂહ હોય તેવા પરચૂરણ ખર્ચ કર્યો છે અને અમે તેને હજુ સુધી પરીક્ષણ ન કરવાનો પ્રયાસ કર્યો છે - ખાતરી કરવા માટે કે તે તમામ કમ્પાઇલ બનાવે છે. ત્યાં વસ્તુઓ છે કે જે અમે કરવા માટે ખાતરી કરો કે આ ખરેખર કમ્પાઇલ દેખાશે એક દંપતી છે. પ્રથમ, જુઓ જો અમે કોઈ લાઈબ્રેરીઓ કોઈપણ વિધેયો કે અમે હજુ સુધી સમાવેશ થાય છે ઉપયોગ કરી રહ્યો છું. આ વિધેયો અમે અત્યાર સુધી ઉપયોગ કર્યો છે malloc છે, અને પછી અમે પણ આ પ્રકારની કરી છે ઉપયોગ કરીને - આ nonstandard 'bool' કહેવાય પ્રકાર - જે પ્રમાણભૂત bool હેડર ફાઈલ માં સમાવવામાં આવેલ છે. અમે ચોક્કસપણે માટે bool પ્રકાર માટે પ્રમાણભૂત bool.h સમાવેશ કરવા માંગો છો, અને અમે પણ # પ્રમાણભૂત લાઈબ્રેરીઓ માટે પ્રમાણભૂત lib.h સમાવેશ કરવા માંગો છો કે malloc અને મુક્ત છે, અને તે બધી સમાવેશ થાય છે. તેથી, બહાર ઝૂમ, અમે બહાર નીકળવા જઈ રહ્યાં છો. ચાલો પ્રયાસ કરો અને ખાતરી કરો કે આ ખરેખર કમ્પાઇલ કર્યું બનાવે છે. અમે જુઓ કે તે કરે છે, તેથી અમે અધિકાર ટ્રેક પર છો. 

ચાલો અપ binary_tree.c ફરીથી ખોલો. તે કમ્પાઇલ. ચાલો નીચે જાઓ અને ખાતરી કરો કે અમે અમારા સમાવે કાર્ય કેટલાક કોલ્સ દાખલ કરો - ફક્ત ખાતરી કરો કે જે બધા સારી અને સારી બનાવવા માટે. ઉદાહરણ તરીકે, જ્યારે અમે અમારા વૃક્ષ કેટલાક લુકઅપો અગાઉ કર્યું અમે જે 6 મૂલ્યો, 10, અને 1 જોવા પ્રયાસ કર્યો છે, અને અમે જાણતા હતા કે 6 વૃક્ષ હતો, 10 વૃક્ષ માં ન હતી, અને 1 એ વૃક્ષ ક્યાં ન હતી. ચાલો એક માર્ગ તરીકે તે નમૂના કોલ્સનો ઉપયોગ માટે આકૃતિ કે શું નથી અથવા અમારા સમાવે કાર્ય કાર્યરત છે. ક્રમમાં છે કે જે કરવું, હું printf વિધેય વાપરી જાઉં છું, અને અમે બહાર કરવા માટે સમાવે છે કોલ પરિણામ છાપી રહ્યા છીએ. સમાવે હું શબ્દમાળા મૂકવા જાઉં છું "(% d) = કારણ કે  અમે કિંમત સાથે પ્લગ ઇન જઈ રહ્યાં છો કે અમે જોવા માટે જઈ રહ્યાં છો, અને =% s ને \ n "અને તે ઉપયોગ અમારા ફોર્મેટ સ્ટ્રિંગ તરીકે. શાબ્દિક સ્ક્રીન પર છાપે - અમે હમણાં જ જોવા માટે જઈ રહ્યાં છો - શું વિધેય કોલ જેવી દેખાય છે. આ વાસ્તવમાં એ વિધેય કોલ નથી.  આ માત્ર એક ફંક્શન કોલ જેમ દેખાય છે માટે રચાયેલ શબ્દમાળા છે. 

હવે, અમે કિંમતો પ્લગ રહ્યા છીએ. અમે 6 પર સમાવે પ્રયાસ જઈ રહ્યાં છો, અને પછી શું અમે અહીં જઈ રહ્યાં છો કે ત્રણ ભાગનું બનેલું ઓપરેટર ઉપયોગ છે. ચાલો જોવા - 6 સમાવે છે - તેથી, હવે હું 6 સમાયેલ કરી છે અને જો 6 સમાવે સાચું છે, શબ્દમાળા કે અમે% s ફોર્મેટ અક્ષર મોકલી રહ્યા છીએ છે શબ્દમાળા "સાચા" હશે. ચાલો થોડો ઉપર સ્ક્રોલ. અન્યથા, અમે શબ્દમાળા "ખોટા" મોકલો જો 6 ખોટા વળતર સમાવે કરવા માંગો છો. આ થોડો મૂર્ખ દેખાવ હોય છે, પરંતુ હું આકૃતિ હું તેમજ સમજાવે શકે છે આ ત્રણ ભાગનું બનેલું ઓપરેટર શું છે કારણ અમે તેને ક્ષણભર માટે જોઇ ન હોય જેવો દેખાય છે. આ એક સરસ, સરળ બહાર આકૃતિ જો અમારી સમાવે કાર્ય કામ કરે છે રસ્તો છે. હું ડાબી પર પાછા સ્ક્રોલ જાઉં છું, અને હું નકલ અને આ રેખા પેસ્ટ થોડી વાર જાઉં છું. તે આ કિંમતો કેટલાક આસપાસ બદલી, તેથી આ માટે 1 પ્રયત્ન રહ્યું છે, અને આ માટે 10 પ્રયત્ન રહ્યું છે. 

આ બિંદુએ અમે સરસ સમાવે કાર્ય મેળવ્યા છે. અમે કેટલાક પરીક્ષણો મળી છે, અને અમે જો આ તમામ કામો જોશો. આ બિંદુએ અમે કેટલાક વધુ કોડ તેવા પરચૂરણ ખર્ચ કર્યો છે. બહાર છોડી દીધી હતી અને ખાતરી કરો કે બધું હજુ કમ્પાઇલ કરવા માટે સમય. બહાર છોડો, અને હવે આપણે દ્વિસંગી વૃક્ષ ફરીથી બનાવવા પ્રયાસ કરો. વેલ, લાગે છે કે અમે ભૂલ મળી છે, અને અમે આ મળ્યો કર્યું છે સ્પષ્ટપણે પુસ્તકાલય કાર્ય printf જાહેર કર્યુ. એવું લાગે છે કે અમે જઈ અને # standardio.h સમાવેશ કરવાની જરૂર છે. અને તે સાથે, બધું કમ્પાઇલ કરીશું. અમે તમામ છો સારું. હવે આપણે દ્વિસંગી વૃક્ષ ચલાવવાનો પ્રયત્ન અને જુઓ શું થાય છે. અહીં અમે હોય છે, /. Binary_tree, અને અમે જુઓ કે, અમે અપેક્ષિત - કારણ કે અમે હજુ સુધી અમલી નથી કરી સમાવે છે, અથવા બદલે, અમે માત્ર ખોટા વળતર મૂક્યો છે - અમે જુઓ કે તે ફક્ત તેને બધા માટે છે ખોટા પરત, જેથી તમામ મોટા ભાગ માટે છે એકદમ સારી રીતે કામ કરે છે. 

ચાલો પાછા જાઓ અને ખરેખર અમલ આ બિંદુએ સમાવે છે. હું સરકાવો માં ઝૂમ માંગવાનો, અને - યાદ રાખો, અલગોરિધમ કે અમે કરવામાં આવ્યો હતો કે અમે રુટ નોડ શરૂ અને પછી દરેક નોડ કે અમે અનુભવી અંતે, અમે સરખામણી કરવા માટે, અને તે કમ્પેરિઝન આધારિત અમે ક્યાં ડાબી બાળકને અથવા જમણી બાળક માટે ખસેડો. આ ખૂબ જ બાઈનરી શોધ કોડ કે અમે આ શબ્દ પહેલાં લખ્યું જેવુ સરખુ રહ્યું છે. જ્યારે અમે આ બોલ પર શરૂ કરવા માટે, આપણે જાણીએ છીએ કે અમે વર્તમાન નોડ ને પકડી માંગો છો કે અમે જોઈ રહ્યાં છો, અને વર્તમાન નોડ માટે રુટ નોડ માટે આરંભ કરી રહ્યું છે. અને હવે, અમે વૃક્ષ પસાર થઇ રાખવા જઈ રહ્યાં છો, અને તે અમારા બંધ શરત યાદ -  જ્યારે અમે ખરેખર હાથ દ્વારા ઉદાહરણ મારફતે કામ કર્યું - હતો જ્યારે અમે નલ નોડ આવી, , નહિં કે જ્યારે અમે નલ બાળક પર જોવામાં પરંતુ જ્યારે અમે ખરેખર વૃક્ષ નોડ ખસેડવામાં મળી અને કે અમે નલ ગાંઠ પર છો. અમે ભારપૂર્વક કહેવું જઈ રહ્યાં છો ત્યાં સુધી વર્તમાન માટે null સમાન નથી. અને અમે શું કરી શકે છે? અમે ચકાસણી માટે જઈ રહ્યાં છો જો - (વર્તમાન કિંમત> == કિંમત) પછી આપણે જાણીએ છીએ કે આપણે ખરેખર નોડ કે અમે શોધી રહ્યાં છો મળ્યાં છે. અહીં, અમે સાચું પાછા આવી શકો છો. અન્યથા, અમે જોવા માટે કે શું નથી અથવા કિંમત કિંમત કરતા ઓછો છે કરવા માંગો છો. જો વર્તમાન નોડ કિંમત કિંમત કરતાં ઓછી હોય તો અમે શોધી રહ્યાં છો, અમે અધિકાર ખસેડવા જઈ રહ્યાં છો. તેથી, વર્તમાન = વર્તમાન - right_child>; અને અન્યથા, અમે ડાબી ખસેડવા જઈ રહ્યાં છો. વર્તમાન = વર્તમાન - left_child>;. સુંદર સરળ. 

તમે કદાચ લૂપ કે ખૂબ જ આ જેવું જ દેખાય છે ઓળખી દ્વિસંગી શબ્દનો પહેલાં શોધ, પછી સિવાય અમે નીચા બોલ, અને ઊંચા સાથે વ્યવહાર કરવામાં આવી હતી. અહીં, અમે હમણાં જ એક વર્તમાન કિંમત જોવા હોય તો, તેથી તે સરસ અને સરળ છે. ચાલો ખાતરી કરો કે આ કોડ કામ કરે છે તેની ખાતરી કરો. પ્રથમ, ખાતરી કરો કે તે કમ્પાઇલ બનાવે છે. તેને એવું લાગે છે. ચાલો તે ચાલી રહ્યું પ્રયાસ કરો. અને ખરેખર, તે બહાર બધું છે કે આપણે અપેક્ષિત છાપે છે. તે વૃક્ષ 6 શોધે, 10 શોધી કારણ કે 10 વૃક્ષ માં નથી થતું નથી, અને 1 ક્યાં શોધી નથી કારણ કે 1 પણ વૃક્ષ નથી. કૂલ સામગ્રી. 

ઓલરાઇટ. ચાલો અમારી સ્પષ્ટીકરણ પાછળ જવા માટે અને શું આગામી છે. હવે, તે અમારી વૃક્ષ કેટલાક વધુ ગાંઠો ઉમેરવા માંગે છે. તે 5, 2, અને 8 ઉમેરવા, અને ખાતરી કરો કે આપણી કોડ ધરાવે બનાવવા માંગે છે હજુ પણ કામ કરે છે, જેમ ઈચ્છિત. ચાલો જવા કે નથી. આ બિંદુએ, કે બદલે નકામી કૉપિ અને પેસ્ટ કરી ફરીથી કરતાં, ચાલો એક ખરેખર નોડ બનાવવા કાર્ય લખો. જો અમે સરકાવો મુખ્ય બધી રીતે, અમે જુઓ કે અમે આ કરવામાં કરવાનું કર્યું છે ઉપર અને ફરીથી પર દરેક સમય કે અમે નોડ બનાવવા માંગો છો ખૂબ સમાન કોડ. 

ચાલો એક કાર્ય છે કે જે વાસ્તવમાં આપણા માટે નોડ નિર્માણ કરશે અને તેને પરત લખો. હું કહી તે build_node જાઉં છું. હું એક ખાસ મૂલ્ય સાથે નોડ બિલ્ડ જાઉં છું. અહીં ઝૂમ ઘટાડો. પ્રથમ વાત હું કરવા જાઉં છું વાસ્તવમાં ઢગલો પર નોડ માટે જગ્યા બનાવી છે. તેથી, નોડ * n એ = malloc ((નોડ) sizeof); n -> = મૂલ્ય કિંમત; અહીં છે અને પછી, હું ફક્ત બધા ક્ષેત્રોમાં પ્રારંભ માટે યોગ્ય કિંમતો પ્રયત્ન જાઉં છું. અને ખૂબ જ ઓવરને અંતે, અમે અમારી નોડ પરત મળશે. ઓલરાઇટ. નોંધ કરવાની એક વસ્તુ આ કાર્ય કે અહીં છે છે કે મેમરી હીપ-ફાળવવામાં આવ્યો છે એક નિર્દેશક પાછા જવાનું. આ વિશે સરસ શું છે કે જે આ નોડ હવે - અમે તે ઢગલો પર જાહેર કારણ કે જો અમે તેને સ્ટેક પર જાહેર હોય છે અમે તેને આ જેવી આ કાર્ય કરતા શકશે નહીં. કે મેમરી બહાર અવકાશ ઓફ જશે અને તે અમાન્ય હોઈ જો આપણે તેને પાછળથી ઍક્સેસ કરી દેતી હતી. કારણ કે આપણે ઢગલો-ફાળવેલ મેમરીની જાહેર કરવામાં આવે છે, અમે પછીથી તેને મુક્ત કરીને કાળજી લેવા હોય જવું છે અમારા કાર્યક્રમ માટે કોઈ મેમરી લીક ન કરવા. અમે બાકીનું બધું માટે કર્યું છે કે પર કોડ માં punting ફક્ત સમયે સરળતા ખાતર, પરંતુ જો તમે ક્યારેય કાર્ય કે આ જેવી લાગે લખી જ્યાં તમે મળ્યો છે - કેટલાક તેને malloc અથવા અંદર realloc કૉલ - તમે ખાતરી કરો કે તમે ટિપ્પણી અમુક પ્રકારની મૂકી અહીં કહે બનાવવા માંગો છો, હેય તમને ખબર છે, એક ઢગલો ફાળવવામાં મૂલ્ય પસાર થતા-સાથે આરંભ નોડ આપે છે. અને પછી તમે ખાતરી કરો કે તમે નોંધ કરો કે કહે અમુક પ્રકારની મૂકવા બનાવવા માંગો છો આ કોલર એ પાછો મેમરી મુક્ત કરવું જ જોઈએ. આ રીતે, જો કોઈકને ક્યારેય જાય અને તે કાર્ય વાપરે છે, તેઓ જાણે છે કે ગમે તે વિધેય માંથી પાછી મેળવવા અમુક બિંદુએ પર મુક્ત થવાની જરૂર રહેશે. 

એમ ધારી રહ્યા છીએ કે જે બધી સારી છે અને સારી અહીં છે, અમે નીચે અમારી કોડ જાય અને આ રેખાઓ બધા અહીં બદલી શકો છો અમારા બિલ્ડ નોડ કાર્ય પર કૉલ સાથે. ચાલો કે ખરેખર ઝડપથી કામ કરે છે. આ એક ભાગ છે કે અમે બદલો નથી જઈ રહ્યાં છો અને આ ભાગ નીચે અહીં છે નીચે જ્યાં અમે ખરેખર આ ગાંઠો WIRE માટે દરેક અન્ય બિંદુએ, કારણ કે અમે અમારા કાર્ય ન કરી શકે છે. પરંતુ, ચાલો રુટ કરવું = (7) build_node; નોડ ત્રણ * = build_node (3); નોડ છ * = (6) build_node; નોડ નવ * = build_node (9);. અને હવે, અમે પણ માટે ગાંઠો ઉમેરવા માગે છે - નોડ પાંચ * = (5) build_node; નોડ આઠ * = build_node (8); અને અન્ય નોડ શું હતું? માતાનો અહીં જોવા દો. અમે પણ એ 2 ઉમેરવા માગે છે - નોડ બે * = (2) build_node;. ઓલરાઇટ. આ બિંદુએ, અમે જાણીએ છીએ કે અમે 7 એ, 3 જે 9,, અને 6 એ મળી છે બધા યોગ્ય વાયર્ડ, પરંતુ 5 એ, 8, અને 2 એ શું? યોગ્ય ક્રમમાં બધું રાખવા માટે, આપણે જાણીએ છીએ કે ત્રણ અધિકાર બાળક 6 છે. તેથી, જો અમે 5 ઉમેરો જઈ રહ્યાં છો, આ 5 પણ વૃક્ષ જમણી બાજુ જે 3 રુટ છે અનુલક્ષે, 5 તેથી 6 ડાબી બાળક તરીકે અનુસરે છે. અમે જણાવ્યું હતું કે, છ દ્વારા આ કરી શકો છો -> left_child પાંચ =; અને પછી 8 ના 9 ડાબી બાળક તરીકે અનુસરે છે, તેથી નવ - આઠ> left_child =; અને પછી 2 3 ડાબી બાળક છે, તેથી અમે તે અહીં કરી શકો છો - તને - બે> left_child =;. જો તમે તદ્દન કે સાથે અનુસરણ કર્યું ન હતું, હું સૂચવે છે કે તમે તેને દોરવા જાતને બહાર. 

ઓલરાઇટ. ચાલો આ સંગ્રહો. ચાલો બહાર જાઓ અને ખાતરી કરો કે તે કમ્પાઇલ કરવા માટે, અને પછી અમે અમારી સમાવે કોલમાં ઉમેરી શકો છો. એવુ લાગે છે કે બધું હજુ કમ્પાઇલ. ચાલો જવા અને કેટલાક કોલ્સ સમાવે ઉમેરો. ફરીથી, હું કૉપિ અને પેસ્ટ કરવામાં થોડો કરવા જાઉં છું. હવે ચાલો 5, 8, છે અને 2 માટે શોધ કરો. ઓલરાઇટ. ચાલો ખાતરી કરો કે આ બધા સારા હજુ પણ લાગે છે તેની ખાતરી કરો. સરસ! સાચવો અને છોડી દીધું. હવે આપણે કરવા માટે, સંકલન, અને હવે આપણે ચલાવો. આ પરિણામો પરથી, તેને લાગે છે કે દરેક વસ્તુ સરસ અને સારી રીતે કામ કરી રહી છે. સરસ! તેથી હવે અમે મળી છે અમારા સમાવે છે તેવા પરચૂરણ ખર્ચ કાર્ય કરે છે. ચાલો પર ખસેડો અને કેવી રીતે વૃક્ષ પર ગાંઠો દાખલ કરવા માટે પર કામ શરૂ કારણ કે, આપણે તે કરી રહ્યા હમણાં, વસ્તુઓ ખૂબ જ સુંદર નથી. 

જો અમે સ્પષ્ટીકરણ પર પાછા જાઓ, અમને પૂછે માટે દાખલ કહેવાય કાર્ય લખી - ફરી એક bool પરત કે નથી આપણે ખરેખર વૃક્ષ માં નોડ દાખલ કરી શકે છે - અને પછી એ વૃક્ષ દાખલ કિંમત તરીકે સ્પષ્ટ થયેલ છે અમારા insert કામ કરવા માટે માત્ર દલીલ. અમે સાચા પાછા જો આપણે ખરેખર વૃક્ષ માં નોડ સમાવતી કિંમત દાખલ કરો શકે છે, જેનો અર્થ છે કે અમે એક, પૂરતી મેમરી હતી, અને બાદમાં બે, કે જે નોડ પહેલાથી જ કારણ કે વૃક્ષ અસ્તિત્વમાં ન - યાદ રાખો, અમે વૃક્ષ નકલી કિંમતો નથી જવાનું છે, ફક્ત વસ્તુઓ સરળ બનાવવા માટે. ઓલરાઇટ. કોડ પાછળ. તેને ખોલવા માટે છે. થોડી માં મોટું, પછી સરકાવો. ચાલો એવા સમાવે ઉપર જમણી insert કાર્ય મૂકો. ફરી, તે bool insert કહેવાય (પૂર્ણાંક કિંમત) બનશે. તે થોડું વધુ જગ્યા આપે છે, અને પછી મૂળભૂત તરીકે, ચાલો બહુ ઓવરને અંતે ખોટા બદલામાં મૂકી. હવે તળિયે નીચે, ચાલો આગળ છે અને તેની જગ્યાએ જાતે ગાંઠો બનાવવાની જાઓ મુખ્ય માં જાતને અને તેમને વાયરિંગ સુધી દરેક અન્ય નિર્દેશિત કરવા માટે જેમ અમે કરી રહ્યા છીએ, અમે અમારા insert કાર્ય પર આધાર રાખે છે કે જે કરવું પડશે. અમે અમારા insert કાર્ય પર આધાર રાખતા નથી શરૂઆતથી સમગ્ર વૃક્ષ હજુ સુધી નિર્માણ કરશે પરંતુ અમે આ રેખાઓ છૂટકારો મળશે - we'll આ રેખાઓ આઉટ ટિપ્પણી - કે 5 ગાંઠો, 8, છે અને 2 બિલ્ડ. અને તેના બદલે, અમે કૉલ અમારા insert કાર્ય શામેલ કરવા પડશે ખાતરી કરવા માટે કે જે વાસ્તવમાં કામ કરે છે. અહીં અમે જાઓ. 

હવે અમે આ રેખાઓ ટિપ્પણી કરી છે. અમે ફક્ત આ બિંદુ પર અમારી વૃક્ષ 7, 3, 9, અને 6 હોય છે. ખાતરી કરવા માટે કે જે આ બધા કામ કરે છે બનાવવા માટે, અમે ઝૂમ, અમારા દ્વિસંગી વૃક્ષ કરી શકો છો, તેને ચલાવવા માટે, અને અમે તે સમાવે જોવા હવે અમને જણાવ્યાં કે અમે તદ્દન યોગ્ય છો કરી શકો છો - 5, 8, છે અને 2 એ વૃક્ષ લાંબા સમય સુધી હોય છે. આ કોડમાં પાછા જાઓ, અને અમે કેવી રીતે શામેલ કરવા જવું છે? યાદ રાખો, આપણે શું કર્યું જ્યારે અમે ખરેખર 5 દાખલ કરવામાં આવી હતી, 8, છે અને 2 અગાઉ. અમે તે Plinko રમત રમી જ્યાં અમે રુટ શરૂ, નીચે એક પછી એક કરીને વૃક્ષ એક થયું ત્યાં સુધી અમે યોગ્ય તફાવત જોવા મળે છે, અને પછી અમે યોગ્ય સ્થળ પર નોડમાં વાયર્ડ. અમે એ જ વસ્તુ કરવા જઇ રહ્યા છો. આ કોડ કે અમે ઉપયોગ લેખિત જેવી મૂળભૂત રીતે કાર્ય સમાવે છે માટે હાજર જ્યાં નોડ પ્રયત્ન કરીશું શોધવા માટે, અને પછી અમે માત્ર નોડ અધિકાર ત્યાં સામેલ રહ્યા છીએ. ચાલો જે શરૂ કરો. 

તેથી અમે નોડ * વર્તમાન રુટ = હોય; અમે હમણાં જ અનુસરી કોડ સમાવે જઈ રહ્યાં છો ત્યાં સુધી અમે શોધી છે કે તે તદ્દન અમારા માટે કામ કરતું નથી. અમે વૃક્ષ પસાર જઈ રહ્યાં છો, જ્યારે વર્તમાન તત્વ નલ નથી, અને જો આપણે શોધવા કે વર્તમાન કિંમત મૂલ્ય કે અમે દાખલ પ્રયાસ કરી રહ્યા છો સમાન છે - સાથે સાથે, આ કેસમાં છીએ, જેમાં આપણે ખરેખર નોડ શામેલ કરી શકે છે આ વૃક્ષ પર છે કારણ કે આ અર્થ એ કે અમે નકલી કિંમત હોય છે. અહીં અમે ખરેખર ખોટા પાછા જઈ રહ્યાં છો. હવે, તે વર્તમાન કિંમત કિંમત કરતાં ઓછા જો બીજું છે, હવે આપણે જાણીએ છીએ કે આપણે જમણી ખસેડવા  કારણ કે કિંમત વર્તમાન વૃક્ષ જમણી અર્ધ અનુસરે છે. અન્યથા, અમે ડાબી ખસેડવા જઈ રહ્યાં છો. જે સામાન્ય છે અમારા સમાવે અધિકાર ત્યાં કામ કરે છે. 

આ બિંદુએ, એક વખત અમે આ વખતે લૂપ પૂર્ણ કરી લીધી છે, અમારા વર્તમાન નિર્દેશક માટે null પોઇન્ટ કરી રહ્યું છે જો કાર્ય પહેલેથી જ પાછા ફર્યા નથી. તેથી અમે સ્પોટ પર કરી રહ્યાં છો વર્તમાન કર્યા જ્યાં અમે નવા નોડ સામેલ કરવા માંગો છો. પૂર્ણ કરવા માટે રહે છે શું ખરેખર નવી નોડ બિલ્ડ છે, જે અમે ખૂબ સરળતાથી કરી શકે છે. અમે અમારા સુપર હાથમાં બિલ્ડ નોડ વિધેય વાપરી શકે છે, કંઈક અને કે અમે પહેલાં ન કર્યું - અમે ફક્ત પ્રકારની માની લીધો છે, પરંતુ હવે અમે ફક્ત ખાતરી કરો કરવા પડશે - અમે ખાતરી કરો કે નવું નોડ દ્વારા પરત કિંમત ખરેખર હતો બનાવવા ચકાસવા પડશે નથી નલ, અમે તે મેમરી એક્સેસ જો તે નલ છે શરૂ કરવા નથી માંગતા કારણ કે. અમે ખાતરી કરો કે નવા નોડ નલ માટે સમાન નથી પરીક્ષણ કરી શકે છે. અથવા તેના બદલે, અમે હમણાં જ જો તે ખરેખર નલ છે જોઈ શકે છે, અને જો તે નલ છે, તો પછી અમે માત્ર ખોટા શરૂઆતમાં પાછા આવી શકો છો. 

આ બિંદુએ, અમે તેના વૃક્ષ યોગ્ય બિંદુમાં નવી નોડ WIRE છે. જો અમે મુખ્ય અંતે પાછળ જુઓ અને જ્યાં અમે ખરેખર હતા તે પહેલાં કિંમતો વાયરિંગ, અમે જુઓ કે માર્ગ અમે તેને કરી રહ્યા હતા ત્યારે અમે વૃક્ષ 3 મૂકવા માગે છે હતી અમે રુટ ડાબી બાળક વાપરી શકાય છે. જ્યારે આપણે વૃક્ષ 9 મૂકી, અમે રુટ જમણી બાળક ઍક્સેસ હતી. અમે પિતૃ માટે નિર્દેશક હોય છે કરવા માટે વૃક્ષ એક નવી કિંમત મૂકી હતી. પાછા સરકાવવાથી સુધી દાખલ કરો, કે જે તદ્દન કામ અહીં ચાલી રહ્યું છે કારણ કે અમે એક પિતૃ નિર્દેશક નથી. અમે કરવા માટે કરવાનો પ્રયત્ન કરવા માંગો છો શું આ બિંદુએ છે, આ પિતૃ કિંમત તપાસો અને જુઓ - સારી gosh, જો આ પિતૃ કિંમત વર્તમાન કિંમત કરતાં ઓછી છે, પછી પિતૃ અધિકાર બાળક નવા નોડ હોવો જોઈએ; અન્યથા, આ પિતૃ ડાબી બાળક નવા નોડ પ્રયત્ન કરીશું. પરંતુ, આપણે આ પિતૃ નિર્દેશક તદ્દન હજુ સુધી નથી. 

ક્રમમાં તે વિચાર, અમે ખરેખર તેને ટ્રેક પાસે જઈ રહ્યાં છો કારણ કે અમે વૃક્ષ મારફતે જાઓ અને અમારા ઉપર લૂપ યોગ્ય સ્થળ શોધવા. અમે સ્ક્રોલિંગને દ્વારા કે અમારા insert કાર્ય ટોચ પર પાછા અપ કરી શકો છો અને અન્ય નિર્દેશક ચલ ટ્રેકિંગ પિતૃ કહેવામાં આવે છે. અમે તેને સમાન સેટ જઈ રહ્યાં છો પ્રારંભમાં null, અને પછી દરેક વખતે આપણે વૃક્ષ મારફતે જાઓ, અમે પિતૃ નિર્દેશક સેટ કરવા માટે વર્તમાન નિર્દેશક સાથે મેળ રહ્યા છીએ. વર્તમાન સમાન પિતૃ સુયોજિત કરો. આ રીતે, દરેક સમય અમે મારફતે જાઓ, અમે ખાતરી કરવા માટે કે જે વર્તમાન નિર્દેશક નોંધાયો નહીં વધે જઈ રહ્યાં છો પિતૃ નિર્દેશક તે અનુસરે છે - માત્ર એક સ્તર વૃક્ષ વર્તમાન નિર્દેશક કરતાં વધારે છે. કે બધા ખૂબ સારું લાગે છે. 

મને લાગે છે કે આ એક વસ્તુ કે અમે સંતુલિત કરવા માગશો છે અને આ નોડ પરત નલ બિલ્ડ. ક્રમમાં નોડ બનાવવા માટે ખરેખર સફળતાપૂર્વક નલ પરત મેળવવા માટે, અમે તે કોડ સુધારવા પડશે, અહીં કારણ કે, અમે પરીક્ષણ ક્યારેય ખાતરી કરો કે malloc માન્ય નિર્દેશક પરત કરો. તેથી, જો (= n NULL!), તો પછી - જો malloc માન્ય નિર્દેશક ફર્યા, પછી અમે તેને પ્રારંભ પડશે; અન્યથા, અમે હમણાં જ પાછા આવો અને જે અંત અમારા માટે નલ પરત રહેશે. હવે ખૂબ સારું લાગે છે. ચાલો ખાતરી કરો કે આ ખરેખર કમ્પાઇલ બનાવે છે. દ્વિસંગી વૃક્ષ બનાવે છે, અને ઓહ, અમે કેટલીક અહીં જઈને સામગ્રી મળી છે. 

અમે મળી છે કાર્ય એક ગર્ભિત ઘોષણા નોડ બિલ્ડ. ફરીથી, આ કમ્પાઇલરોનો સાથે, અમે ટોચ પર શરૂ રહ્યા છીએ. તેનો અર્થ જ જોઈએ શું છે કે હું નોડ બિલ્ડ કૉલ છું તે પહેલાં હું ખરેખર તે જાહેર કર્યું છે. ચાલો કોડ પાછા ખરેખર ઝડપથી જાઓ. સરકાવો અને ખાતરી કરો કે પર્યાપ્ત, મારા insert કાર્ય જાહેર કરવામાં આવે છે બિલ્ડ નોડ કાર્ય ઉપર, પણ મને insert ની અંદર નોડ બિલ્ડ ઉપયોગ કરવાનો પ્રયાસ કરી રહ્યો છું. હું નકલ અને જવા જાઉં છું - અને પછી ટોચ પર બિલ્ડ નોડ કાર્ય માર્ગ અહીં પેસ્ટ કરો. આ રીતે, આસ્થાપૂર્વક કે કામ કરશે. ચાલો આપી આ જાઓ અન્ય. હવે તે તમામ કમ્પાઇલ. બધા સારા છે. 

પરંતુ આ સમયે, અમે ખરેખર અમારા insert કાર્ય ન કહેવાય છે. અમે હમણાં જ ખબર છે કે તે કમ્પાઇલ, તેથી આપણે જવા અને કેટલાક કોલ્સ મૂકી સાઇન ચાલો અમારી મુખ્ય કાર્ય છે કે નથી. અહીં, અમે 5, 8, છે અને 2 ટિપ્પણી કરી હતી, અને પછી અમે તેમને WIRE અપ નહોતી નીચે અહીં. ચાલો કેટલાક કોલ્સ દાખલ કરવા માટે બનાવવા માટે, દો અને પણ સામગ્રી સમાન પ્રકારની છે કે અમે ઉપયોગ ઉપયોગ જ્યારે અમે આ printf કોલ્સ કરવામાં ખાતરી કરવા માટે કે બધું જ યોગ્ય રીતે મળે શામેલ ન હતી બનાવે છે. હું નકલ કરો અને પેસ્ટ કરો જાઉં છું, અને બદલે સમાવે અમે insert કરવા જઇ રહ્યા છો. અને 6, 10, અને 1 બદલે, અમે 5, 8, છે અને 2 ઉપયોગ જઈ રહ્યાં છો. આ આસ્થાપૂર્વક વૃક્ષ માં 5, 8, છે અને 2 સામેલ કરીશું. કમ્પાઇલ. બધા સારા છે. હવે અમે ખરેખર અમારા કાર્યક્રમ ચલાવવા પડશે. 

બધું ખોટું ફર્યા. તેથી, 5, 8, છે અને 2 જતું નથી અને તેને લાગે છે કે સમાવે છે તેમને ક્યાં મળ્યાં નથી. શું થઈ રહ્યું છે તે? ચાલો બહાર ઝૂમ. પ્રથમ સમસ્યા એ હતી કે insert ખોટા પાછા લાગતું હતું, અને તે છે કારણ કે અમે અમારા વળતર ખોટા કોલ બાકી, જેમ દેખાય છે અને અમે સાચા ખરેખર ક્યારેય પાછા ફર્યા. અમે તે સેટ કરી શકો છો. બીજા સમસ્યા છે, હવે તો પણ અમે - આ સંગ્રહો, આ છોડી દીધું, સ્કોર ફરીથી બનાવવા માટે, તે છે, પછી કમ્પાઇલ તેને ચલાવવા માટે - અમે જુઓ કે કંઈક બીજું અહીં થયું છે. 5 ધ, 8, છે અને 2 હજુ પણ વૃક્ષ મળી ક્યારેય આવી હતી. તેથી, શું થઈ રહ્યું છે? 

ચાલો કોડ આ પર એક નજર. ચાલો જોવા જો અમે આ બહાર આકૃતિ કરી શકો છો. અમે પિતૃ હોવા નલ સાથે શરૂ કરો. અમે વર્તમાન રુટ નિર્દેશક સમાન નિર્દેશક સુયોજિત કરો, અને અમે વૃક્ષ દ્વારા અમારી રીતે નીચે કામ રહ્યા છીએ. જો વર્તમાન નોડ નલ નથી, તો પછી આપણે જાણીએ છીએ કે અમે નીચે થોડો ખસેડી શકો છો. અમે અમારા પિતૃ નિર્દેશક સેટ કરવા માટે વર્તમાન નિર્દેશક માટે સમાન હોય છે, મૂલ્ય ચકાસાયેલ - જો કિંમતો સમાન હોય છે અમે ખોટા ફર્યા. જો કિંમતો ઓછી છે અમે તે જમણી તરફ; અન્યથા, અમે ડાબી ખસેડવામાં આવ્યા છે. ત્યાર બાદ અમે એક નોડ બિલ્ડ. હું થોડો ઝૂમ પડશે. અને અહીં, અમે સુધી કિંમતો WIRE એ જ પ્રયત્ન પ્રયાસ રહ્યા છીએ. શું થઈ રહ્યું છે તે? ચાલો જોવા જો કદાચ Valgrind અમને સંકેત આપી શકે છે. 

હું Valgrind ઉપયોગ માત્ર કારણ કે ખરેખર ઝડપથી Valgrind બનાવ્યા માંગો અને તમને કહે છે જો ત્યાં કોઈપણ મેમરી ભૂલો છે. જ્યારે આપણે કોડ પર Valgrind ચલાવવા માટે, જેમ તમે જોઈ શકો છો કે અધિકાર here--Valgrind./binary_tree--and હિટ દાખલ કરો. તમે જુઓ છો કે અમે કોઈ મેમરી ભૂલ ન હતી, તેથી તેને લાગે છે કે બધું ઠીક અત્યાર સુધી છે. અમે અમુક મેમરી લીક્સ, જે આપણે જાણીએ છીએ હોય છે, કારણ કે અમે નથી અમારા ગાંઠો કોઈપણ મુક્ત થઈ રહ્યું. ચાલો GDB ચાલી જોવા માટે ખરેખર શું ચાલી રહ્યું છે તે કરવાનો પ્રયાસ કરો. અમે gdb કરવું /. પડશે binary_tree. તે માત્ર દંડ બુટ. ચાલો insert પર બ્રેક બિંદુ સુયોજિત કરો. ચાલો ચલાવો. એવું લાગે છે કે અમે insert ખરેખર ક્યારેય કહેવામાં આવે છે. એવું લાગે છે કે આ સમસ્યા માત્ર કે જ્યારે હું નીચે મુખ્ય અહીં બદલી હતી - સમાવે આ printf કોલ બધા - હું આ ખરેખર ક્યારેય બદલીને insert કૉલ કરો. હવે આપણે તેના અજમાવી. ચાલો કમ્પાઇલ. બધા સારા ત્યાં દેખાય છે. હવે આપણે તેના ચલાવવાનો પ્રયત્ન જુઓ, શું થાય છે. ઓલરાઇટ! બધું ખૂબ ત્યાં સારી દેખાય છે. 

ફાઇનલ વિશે વિચારો વસ્તુ છે, ત્યાં આ insert કોઈપણ ધાર કિસ્સાઓમાં? અને તે તારણ છે કે જે સારી રીતે, એક ધાર કેસ કે હંમેશા માટે વિશે વિચારો રસપ્રદ છે, જો તમારો વૃક્ષ ખાલી છે બને છે અને તમે આ insert કાર્ય કહી? તે કામ કરશે? વેલ, ચાલો તેનો પ્રયાસ આપે છે. - Binary_tree સી. - જે રીતે અમે આ પરીક્ષણ જઈ રહ્યાં છો, તો અમે અમારી મુખ્ય કાર્ય કરવા માટે નીચે જાઓ રહ્યાં છો રહ્યું છે, અને તેના બદલે આ જેવી આ ગાંઠો વાયરિંગ અપ કરતાં, અમે હમણાં જ બહાર સમગ્ર વસ્તુ ટિપ્પણી જઈ રહ્યાં છો, અને બદલે જાતને ગાંઠો ઉપર વાયરિંગ છે, અમે ખરેખર માત્ર આગળ જઈ શકે છે અને આ તમામ કાઢી નાખો. અમે શામેલ કરવા કૉલ બધું કરી રહ્યા છીએ. તેથી, ચાલો કરવું - બદલે 5, 8, છે અને 2, અમે 7 દાખલ કરો, 3, અને 9 રહ્યા છીએ. અને પછી અમે પણ 6 તેમજ સામેલ કરવા માંગો છો પડશે. સાચવો. છોડો. દ્વિસંગી વૃક્ષ બનાવે છે. તે બધા કમ્પાઇલ. અમે હમણાં જ તે છે સ્કોર કરી શકે છે અને શું થાય છે, પરંતુ તે પણ ખરેખર મહત્વપૂર્ણ જ હશે કે ખાતરી કરો અમે કોઈ મેમરી ભૂલો નહિં હોય, કારણ કે આ એક અમારા ધાર કિસ્સાઓમાં કે અમે વિશે જાણવાની છે. 

ચાલો ખાતરી કરો કે તે Valgrind હેઠળ કામ કરે છે, જે અમે ફક્ત binary_tree. / Valgrind ચલાવીને કરવું પડશે. એવું લાગે છે કે આપણે ખરેખર એક સંદર્ભમાં એક ભૂલ હોય - અમે આ સેગ્મેન્ટેશન ક્ષતિમાં છે. શું થયું? Valgrind વાસ્તવમાં આપણને કહે છે, જ્યાં તે છે. બહાર થોડો ઝૂમ ઘટાડો. એવું લાગે છે કે તે અમારી insert કાર્ય થઇ રહ્યું છે તે, જ્યાં અમે insert અંતે 4 કદ એક અમાન્ય વાંચી છે, 60 લીટી. ચાલો પાછા જાઓ અને શું થઈ રહ્યું છે તે અહીં. ઝૂમ ઘટાડો ખરેખર ઝડપી. હું ખાતરી કરો કે તે સ્ક્રીન ધાર ન જાઓ કે જેથી અમે બધું જોઈ શકો છો નથી બનાવવા માંગો છો. થોડો કે ખેંચો. ઓલરાઇટ. સરકાવો અને સમસ્યા અહીં છે. જો અમે નીચે વિચાર થાય છે અને અમારી વર્તમાન નોડ પહેલેથી જ છે નલ, અમારા પિતૃ નોડ નલ છે, તેથી જો આપણે ખૂબ ટોચ અહીંથી અંતે લુકઅપ - જો આ વખતે લૂપ ખરેખર ક્યારેય ચલાવે છે કારણ કે અમારી વર્તમાન કિંમત નલ છે - અમારા રુટ નલ છે જેથી વર્તમાન નલ છે - પછી અમારી પિતૃ સેટ નહીં ક્યારેય વર્તમાન માટે અથવા માન્ય કિંમત છે, તેથી, પિતૃ પણ નલ હશે. અમે તે માટે ચેક યાદ કરવાની જરૂર છે સમય દ્વારા અમે નીચે અહીં મળે છે, અને અમે તે પિતૃ કિંમત એક્સેસ કરવાનું શરૂ કરો. તેથી, શું થાય છે? વેલ, જો પિતૃ નલ છે - જો (પિતૃ == NULL) - તો પછી આપણે જાણીએ છીએ કે ત્યાં વૃક્ષ પણ ન હોવું જોઈએ. અમે તે રૂટ પર દાખલ કરવાનો પ્રયાસ કરી હોવા જ જોઈએ. અમે ફક્ત નવા નોડ માટે સમાન રુટ સુયોજિત કરીને આ કરી શકે. તો પછી આ બિંદુએ, અમે ખરેખર આ અન્ય વસ્તુઓ પસાર કરવા માંગતા નહિં હોય. તેના બદલે, અહીં, અમે ક્યાં તો-બીજું જો-બીજું શું કરી શકો છો, અથવા આપણે બધું ભેગા એક બીજું અહીં શકે છે, પરંતુ, અહીં આપણે માત્ર બીજા ઉપયોગ કરે છે અને પડશે તે રીતે કામ કરે છે. હવે, અમે ચકાસણી માટે જઈ રહ્યાં છો કરવા માટે ખાતરી કરો કે જે અમારા પિતૃ નલ નથી પછી તે પહેલાં ખરેખર તેના ક્ષેત્રો ઍક્સેસ કરવાનો પ્રયાસ કરી. આ મદદ કરશે અમને સેગ્મેન્ટેશન ક્ષતિમાં ટાળો. તેથી અમે બહાર નીકળવા, બહાર ઝૂમ, કમ્પાઇલ, ચલાવો. 

કોઈ ભૂલો છે, પરંતુ અમે હજુ મેમરી લીક્સ સમૂહ છે કારણ કે અમે અમારા ગાંઠો કોઈપણ મુક્ત ન હતી. પરંતુ, જો આપણે અહીં જાઓ અને અમે અમારા પ્રિંટઆઉટ પર નજર, અમે જુઓ કે, સારી, અમારા દાખલ તમામ જેવું દેખાય હતા સાચું પરત, જે સારા હોય છે. આ દાખલ બધા છે ખરું છે, અને પછી યોગ્ય સમાવે કોલ્સ પણ છે સત્ય. 

નોકરી સારી! એવું લાગે છે કે અમે સફળતાપૂર્વક insert તેવા પરચૂરણ ખર્ચ કર્યો છે. તે તમામ આપણે આ સપ્તાહ સમસ્યા સેટ સ્પષ્ટીકરણ માટે હોય છે. એક મજા કરવા વિશે વિચારવું પડકાર છે કે તમે કેવી રીતે વાસ્તવમાં જઈ શકે છે અને મફત આ વૃક્ષ ગાંઠો હોય. અમે આમ વિવિધ રીતે કરી શકો છો, પરંતુ હું કે રજા ઉપર પ્રયોગ કરવા પડશે તમે, અને એક મજા પડકાર તરીકે પ્રયાસ કરો, અને ખાતરી કરો કે તમે ખાતરી કરો છો કે આ Valgrind અહેવાલ કોઈ ભૂલો અને કોઈ લીક્સ આપે છે. 

શુભેચ્છા કે આ સપ્તાહ હફમેનના કોડિંગ સમસ્યા સેટ પર, અને અમે આગામી સપ્તાહે તમે જોઈ શકશો! [CS50.TV]