[Powered by Google Translate] [অনুচ্ছেদ 7] [কম আরামদায়ক] [Nate Hardison] [হার্ভার্ড বিশ্ববিদ্যালয়] [এটি CS50.] [CS50.TV] 

স্বাগতম অনুচ্ছেদ 7. ধন্যবাদ হারিকেন Sandy, পরিবর্তে একটি লম্বচ্ছেদ হচ্ছে এই সপ্তাহ, আমরা এই করছি প্রশ্নের বিভাগের মাধ্যমে হাঁটতে-মাধ্যমে,. আমি সমস্যা সহ নিম্নলিখিত স্পেসিফিকেশন 6 সেট করা যাচ্ছে না, এ সমস্ত প্রশ্নের ভিতর দিয়ে যাচ্ছে প্রশ্ন অধ্যায় একটি অনুচ্ছেদ. যদি কোন প্রশ্ন আছে, CS50 আলোচনা এই পোষ্ট করুন. 

ঠিক আছে. আসুন শুরু করি. এখন আমি ডান সমস্যা সেট এর স্পেসিফিকেশন পাতা 3 এ খুঁজছি. আমরা প্রথমে বাইনারি গাছ সম্পর্কে কথা শুরু চলুন যেহেতু যারা এই সপ্তাহে এর সমস্যা সেট প্রাসঙ্গিকতা অনেক আছে - Huffman বৃক্ষ এনকোডিং. এক খুব প্রথম ডাটা স্ট্রাকচার সম্পর্কে আমরা 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 সঙ্গে একটি নতুন নোড নির্মাণ, এটা উপযুক্ত স্থান নির্দেশ করার জন্য টেলিগ্রাম, এবং তারপর পুনরায় তারের 8 9 ডাউন দিকে নির্দেশ করে. যে বেশ দ্রুত, অভিমানী আমরা ঠিক জানি যেখানে আমরা 9 ​​সন্নিবেশ করতে চান. কিন্তু এই বিনিময়ে ট্রেড বন্ধ হল যে এখন আমরা ধ্রুবক সময় এক্সেস হারিয়ে ফেলেছি কোন তথ্য আমাদের কাঠামো বিশেষ উপাদান. উদাহরণস্বরূপ, যদি আমি এই সংযুক্ত তালিকার চতুর্থ উপাদান খুঁজতে চান, আমি তালিকার খুব প্রারম্ভে শুরু করতে যাচ্ছি এবং নোড দ্বারা নোড গণনা মাধ্যমে আমার পথ পর্যন্ত আমি চতুর্থ এক কাজ খুঁজতে. 

যাতে ভাল একটি লিঙ্ক তালিকা তুলনায় কর্মক্ষমতা এক্সেস পেতে পারেন - কিন্তু বেনিফিট যে আমরা তা নিয়ে কিছু ধরে রাখা একটি লিঙ্ক তালিকা থেকে সন্নিবেশ সময় শর্তাদি - একটি বাইনারি গাছ যাও যাও একটু বেশি মেমরি ব্যবহার করার প্রয়োজন হবে. বিশেষ করে, পরিবর্তে শুধুমাত্র একটি বাইনারি গাছ নোডের মধ্যে একটি হচ্ছে পয়েন্টার - সংযুক্ত-তালিকা ভালো নোড আছে - আমরা বাইনারি গাছ নোডের একটি দ্বিতীয় পয়েন্টার যুক্ত চলুন. বরং ঠিক পরের উপাদান এক পয়েন্টার হচ্ছে, আমরা একটি শিশুর বাম এবং ডান একটি শিশু একটি পয়েন্টার আছে চলুন. 

চলুন কি যে আসলে মতো দেখতে দেখতে একটি ছবি আঁকা. আবার, আমি এইসব বাক্সে এবং তীরচিহ্ন ব্যবহার করতে যাচ্ছি. একটি বাইনারি গাছ নোডের মধ্যে মাত্র একটি সহজ বক্স দিয়ে শুরু চালু হবে. এটা মান জন্য একটি স্থান আছে যাচ্ছে, এবং তারপর এটা বাম ও ডান শিশু সন্তানের জন্য একটি স্থান আছে যাচ্ছে. আমি এখানে তাদের লেবেল যাচ্ছি. আমরা বাম সন্তান আছে যাচ্ছে, এবং করছি তারপর আমরা শিশু অধিকার আছে চলুন. অনেক এই কাজ করার বিভিন্ন উপায় আছে. কখনও কখনও জন্য স্থান এবং সুবিধার্থে, আমি আসলে এটা ভালো আমি নিচ করছে এখানে করছি আঁকা করব যেখানে আমি উপরের মূল্য আছে চলেছি, এবং তারপর নিচে ডান দিকে ডান সন্তান, এবং নিচের বাম দিকের বাম সন্তান. উপরের এই চিত্রটি যাব ফিরে, আমরা খুব উপরের মূল্য আছে, তারপর আমরা বাম সন্তান পয়েন্টার আছে, এবং তারপর আমরা ডান সন্তানের পয়েন্টার আছে. 

ইন সমস্যা সেট স্পেসিফিকেশন, আমরা একটি নোডের মধ্যে যে একটা মূল্য আছে 7 অঙ্কন সম্পর্কে কথা বলতে, এবং তারপর একটি বাম সন্তান যে নাল পয়েন্টার, এবং একটি সঠিক সন্তান যে নাল পয়েন্টার. আমরা উভয় স্থান মূলধন শূন্য জন্য লিখতে পারেন বাম এবং ডান উভয় সন্তানের সন্তান, অথবা আমরা এই তির্যক স্ল্যাশ আহরণ করতে পারে এর মাধ্যমে বাক্সে প্রতিটি এটা নাল নির্দেশ. আমি যে মাত্র কারণ যে সহজ করতে যাচ্ছি. আপনি কি এখানে দেখতে হয় একটি খুব সহজ বাইনারি গাছ নোড diagramming দুটি উপায় যেখানে আমরা মান 7 এবং সন্তানের নাল পয়েন্টার আছে. 

কিভাবে আমাদের সাথে লিঙ্ক তালিকা স্পেসিফিকেশন সম্পর্কে আলোচনা দ্বিতীয় অংশ - মনে রাখবেন, আমরা শুধুমাত্র প্রথম উপাদান একটি তালিকার উপর রাখা ছিল সমগ্র তালিকা স্মরণ - এবং অনুরূপভাবে একটি বাইনারি ট্রি সহ, আমরা এক পয়েন্টার উপর রাখা গাছ শুধুমাত্র আছে যাতে সম্পূর্ণ ডাটা স্ট্রাকচার উপর নিয়ন্ত্রণ বজায় রাখার জন্য. এই ট্রি একটি বিশেষ উপাদান ট্রি রুট নোড নামে অভিহিত করা হয়. উদাহরণস্বরূপ, যদি এই একটি নোড - এই নোডের মান ধারণকারী 7 সঙ্গে নাল বাম এবং ডান সন্তানের পয়েন্টার - গাছ ছিল আমাদের মধ্যে কেবল মান, তারপর এই আমাদের রুট নোড হবে. এটা খুব গাছ আমাদের শুরুতে. এই আমরা একটু দেখতে আরো পরিষ্কারভাবে একবার আমরা শুরু গাছ আমাদের আরো নোড যোগ করতে পারেন. আমাকে একটি নতুন পাতা মুঠি ধরে টেনে তুলবো. 

এখন আমরা একটি গাছ যে root-এ রয়েছে 7 আঁকা চলুন, শিশু এবং বাম, ডান এবং শিশুর 9 ভিতর 3 ভিতরে. আবার, এটা বেশ সহজ. আমরা 7 পেয়েছেন, 3 জন্য একটি নোড, 9 জন্য একটি নোড আঁকা, এবং আমি 7 নোড 3 ধারণকারী নির্দেশ বাম সন্তানের পয়েন্টার সেট চলেছি, এবং নোড নোড 9 ধারণকারী 7 ধারণকারী ডান সন্তানের পয়েন্টার. এখন, 3 এবং 9 কোনো সন্তান থাকে না, আমরা তাদের সন্তানের পয়েন্টার সমস্ত ফাঁকা সেট চলুন. এখানে, আমাদের ট্রি রুট নোড নম্বর 7 ধারণকারী অনুরূপ. আপনি যে সব দেখতে যদি আমরা আছে যে রুট নোড একটা পয়েন্টার করতে পারেন, তারপর আমরা আমাদের গাছ মাধ্যমে হাঁটতে পারা এবং উভয় সন্তানের নোড অ্যাক্সেস করতে পারেন - উভয় 3 এবং 9. কোনো প্রতি ট্রি একক নোড যাও পয়েন্টার বজায় রাখা প্রয়োজন. ঠিক আছে. এখন আমরা এই চিত্রটি অন্য একটি নোড যোগ চলুন. আমরা একটি নোড 6 ধারণকারী যোগ চলুন, এবং আমরা নোড 3 ধারণকারী শিশু অধিকার হিসাবে এই যোগ চলুন. যে না, আমি 3-নোডের মধ্যে যে নাল পয়েন্টার নিশ্চিহ্ন করা যাচ্ছে না এবং এটি আপ নোড 6 ধারণকারী নির্দেশ টেলিগ্রাম. ঠিক আছে. 

এই সময়ে, আসুন এর একটি পরিভাষা একটু ঝালিয়ে নেওয়া. যাও কারণে যে এই একটি বিশেষ বাইনারি গাছ বলা হয় শুরু, যে দুই সন্তানের পয়েন্টার আছে. গাছ যে আরো সন্তানের পয়েন্টার আছে অন্য ধরনের আছে. বিশেষ করে, আপনি একটি সমস্যা সেট করুন 5 'চেষ্টা' did. আপনি যে ব্যবহার করে দেখুন যে লক্ষ্য করা হবে, আপনি 27 বিভিন্ন শিশুদের বিভিন্ন পয়েন্টার ছিল - ইংরেজি বর্ণমালার মধ্যে 26 অক্ষরের জন্য প্রত্যেক এক, এবং তারপর ঊর্ধকমা জন্য 27 তম - তাই, যে অনুরূপ ট্রি একটি ধরন. কিন্তু এখানে এটি এর বাইনারি থেকে,, আমরা কেবল দুই সন্তানের পয়েন্টার আছে. 

এই রুট নোড যে আমরা স্বপ্ন ছাড়াও, আমরা করেছি এই শব্দটি প্রায় 'সন্তান.' নিক্ষেপ করা হয়েছে কি জন্য একটি নোড অন্য নোডের একটি শিশু হতে চাওয়ার কথা বলছেন কি? এটা আক্ষরিক মানে হল একটি চাইল্ড নোড হল অন্য একটি নোডের একটি শিশু যদি যে অন্যান্য নোডের চাইল্ড নোড যে নির্দেশ সেট পয়েন্টার এক হয়েছে. এই আরো কংক্রিট পদ পুরা, যদি 3 থেকে 7 চাইল্ড পয়েন্টার এক দ্বারা জোরাল হয়, তাহলে 3 7 সন্তান. যদি আমরা চিন্তা কি 7 সন্তান ছিল - ভাল, আমরা দেখতে যে 7 3 যাও একটি পয়েন্টার এবং 9 একটি ইশারা আছে, তাই 9 এবং 3 হয় 7 শিশুদের. নাইন কোন সন্তান থাকে কারণ তার সন্তানের নাল পয়েন্টার হয়, এবং 3 শুধুমাত্র এক শিশু, 6 আছে. ছয় এছাড়াও কোন শিশু রয়েছে কারণ এর পয়েন্টার উভয় নাল হয়, যা আমরা এখন অধিকার আঁকা হবে. 

উপরন্তু, আমরা একটি বিশেষ নোডের মধ্যে পিতামাতারা এ সম্পর্কে কথা বলা, এবং এই হল, আপনি আশা করতে চাই, এই শিশু বর্ণনার বিপরীত. পরিবর্তে দুটি হিসাবে আপনি মানুষের প্রত্যাশা হতে পারে - প্রতিটি নোডের শুধুমাত্র এক ঊর্ধ্বতন আছে. উদাহরণস্বরূপ, 3 মা বাবা হয় 7. 9 অভিভাবক হয় 7, 6 এবং পিতা বা মাতা হয় 3. এটা যাও নেই. আমরা grandparents এবং grandchildren সম্বন্ধেই পদ আছে, এবং আরো সাধারণভাবে আমরা পূর্বপুরুষ সম্পর্কে কথা বলা এবং একটি নির্দিষ্ট নোড উত্তরপুরুষ. একটি নোডের মধ্যে পূর্বপুরুষ - বা পূর্বপুরুষ পরিবর্তে, একটি নোডের মধ্যে, - হয় নোড থেকে root পরিচয়ে যে নোড পাথ যে থাকা সব. উদাহরণস্বরূপ, যদি আমি নোড 6 খুঁজছি, তারপর পূর্বপুরুষ উভয় 3 এবং 7 হতে যাচ্ছে. উদাহরণস্বরূপ 9 পূর্বপুরুষ,, হয় - যদি আমি নোড 9 এ খুঁজছি - তারপর 9 পূর্বপুরুষ শুধুমাত্র 7. এবং উত্তরপুরুষ হয় ঠিক বিপরীত. যদি আমি 7 উত্তরপুরুষ সব তাকান করতে চান, তারপর আমি এটা অধ নোডের মধ্যে সমস্ত তাকান আছে. সুতরাং, আমি 3, 9, এবং 7 উত্তরপুরুষ হিসাবে 6 সব আছে. 

চূড়ান্ত শব্দটি যে আমরা যে বিষয়ে কথা বলা করবেন তা হচ্ছে একটি সহোদর এই ধারণা. সহোদর - এইসব পরিবার শর্তাবলী অনুসরণ বরাবর ধরনের - হয় নোড গাছ একই পর্যায়ে যে হয়. সুতরাং, 3 এবং 9 ভাইবোন আছে কারণ তারা গাছ একই পর্যায়ে রয়েছে. তারা উভয় একই পিতা বা মাতা, 7 আছে. 6 কোন ভাইবোন থাকে কারণ 9 কোনো সন্তান থাকে না. এবং 7 কারণ এটি আমাদের ট্রি রুট আছে ভাইবোন না, এবং শুধুমাত্র কখনও 1 রুট আছে. জন্য 7 ভাইবোন আছে সেখানে 7 উপরের একটি নোড হতে হবে. আছে যাও 7 মা বাবা, যে ক্ষেত্রে 7 আর ট্রি রুট পর্যন্ত করা হবে না. তারপর যে 7 এর নতুন একটি শিশুর পিতা বা মাতা এছাড়াও আছে থাকবে, এবং তারপর যে শিশু হতে 7 ভাইবোন হবে. 

ঠিক আছে. মুভিং উপর. যখন আমরা বাইনারি গাছ আমাদের আলোচনার শুরু, আমরা কিভাবে আমরা তাদের ব্যবহার চালু ছিল স্বপ্ন উভয় অ্যারে এবং সংযুক্ত তালিকার উপর একটি সুবিধা লাভ করে. এবং আমাদের যে কি চলুন এই ক্রম সম্পত্তি হয়. আমরা বলতে স্পেসিফিকেশন অনুযায়ী যে বাইনারি গাছ নির্দেশ দেওয়া হয়, যদি আমাদের জন্য গাছ প্রতিটি নোডের মধ্যে, বাম দিকে তার সেই বংশধরেরা সব - বাম এবং বাম শিশু সন্তানের উত্তরপুরূষ সব - কম মান, এবং ডানদিকে নোড সব আছে - শিশু অধিকার এবং অধিকার সন্তানের উত্তরপুরূষ সব - নোড বর্তমান নোড মান যে আমরা এ খুঁজছেন তার চেয়ে অনেক বেশী আছে. শুধু সরলতার জন্য, আমরা আমাদের যে কোন ট্রির প্রতিলিপি নোড আছে ধরে নিই চলুন. এই গাছ উদাহরণস্বরূপ, আমরা মামলা নিয়ে যাচ্ছেন না যেখানে আমরা root-এ মান 7 আছে  এবং তারপর আমরা মান 7 স্থানের গাছ আছে. এই ক্ষেত্রে, আপনি যে প্রকৃতপক্ষে এই গাছ ক্রমাঙ্কিত বিজ্ঞপ্তি পাবেন. আমরা root-এ মান 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 এবং root-র জন্য শুধুমাত্র সম্ভাব্য মান হল না. আমরা এও হতে পারে 3 root-এ করা. যদি 3 root-এ হয় তাহলে কি হবে? এখানে, জিনিসপত্র পেতে একটু বিট আকর্ষণীয়. তিনটি কোনো মান হল এটি কম নেই, তাই কেবল যে সমগ্র গাছ বাম দিকে যাও নাল হতে যাচ্ছে. এর থেকে কিছু করা যাচ্ছে না এখন পর্যন্ত. ডান যাও, আমরা অর্ডার আরোহী বিভিন্ন জিনিষ তালিকা পারে. আমরা 3, তারপর 6, তারপর 7, তারপর 9 পারে. অথবা, আমরা কি তাহলে 3, 6 পারে, তারপর 9, তারপর 7. অথবা, আমরা কি তাহলে 3, 7 পারে, তারপর 6, তারপর 9. বা, 3, 7 - আসলে নেই, আমরা আর একটি 7 না পারেন. যে আছে আমাদের এক জিনিস. আমরা 9 ​​করবেন, এবং তারপর পারেন 9 থেকে আমরা 6 করবেন এবং তারপর 7 পারেন. অথবা, আমরা কি তাহলে 3, 9 পারেন, তারপর 7, তারপর এবং 6. 

একটি বিষয় এখানে আপনার দৃষ্টি আকর্ষণ করতে হয় এই যে গাছ হয় একটু অদ্ভুত সুদর্শন. বিশেষত, যদি আমরা ডান পাশের 4 গাছ তাকান - আমি তাদের বৃত্ত, এখানে পাবেন - এই ট্রি একটি লিঙ্ক তালিকা অনুরূপ অংশবিশেষ. প্রতিটি নোডের শুধুমাত্র একটি শিশু আছে, এবং তাই আমরা এই গাছ মত কাঠামো, যা আমরা দেখতে কোনো উদাহরণ জন্য না,,  এই এক নির্জন এখানে উপর থেকে নিচ বাম দিকের গাছ. আসলে এই গাছ হয় বাইনারি গাছ অধ: পতিত বলা হয়, এবং আমরা এই সম্পর্কে ভবিষ্যতে আরো কথা বলা হবে - বিশেষ করে যদি আপনার অন্যান্য কম্পিউটার বিজ্ঞান কোর্স নিতে নেভিগেশন এড়িয়ে যান. এই বৃক্ষ হল অধঃপতিত. এগুলি কারণ প্রকৃতপক্ষে, এই কাঠামো নিজেই ধার খুব দরকারী না  যাও বার অনুরূপ একটি লিঙ্ক তালিকার যে লুকআপ. এই অতিরিক্ত পয়েন্টার - আমরা অতিরিক্ত মেমরি সুবিধা গ্রহণ না পাওয়া - কারণ আমাদের এই কাঠামো উপায় হচ্ছে খারাপ. বরং নেভিগেশন এড়িয়ে যান এবং বাইনারি গাছ যে root-এ 9 আছে আঁকা আউট, যা চূড়ান্ত কেস যে আমরা চাই, আমরা পরিবর্তে এই সময়ে, এই শব্দটি সম্পর্কে অন্য একটি সামান্য বিট কথা বলা যাচ্ছে আমরা যে গাছ, যার উচ্চতা বলা হয় সম্পর্কে যখন কথা বলা ব্যবহার. 

একটি গাছ এর উচ্চতা হল থেকে root পরিচয়ে সর্বাপেক্ষা দূরবর্তী নোডের মধ্যে দূরত্ব, বরং বা হপস সংখ্যা যে আপনি যাতে থাকবে রুট থেকে শুরু এবং তারপর গাছ মধ্যে সর্বাপেক্ষা দূরবর্তী নোড আপ শেষ. যদি আমরা কিছু এই গাছের যে মুহূর্তে আমরা এখানে টানা করেছি, চেহারা আমরা 3 দেখতে পারেন যে যদি আমরা উপরের বাম প্রান্তে এই গাছ নিতে এবং আমরা শুরু, তারপর আমরা 1 হপ 6 পেতে, একটি দ্বিতীয় হপ 7 পেতে করা আছে, এবং একটি তৃতীয় হপ 9 পেতে. সুতরাং, এই গাছ উচ্চতা হল 3. আমরা এই সবুজ গাছ রূপরেখা জন্য একই ব্যায়াম করতে পারেন, এবং আমরা দেখতে যে এই গাছের সমস্ত উচ্চতা হয় প্রকৃতপক্ষে 3. এটা কি তোলে তাদের অবক্ষয়িত অংশ - যে তাদের উচ্চতা শুধুমাত্র সম্পূর্ণ গাছ বিভিন্ন নোডের সংখ্যার চেয়ে এক কম. যদি আমরা এই অন্যান্য অন্যদিকে গাছ যে লাল সঙ্গে পরিবৃত, তাকান, আমরা দেখতে যে সর্বাপেক্ষা দূরবর্তী পাত নোড হল 6 এবং 9 - পাতার হচ্ছে যারা নোড যে কোন সন্তান আছে. সুতরাং, অর্ডার থেকে রুট নোড হয় 6 অথবা 9 পেতে, আমরা এক হপ 7 পেতে করতে হবে এবং তারপর একটি দ্বিতীয় হপ 9 পেতে, এবং অনুরূপভাবে, কেবল একটি দ্বিতীয় হপ 6 7 থেকে পেতে. সুতরাং, এই গাছ এখানে বেশী উচ্চতা শুধুমাত্র 2. আপনি ফিরে যান এবং অন্যান্য গাছের সব জন্য যে পূর্বে আমরা আলোচনা করতে পারেন 7 এবং 6 থেকে শুরু করে, এবং আপনি যে ঐ গাছ সব উচ্চতা হয় 2 পাবেন. 

কারণ আমরা যে বিষয়ে কথা বলা হয়েছে করেছি বাইনারি গাছ আদেশ এবং কেন তারা কুল কারণ হল আপনি তাদের মাধ্যমে অনুসন্ধান করতে পারেন একটি সাজানো একটি অ্যারের মধ্যে অনুসন্ধানের অনুরূপ উপায়. এই যেখানে আমরা যে উন্নত লুকআপ সময় পেয়ে সম্পর্কে কথা বলা উপর সহজ লিঙ্ক তালিকা. সঙ্গে একটি লিঙ্ক তালিকা - যদি আপনি একটি বিশেষ উপাদান খুঁজে পেতে চান - আপনি ভাল রৈখিক অনুসন্ধান কিছু বাছাই করা যাচ্ছে না করেন যেখানে আপনি একটি তালিকা এবং হপ এক দ্বারা এক প্রারম্ভে শুরু - একটি নোড দ্বারা একটি নোড - এর মাধ্যমে সম্পূর্ণ তালিকা পর্যন্ত আপনি খুঁজে যাই হোক না কেন আপনি অনুসন্ধান করছেন. যেহেতু, আপনি যদি একটি বাইনারি গাছ যে এই সুন্দর বিন্যাসে সঞ্চিত আছে, আপনি আসলে একটি বাইনারি অনুসন্ধান করা হচ্ছে আরও পেতে পারেন যেখানে আপনি এবং বিভক্ত করা জিতা এবং প্রতিটি ধাপ এ গাছ যথাযথ অর্ধেক মাধ্যমে অনুসন্ধান. চলুন কিভাবে যে কাজ দেখতে. 

যদি আমরা আছে - আবার, আমাদের মূল গাছ ফিরে যাচ্ছে - আমরা 7 শুরু, আমরা বাম দিকে 3 অধিকার 9,, এবং 3 অধ আমরা 6 আছে. আমরা যদি এই গাছ মধ্যে 6 নম্বর জন্য অনুসন্ধান করতে চান, আমরা root-এ শুরু চাই. আমরা মান আমরা, 6 বলে খুঁজছেন তুলনা হবে, মান নোড আমরা বর্তমানে যে, এ 7 করছি সঞ্চিত, যে 6 প্রকৃতপক্ষে কম 7, যাতে আমরা বাম সরাতে চাই. যদি এর মান 6 7 তার চেয়ে অনেক বেশী ছিল, আমরা পরিবর্তে অধিকার সরানো হবে. যেহেতু আমরা জানি যে - কারণে আমাদের আদেশ বাইনারি ট্রি কাঠামো - মান 7 কম সমস্ত 7 বাঁদিকে সঞ্চিত করা যাচ্ছে, কোন প্রয়োজন এমনকি গাছ ডানদিকে মাধ্যমে খুঁজছেন বিরক্ত আছে. একবার বাঁদিকে সরানো এবং আমরা আমরা নোড 3 থাকবে এখন করছি, আমরা যে একই তুলনা আবার না যেখানে আমরা 3 এবং 6 তুলনা করতে পারেন. এবং আমরা দেখি যে যখন 6 - মান আমরা খুঁজছেন - 3 চেয়ে অনেক বেশী, আমরা নোড 3 ধারণকারী ডানদিকে যেতে পারেন. এখানে এখন পর্যন্ত কোন বাম দিকে, তাই আমরা যে উপেক্ষা করা যেতে পারে. কিন্তু আমরা শুধু জানি যে কারণ আমরা গাছ নিজেই এ খুঁজছেন, এবং আমরা যে গাছ কোন সন্তান আছে দেখতে পারেন. 

এটা বেশ সহজ এই গাছ অল্পক্ষণের 6 আপ যদি আমরা নিজেদেরকে মানুষ হিসাবে কাজ করে থাকেন, কিন্তু এর এই প্রক্রিয়া অনুসরণ যান্ত্রিকভাবে একটি কম্পিউটার ভালো যাক কি সত্যিই বুঝতে এলগরিদম. এই মুহুর্তে, আমরা এখন একটি নোডের মধ্যে যে 6 রয়েছে এ করছি, এবং আমরা মান 6 খুঁজছেন, তাই প্রকৃতপক্ষে, আমরা যথাযথ নোড পাওয়া করেছি. আমরা আমাদের গাছ মান 6 পাওয়া গেছে, এবং আমরা আমাদের অনুসন্ধান করতে পারবে. এই সময়ে, কি করছেন তার উপর নির্ভর করে, আমরা বলতে পারেন, হ্যাঁ, আমরা মান 6 পাওয়া গিয়েছে, এটা আমাদের গাছ বিদ্যমান. অথবা, যদি আমরা একটি নোড বা সন্নিবেশ করার কিছু পরিকল্পনা করছি, আমরা এই সময়ে তা করতে পারে. 

চলুন শুরু করা যাক একটি দম্পতি আরো অনুসন্ধান শুধু কিভাবে এই কাজ করে দেখতে না. চলুন কি যদি আমরা চেষ্টা মান 10 এবং সন্ধান করার ছিল তাকান. যদি আমরা মূল্য 10 সন্ধান করার ছিল, আমরা root-এ শুরু হয়নি. আমরা যে 10 7 তার চেয়ে অনেক বেশী, তাই আমরা দেখতে ডান দিকে সরাতে চাই চাই. আমরা 9 ​​এবং 10 থেকে 9 তুলনা পেতে এবং যে 9 প্রকৃতপক্ষে কম 10 দেখতে চাই. তাই আবার, আমরা অধিকার নিয়ে যেতে চেষ্টা চাই. কিন্তু এই সময়ে, আমরা যে আমরা একটি নাল নোড করেন বিজ্ঞপ্তি চাই. সেখানে কিছুই নেই. যেখানে কিছুই করা উচিত 10 পর্যন্ত. এই যেখানে আমরা ব্যর্থতা রিপোর্ট করতে পারেন - যা প্রকৃতপক্ষে সেখানে কোন গাছ 10. এবং পরিশেষে, যাক এর ক্ষেত্রে যেখানে আমরা গাছ অল্পক্ষণের 1 আপ করার চেষ্টা মধ্য দিয়ে যেতে হবে. এটি অনুরূপ কি বদলে যাচ্ছে ডান ছাড়া যদি আমরা চেহারা 10 আপ, যাও, আমরা বাম যেতে চলুন. আমরা 7 থেকে আরম্ভ হয় এবং যে 1 7 তুলনায় কম, তাই আমরা বাঁদিকে সরানো. আমরা 3 পেতে এবং যে 1 3 তুলনায় কম, তাই আবার আমরা বাম সরাতে চেষ্টা করুন. এই পর্যায়ে আমরা একটি নাল নোড আছে, তাই আবার আমরা ব্যর্থতা রিপোর্ট করতে পারেন. 

যদি আপনি বাইনারি গাছ সম্পর্কে আরো জানতে চান, একটি মজার সামান্য সমস্যা যে আপনি তাদের সাথে করতে পারেন আভা আছে. আমি আঁকার চর্চা এইসব চিত্র এক দ্বারা এক আউট করার পরামর্শ বিভিন্ন ধাপের মাধ্যমে এবং সমস্ত নিম্নলিখিত, কারণ এই অতি - উপকারে আসা হবে না আপনি যখন Huffman এনকোডিং সমস্যা সেট করছেন কিন্তু ভবিষ্যতে কোর্স - শুধু শেখার কিভাবে ডাটা স্ট্রাকচার আঁকতে আউট এবং সমস্যা মাধ্যমে মনে সঙ্গে কলম এবং কাগজ বা, এই ক্ষেত্রে, রহমান এবং লেখনী. 

যদিও এই মুহুর্তে, আমরা উপর কিছু কোডিং অনুশীলনের না সরানো চলুন এবং প্রকৃতপক্ষে এই বাইনারি গাছ এবং সাথে খেলা দেখতে. আমি ফিরে যাও আমার কম্পিউটারের মাধ্যমে সুইচ যাচ্ছি. জন্য পরিবর্তে CS50 রান বা CS50 শূন্যস্থানের ব্যবহার অধ্যায়, এই অংশ, আমি যন্ত্র ব্যবহার করতে যাচ্ছি. 

সমস্যা সেট স্পেসিফিকেশন সঙ্গে নিম্নলিখিত বরাবর, আমি দেখতে যে আমি যন্ত্র খুলুন অনুমিত করছি, আমার ড্রপবক্স ফোল্ডারে যান, নামক একটি ফোল্ডার তৈরি অনুচ্ছেদ 7, এবং তারপর নামক কোনো ফাইল binary_tree.c তৈরি. আমরা শুরু করছি. আমি আনুষঙ্গিক ইতিমধ্যেই খোলা পেয়েছেন. আমি একটি টার্মিনাল মুঠি ধরে টেনে তুলবো যাচ্ছি. আমি ড্রপবক্স ফোল্ডারে যেতে যাচ্ছি, একটি ডিরেক্টরিতে নামক section7 করা, দেখুন এবং এটা সম্পূর্ণই খালি. এখন আমি binary_tree.c খুলুন যাচ্ছি. ঠিক আছে. খালি ফাইল - আমরা শুরু করছি. 

যাক এর স্পেসিফিকেশন ফিরে যান. বৈশিষ্টে একটি নতুন সংজ্ঞা তৈরি জিজ্ঞেস টাইপ একটি নোডের জন্য বাইনারি গাছ int মান ধারণকারী - ঠিক মত মান যে আমরা আগে আমাদের diagramming মধ্যে সৃষ্টি আউট. আমরা এই boilerplate typedef যে মুহূর্তে আমরা এখানে ব্যবহার করেছেন চলুন আপনি যে সমস্যা সেট 5 থেকে সনাক্ত করা উচিত - যদি আপনি হ্যাশ অতিক্রমকারী speller প্রোগ্রামের টেবিল উপায় কি. আপনি গত সপ্তাহে এর অধ্যায় থেকে তা সনাক্ত করা উচিত যেখানে আমরা লিঙ্ক তালিকা সম্পর্কে বললাম. আমরা একটি struct নোডের এই typedef পেয়েছেন, এবং আমরা struct নোডের এই পূর্বেই এই নাম দেওয়া struct নোড করেছি যাতে পরে আমরা তা থেকে আমরা struct নোড পয়েন্টার আছে চাইবেন পাঠাতে পারেন হিসাবে আমাদের struct অংশ, কিন্তু আমরা কি তাহলে এই আবৃত করেছি - অথবা এর পরিবর্তে, ঘিরা এই - একটি typedef মধ্যে যাতে, পরে কোড, আমরা এই struct যাও পরিবর্তে শুধুমাত্র একটি struct নোডের একটি নোড হিসাবে পাঠাতে পারেন. 

এই একাকী সংযুক্ত তালিকা সংজ্ঞা অনুরূপ যে আমরা দেখেছি গত সপ্তাহে হবে. এই কাজের জন্য, আমি শুধু লেখা boilerplate আউট দ্বারা আরম্ভ. আমরা জানি যে আমরা একটি পূর্ণসংখ্যা মান আছে, তাই আমরা int মান, এবং তারপর করা পরিবর্তে পরবর্তী উপাদান শুধু একটি হচ্ছে পয়েন্টার পাবেন - হিসাবে আমরা এককভাবে সংযুক্ত তালিকার সঙ্গে কি - আমরা বাম এবং ডান সন্তানের পয়েন্টার আছে চলুন. খুব সুন্দর সহজ - struct নোড * বাম সন্তান; এবং struct নোড * শিশু অধিকার;. কুল. যে একটি প্রশংসনীয় ভাল শুরু মত দেখাচ্ছে. যাক এর স্পেসিফিকেশন ফিরে যান. 

এখন আমরা একটি গাছ মূল নোডের জন্য একটি বিশ্বব্যাপী * পরিবর্তনশীল ঘোষণা করা প্রয়োজন. আমরা এই গ্লোবাল ঠিক মত আমরা আমাদের লিঙ্ক তালিকা এছাড়াও বিশ্বের প্রথম পয়েন্টার তৈরি করতে যাচ্ছেন. এই ছিল যাতে কাজ করে যে আমরা লিখুন আমরা এই রুট কাছাকাছি রাখতে পার না - যদিও আমরা যে আপনি যদি না যাও recursively এই ফাংশন লিখতে চান দেখতে পাবেন, এটি প্রথমে ভালো ভালো পাস না একটি বিশ্বব্যাপী হিসাবে কাছাকাছি হতে পারে এবং পরিবর্তে এটি আরম্ভ স্থানীয়ভাবে আপনার প্রধান কাজ. কিন্তু, আমরা এটি বিশ্বজুড়ে করতে শুরু করব. আবার, আমরা শূণ্যস্থান কয়েক দিন, এবং আমি একটি নোড * রুট ডিক্লেয়ার চলেছি করব. শুধু আমি নিশ্চিত যে এই uninitialized না ছেড়ে চলে যাও না, আমি নাল এটা সমান সেট যাচ্ছি. মূল কাজ এখন, - যা আমরা সত্যিই দ্রুত ডান এখানে লিখতে হবে - int প্রধান (int-argc, গৃহস্থালির কাজ const * argv []) - এবং আমি const হিসাবে আমার argv অ্যারের ঘোষণা শুরু যাচ্ছে ঠিক তাই যে আমি জানি না যে যারা যুক্তি হয় আর্গুমেন্ট যে আমি সম্ভবত পরিবর্তন করতে না চান. যদি আমি তাদের পরিবর্তন করতে চান সম্ভবত আমি করা উচিত তাদের কপি তৈরি. আপনি এই কোড অনেক দেখতে পাবেন. এটা সূক্ষ্ম উপায় হয়. এটা হিসাবে এটি ছেড়ে সূক্ষ্ম - const যদি চান বর্জন করা. আমি সাধারণত এটি স্থাপন করা ঠিক তাই যে আমি নিজেকে স্মরণ করিয়ে দেওয়া  যে আমি সম্ভবত ঐ আর্গুমেন্ট সংশোধন করতে না চান. 

সর্বদা হিসাবে, আমি এই প্রধান শেষে ফিরে 0 লাইন অন্তর্ভুক্ত যাচ্ছি. এখানে, আমি আমার রুট নোড আরম্ভ করা হবে. যেমন আছে তেমনি অধিকার এখন, আমি একটি নাল পয়েন্টার যে সেট এর পেয়েছেন, তাই এটা কিছুই নির্দেশ করে না. যাতে আসলে নোড নির্মাণের শুরু, আমি সর্বপ্রথম এটি জন্য মেমরি বরাদ্দ করা প্রয়োজন. আমি গাদা malloc মেমরি ব্যবহার করে তা করতে যাচ্ছি. আমি root-র সমান malloc ফলে সেট চলেছি, এবং আমি sizeof অপারেটর একটি নোড মাপ নিরূপণ ব্যবহার করতে যাচ্ছি. যে কারণে আমি sizeof নোড হিসাবে ব্যবহার করার জন্য বিরোধিতা বলে, malloc (4 + 4 +4) বা malloc 12 - ভালো কিছু করছেন - এর কারণ হল আমি আমার কোড যতটা সম্ভব সামঞ্জস্যপূর্ণ হতে চান. আমি এই. গ ফাইলটি যোগ করতে চান, যন্ত্রপাতি এটা কম্পাইল, এবং তারপর আমার 64 বিট ম্যাক এটা কম্পাইল - অথবা একটি সম্পূর্ণ ভিন্ন আর্কিটেকচার - এবং আমি এই একই কাজ করতে চান. 

যদি আমি ভেরিয়েবল মাপ সম্পর্কে অনুমানের তৈরীর করছি - কোন int অথবা একটি পয়েন্টার মাপ মাপ - তারপর আমি আর্কিটেকচারের ধরণের সম্পর্কে করছি ধারনাগুলো তৈরীর যা সাফল্যের সঙ্গে আমার কোড কম্পাইল করার সময় রান করতে পারেন. সর্বদা sizeof ম্যানুয়ালি struct ক্ষেত্র summing বিপরীতে ব্যবহার. অন্যান্য কারণ যে প্যাডিং যে কম্পাইলার struct মধ্যে রাখে হতে পারে সেখানে. কেবল ব্যক্তিগত ক্ষেত্র summing যে আপনি সাধারণত কিছু করে যেতে চাই না, তাই, যে লাইন মুছে দিন. এখন সত্যিই, এই রুট নোড সূচনা, আমি তার বিভিন্ন ক্ষেত্র ও মান চলা যাও আছে যাচ্ছি. উদাহরণস্বরূপ, আমি জানি আমি মান 7 আরম্ভ করতে চান, এবং এখন জন্য আমি বাম সন্তানের নাল সেট করা যাচ্ছে না এবং সঠিক সন্তানের নাল হবে. গ্রেট! আমরা বৈশিষ্ট যে অংশ করেছেন. 

পাতা 3 নীচে স্পেসিফিকেশন নিচে তিনটি আরো নোড নির্মাণ আমাকে জিজ্ঞেস করল - 9 এক সাথে 3, এক 6 ধারণকারী, এবং এক ধারণকারী - এবং তারপর তাকে উপরে তারের তাই এটা ঠিক আমাদের মত গাছ চিত্রটি দেখায় আমরা যে বিষয়ে কথা বলছি, পূর্বে ছিল. চলুন শুরু করা যাক না এখানে যে চমত্কার দ্রুত. আপনি সত্যিই দ্রুত যে আমি প্রতিলিপি কোড একটি গুচ্ছ লেখা শুরু যাচ্ছি দেখতে পাবেন. আমি একটি নোড * তৈরি করতে চাই এবং এটা আমার তিন কল চালু করছি না. আমি এটা malloc (sizeof (নোড)) সমান সেট যাচ্ছি. আমি তিনটি সেট = 3> মান যাচ্ছি. তিন -> left_child = শূন্য; তিনটি -> ডান _child = শূন্য; হিসাবে ভাল. যে দেখায় রুট আরম্ভ যাও প্রশংসনীয় অনুরূপ, এবং যে ঠিক কি আমি যদি আমি শুরু 6 এবং 9 আরম্ভ হিসাবে ভাল আছে যাচ্ছি. আমি যে কি সত্যিই দ্রুত পাবেন - প্রকৃতপক্ষে, আমি একটা সামান্য কপি এবং পেস্ট করতে চলেছি, ঠিক আছে - এবং আমি নিশ্চিত যে করা.  এখন, আমি করেছি এবং এটি কপি করা হবে আমি এগিয়ে যাব 6 এই সমান সেট করতে পারেন. আপনি যে এই কিছুক্ষণ সময় লাগে এবং অতি - কার্যকরী নয় দেখতে পারেন. অল্পমাত্র বিট, আমরা একটি ফাংশন যা আমাদের জন্য এই করবেন লিখুন করব. আমি একটি 9 সঙ্গে এই প্রতিস্থাপন করতে চান, একটি 6 সঙ্গে যে প্রতিস্থাপন করুন. 

এখন আমরা আমাদের সমস্ত নোড সারাংশ তৈরি এবং সক্রিয়া পেয়েছেন. আমরা আমাদের রুট সেট সমান 7 যাও না, বা করেছি মান ধারণকারী 7, আমাদের নোড 3 ধারণকারী, আমাদের নোড 6 ধারণকারী, এবং আমাদের নোড 9 ধারণকারী. এই মুহুর্তে, আমরা সব করতে হবে তা হচ্ছে তারের আপ সবকিছু. কারণ আমি সব NULL পয়েন্টার সক্রিয়া করা হয় ঠিক যে আমি নিশ্চিত হয়ে নেবেন যে আমি ভুলবসত কোনো আছে uninitialized পয়েন্টার নেই. এবং এই সময়ে এছাড়াও থেকে,, আমি আসলে শুধুমাত্র প্রতিটি অন্যান্য নোডের সাথে সংযোগ আছে - বেশী যে তারা আসলে এর সাথে সংযুক্ত যাও - আমি মধ্যে দিয়ে গমন করা এবং না নিশ্চিত করুন যে, সেখানে সব nulls উপযুক্ত জায়গা আছে. 

Root-এ শুরু করে, আমি জানি যে, root এর বাম সন্তানের 3. আমি জানি যে, root-র অধিকার সন্তানের 9. পরে যে, শুধুমাত্র অন্যান্য সন্তানের যে আমি চিন্তা বাকি আছে 3 এর ডান সন্তান, যা 6. এই মুহুর্তে, সব মনে প্রশংসনীয় ভাল. আমরা এই লাইনের কিছু মুছে ফেলব. এখন সবকিছু পরিষ্কার - পরিচ্ছন্ন দেখায় ভালো. চলুন ফিরে যান এবং আমাদের স্পেসিফিকেশন কি আমরা পরের কি আছে দেখতে. 

এই মুহুর্তে, আমরা একটি ফাংশন বলা হয় 'রয়েছে' লিখুন আছে সঙ্গে 'bool রয়েছে (int মান)' র একটি প্রোটোটাইপ. এবং এই ফাংশন রয়েছে সত্য ফিরে যাচ্ছে  যদি যাও আমাদের গাছ বিশ্বব্যাপী root-র দ্বারা পরিবর্তনশীল তীক্ষ্ন  মান ফাংশন এবং মিথ্যা অন্যথায় মধ্যে পাস রয়েছে. চলুন এগিয়ে যান এবং যে না. এই যে আমরা ঠিক লুকআপ রহমান অল্পমাত্র বিট আগে হস্তগত দ্বারা কি মত হতে যাচ্ছে. ধরা যাক এর পিছনে অল্প জুম এবং উপরে স্ক্রোল করুন. আমরা আমাদের অধিকার প্রধান ফাংশন উপরের এই ফাংশন করা চলুন যাতে যাও প্রোটোটাইপিং কোনো সাজানোর আমরা না. সুতরাং, bool রয়েছে (int মান). এখন পর্যন্ত আমরা যেতে. আমাদের boilerplate ঘোষণা আছে. শুধু কি নিশ্চিত যে এই কম্পাইল করতে হবে, আমি এগিয়ে যান এবং এটা সমান মিথ্যা সেট ফিরে যাচ্ছি. রাইট এখন শুধু এই ফাংশন এবং কিছু না সবসময় যে রিপোর্ট করতে হবে মান যে আমরা খুঁজছেন গাছ হয় না. 

এই মুহূর্তে, এটি সম্ভবত একটি ভালো - যেহেতু আমরা একটি কোড আভা লিখিত করেছি এবং আমরা এখনো পরীক্ষার এমনকি চেষ্টা করেন নি - নিশ্চিত করুন যে সব এটি প্রনয়ন করা. যে আমরা কি নিশ্চিত যে আসলে এই কম্পাইল করতে হবে একটি দম্পতি আছে. প্রথমত, আমরা আসছি কোন লাইব্রেরীর কোন ফাংশন যে এখনো আমরা অন্তর্ভুক্ত না করে ব্যবহার করে দেখুন. ফাংশন আমরা এতদূর ব্যবহার করেছি malloc হয়, এবং তারপর আমরা করেছি এই ধরনের ব্যবহার করা হয়েছে - এই ননস্ট্যান্ডার্ড টাইপ বলা '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, এবং আমরা দেখতে যে, হিসাবে আমরা প্রত্যাশিত - কারণ আমরা বাস্তবায়িত হয়নি এখনও রয়েছে, অথবা এর পরিবর্তে, আমরা ফিরে মিথ্যা মধ্যে রেখেছি - আমরা দেখতে যে এটা তাদের জন্য এর ফিরে মিথ্যা, যাতে অধিকাংশ অংশ জন্য সমস্ত এর কাজ মোটামুটি ভাল. 

চলুন ফিরে যান এবং বাস্তবায়ন আসলে এই পর্যায়ে রয়েছে. আমি নিচে স্ক্রল, জুম ইন যাচ্ছে, এবং করছি - মনে রাখবেন, আমরা যে অ্যালগরিদম ব্যবহার ছিল যে আমরা রুট নোড শুরু প্রতিটি নোডের মধ্যে যে আমরা সম্মুখীন হন এবং তারপর, আমরা একটি তুলনা না, এবং উপর ভিত্তি করে আমরা যে তুলনা হয় সন্তানের বাম বা ডান সন্তানের সরাতে. এই বাইনারি অনুসন্ধান কোড লিখেছে যে আমরা আগে শব্দটি খুব অনুরূপ চেহারা হবে. যখন আমরা শুরু করল, আমরা জানি যে আমরা বর্তমান নোডের উপর রাখা চাই আমরা যে এ, খুঁজছি এবং বর্তমান নোড যাও রুট নোড যাও সক্রিয়া করা যাচ্ছে করছি. এবং এখন, আমরা গাছ মাধ্যমে বর্তা চলুন, এবং যে আমাদের বাঁধন শর্ত মনে রাখবেন -  যখন আমরা আসলে উদাহরণ মাধ্যমে কাজ হাতে - যখন আমরা একটি নাল নোড সম্মুখীন, , যখন আমরা একটি নাল সন্তানের দিকে তাকিয়ে না বরং যখন আমরা আসলে একটি নোডের মধ্যে যাও গাছ সরানো এবং দেখা যায় যে আমরা একটি নাল নোড করেন. আমরা বারবার করা যাচ্ছে না হওয়া পর্যন্ত বর্তমান যাও নাল সমান নয়. আমরা কি করতে যাচ্ছি? আমরা পরীক্ষা চলুন যদি (বর্তমান -> মান == মান), তারপর আমরা জানি যে প্রকৃতপক্ষে আমরা নোড যে আমরা যা খুঁজছেন তা খুঁজে পাওয়া যাচ্ছে. তাই এখানে, আমরা সত্য ফিরে আসতে পারেন. অন্যথায়, আমরা কিনা বা না মান মান কম দেখতে চাই. যদি বর্তমান নোড এর মান মান কম আমরা খুঁজছেন, এ মুহূর্তে আমরা সরাতে চলুন. তাই, বর্তমান = নেড়িকুত্তা -> right_child; এবং অন্যথায়, আমরা বাম সরাতে চলুন. নেড়িকুত্তা = নেড়িকুত্তা -> left_child;. চমত্কার সহজ. 

আপনি সম্ভবত যে লুপ দেখায় এই অনুরূপ থেকে চিনতে তারপর ছাড়া বাইনারি অনুসন্ধান আগে শব্দটি, আমরা কম, মধ্য ও উচ্চ সাথে ডিল করা হয়. এখানে, আমরা শুধু একটি বর্তমান মান তাকান আছে, তাই সুন্দর এবং সহজ. চলুন শুরু করা যাক নিশ্চিত হোন যে, এই কোড কাজ করছে. প্রথমত, এটা নিশ্চিত প্রনয়ন করা. এটা আছে মনে হচ্ছে. চলুন এটি চালানোর চেষ্টা. এবং সত্যিই, সেটা ছাপে যা আমরা আশা আউট. এটা গাছ 6 খুঁজে বের করে, কারণ 10 গাছ আছে খুঁজে না 10 না, এবং হয় না খুঁজে 1 না কারণ 1 এর এছাড়াও গাছ না. কুল উপাদান. 

ঠিক আছে. চলুন আমাদের ফিরে যেতে স্পেসিফিকেশন কি এবং এর পরের দেখুন. এখন, এটি আমাদের আরো কিছু গাছ যাও নোড যুক্ত করতে চায়. এটি 5, 2, এবং 8, যোগ এবং নিশ্চিত করুন যে কোড আছে আমাদের করতে চায় এখনও কাজ হিসাবে প্রত্যাশিত. চলুন শুরু করা যাক যে যান না. এই সময়ে, বরং যে বিরক্তিকর কপি এবং পেস্ট আবার করছেন, যাক এর প্রকৃতপক্ষে একটি নোড নির্মাণ একটি ফাংশন লিখুন. যদি আমরা স্ক্রল প্রধান যাও সব উপায় নিচে, আমরা দেখতে যে আমরা এই কাজ করছি এবং উপর আবার প্রতিটি সময় যে আমরা একটি নোড তৈরি করতে চান তাদের খুব অনুরূপ কোড. 

যাক এর একটি ফাংশন যা আসলে আমাদের জন্য একটি নোড নির্মাণ করা হবে এবং এটি ফেরত লিখুন. আমি এটা build_node কল যাচ্ছি. আমি কোনো নির্দিষ্ট মান সঙ্গে একটি নোড নির্মাণ করা যাচ্ছে না. এখানে জুম ইন করুন. প্রথম জিনিস আমি করতে যাচ্ছি প্রকৃতপক্ষে হিপ নোডের জন্য জায়গা তৈরি করতে. সুতরাং, নোড * n = malloc (sizeof (নোড)); n -> মূল্য = মান; এবং তারপর এখানে, আমি ক্ষেত্রগুলি সব থেকে উপযুক্ত মান হতে আরম্ভ করছি যাচ্ছে. এবং খুব শেষে, আমরা আমাদের নোডের মধ্যে ফিরে আসবেন. ঠিক আছে. একটি বিষয় উল্লেখ্য যে এই ফাংশন অধিকার এখানে মেমরি যে গাদা-বরাদ্দ করা হয়েছে একটি পয়েন্টার ফেরত যাচ্ছে. কি এই সম্পর্কে চমৎকার হয় এখন যে এই নোডের - আমরা হিপ কারণ এটি যদি আমরা স্ট্যাকের উপর এটি ঘোষিত ডিক্লেয়ার করা আছে আমরা ভালো এই ফাংশনে এটা করতে পারব না. যে মেমরি সুযোগ অফ যান আউট করবে অবৈধ এবং যদি আমরা সেটা পরে অ্যাক্সেস করার চেষ্টা করা হবে. যেহেতু আমরা গাদা-মেমরি বরাদ্দ ঘোষণা করা হয়, আমরা পরে freeing যত্ন নিতে যাচ্ছে আমাদের প্রোগ্রামের জন্য কোন মেমরি ফুটা করা হইনি. আমরা যা করেছি কোডের punting অন্য সব কিছুর জন্য করা হয়েছে শুধু জন্য সময় সরলতা দোহাই, কিন্তু যদি কখনও কোন একটি ফাংশন ভালো যে দেখায় লিখুন যেখানে আপনি পেয়েছেন - কিছু কল করার জন্য এটি একটি ভিতর malloc বা realloc - আপনি কি নিশ্চিত যে আপনি মন্তব্য নেই কিছু সাজান করা এখনে যে করতে চাই, হেই, আপনি কি জানেন, এক গাদা-বরাদ্দ নোড পাস-মান সঙ্গে সক্রিয়া ফেরৎ. এবং তারপরে আপনি কি নিশ্চিত যে আপনি মনে রাখবেন যে কিছু সাজানোর রাখা করতে চাই আহ্বানকারী ফিরে মেমরি মুক্ত হবে. এইভাবে, যদি কখনও কারো যায় এবং যে ফাংশন ব্যবহার করে, তারা জানেন যে যাই হোক না কেন তারা যে ফাংশান থেকে ফিরে পেতে কিছু সময়ে করা মুক্ত করতে হবে. 

Assuming যে সব আছে এখানে বেশ, ভালো কথা, আমরা আমাদের কোড ঢোকা নিচে এবং এই লাইনের সব অধিকার এখানে প্রতিস্থাপন করতে পারেন আমাদের সাথে কল বিল্ড নোড ফাংশন. চলুন যে সত্যিই দ্রুত না. এক অংশ যে আমরা প্রতিস্থাপন চলুন না এই অংশ নিচে এখানে নীচে যেখানে আসলে আমরা নোড তারের আপ একে অপরের দিকে নির্দেশ করে, যে কারণে আমরা আমাদের কাজ করতে না পারেন. কিন্তু, আমি কি করতে root = build_node (7); নোড * তিনটি = build_node (3); নোড * ছয় = build_node (6); নোড * নয়টি = build_node (9);. এবং এখন, আমরা যাও জন্য নোড যোগ চেয়েছিলেন - নোড * পাঁচটি = build_node (5); নোড * = build_node আট (8); এবং কি ছিল অন্যান্য নোডের? এর এখানে দেখতে দিন. আমরা আরও একটি 2 যোগ চেয়েছিলেন - নোড * দুই = build_node (2);. ঠিক আছে. এই মুহুর্তে, আমরা জানি যে আমরা 7, 3, 9, এবং 6 পেয়েছেন সব তারযুক্ত উপযুক্তভাবে আপ, কিন্তু কি 5, 8, এবং 2? যথাযত ক্রম সবকিছুই রাখা, আমরা জানি যে এর তিনটি সন্তানের অধিকার 6. সুতরাং, যদি আমরা 5 যোগ চলুন, 5 'এ গাছ ডানদিকে যা 3 হয় root এ জন্যে, তাই 5 6 বাম হিসাবে সন্তানের জন্যে. আমরা বলে ছয়, এটা করতে পারেন -> left_child = পাঁচটি; এবং তারপর 8 9 বাম হিসাবে সন্তানের জন্যে, তাই নয় -> left_child = আট; এবং তারপর 2 3 বাম সন্তানের, তাই আমরা যে কি আপ করতে পারেন এখানে - তোমাকে -> left_child = দুই;. আপনি যদি পুরোপুরি অনুসরণ করতে না যে এর সঙ্গে কোন বরাবর, আমি আপনাকে পরামর্শ দিচ্ছি আপনি এটা নিজের আঁকা. 

ঠিক আছে. চলুন এই সংরক্ষণ করুন. চলুন শুরু করা যাক আউট যান এবং নিশ্চিত করুন যে প্রনয়ন করা, এবং তারপর আমরা আমাদের রয়েছে কল মধ্যে যোগ করতে পারেন. দেখে মনে হচ্ছে এখনও সবকিছু প্রনয়ন. যাক এর মধ্যে যান এবং কিছু কল উপস্থিত যোগ করুন. আবার, আমি একটা কপি এবং পেস্ট সামান্য বিট করতে যাচ্ছি. এখন let এর 5, 8, এবং 2 অনুসন্ধান করার জন্য. ঠিক আছে. চলুন শুরু করা যাক এরপর নিশ্চিত হোন যে এই সব দেখায় এখনও ভাল. গ্রেট! এবং সংরক্ষণ করে প্রস্থান করার. এখন এর জন্য লেট, কম্পাইল, এবং এখন এর চালানো যাক. ফলাফল থেকে, এটা দেখে মনে হচ্ছে সমস্তকিছু সুন্দর এবং ভাল কাজ করছে. গ্রেট! তাই এখন আমরা আমাদের রয়েছে লিখিত ফাংশন পেয়েছেন. নেভিগেশন এড়িয়ে চলুন এবং সরানো কিভাবে গাছ মধ্যে যাও নোড সন্নিবেশ কাজ শুরু যেহেতু, আমরা এখন অধিকার করছেন, জিনিষ খুব সুন্দর হয় না. 

যদি আমরা বৈশিষ্টে ফিরে যান, এটি একটি ফাংশন বলা সন্নিবেশ লিখুন আমাদের জিজ্ঞেস করে - আবার, একটি bool ফিরে না কিনা অথবা জন্য আমরা আসলে গাছ নোডের মধ্যে সন্নিবেশ করতে পারে নি - এবং তারপর মান গাছ মধ্যে সন্নিবেশ যাও হিসাবে উল্লেখ করা হয় আমাদের সন্নিবেশ ফাংশন শুধুমাত্র যুক্তি. আমরা সত্য যদি আমরা সত্যিই ট্রি ধারণকারী নোডের মধ্যে মান সন্নিবেশ করুন পারে প্রত্যাবর্তন করবে, যার মানে হচ্ছে যে আমরা, এক, পর্যাপ্ত মেমরি ছিল, এবং তারপর দুই, ইতিমধ্যে যে নোড থেকে গাছ মধ্যে উপস্থিত না - মনে রাখবেন, আমরা ট্রির প্রতিলিপি মান আছে, আছে যাচ্ছে না জিনিসের সহজ করা. ঠিক আছে. কোড ব্যাক. এটি আপ খুলুন. একটু বড় করে দেখুন, তারপর নিচে স্ক্রোল করুন. যাক এর অধিকার রয়েছে উপরের ফাংশন সন্নিবেশ করা. আবার, এটি করা হবে নামক bool সন্নিবেশ (int মান) যাও যাচ্ছে. এটি একটি সামান্য আরো স্থান দিন, এবং তারপর একটি ডিফল্ট হিসাবে,, যাক ফিরে খুব শেষে মিথ্যা রাখা. এখন নিচে নীচে, আসুন এগিয়ে পরিবর্তে নিজে নোড নির্মাণের যান প্রধান নিজেদেরকে এবং তাদের তারের আপ অপরের মত আমরা করছেন দিকে নির্দেশ করে, আমরা কি সেটা আমাদের সন্নিবেশ কার্যকারিতা নির্ভর করব. আমরা আমাদের সন্নিবেশ কার্যকারিতা নির্ভর করা হবে না গোড়া থেকে সম্পূর্ণ গাছ এখনও নির্মাণ, বরং আমরা এই লাইন পরিত্রাণ পাবেন - we'll এই লাইন আউট মন্তব্য - যে নোড 5, 8, এবং 2 নির্মাণ. এবং এর পরিবর্তে, আমরা আমাদের কল সন্নিবেশ ফাংশন প্রবেশ করাতে হবে নিশ্চিত করুন যে আসলে যে কাজ করা. আমরা শুরু করছি. 

এখন আমরা এই লাইন মন্তব্য আউট করেছি. আমরা কেবল এই সময়ে আমাদের গাছ 7, 3, 9, এবং 6 আছে. নিশ্চিত করুন যে এই সব কাজ করতে হয়, আমরা আউট, জুম আমাদের বাইনারি ট্রি করতে পারেন, এটি চালানো এবং আমরা যে উপস্থিত হয় এখন আমাদের যে আমরা সম্পূর্ণ অধিকার দেখতে পারেন - 5, 8, এবং 2 ট্রি উপলব্ধ নয়. কোড ফিরে যান, এবং কিভাবে আমরা প্রবেশ করতে যাচ্ছি? মনে রাখবেন যে আমরা কি কি আসলে যখন আমরা 5 ঢোকাতে হয়, 8, এবং 2 পূর্বে. আমরা যে Plinko খেলাটি যেখানে আমরা root-এ শুরু, গিয়েছিলাম এক এক গাছ এক নিচে যতক্ষণ না আমরা যথাযথ ফাঁক পাওয়া গেছে, এবং তারপর নোডের মধ্যে আমরা যথাযথ স্থানে তারযুক্ত. আমরা একই জিনিস করে যাচ্ছেন. এই কোড যে আমরা ব্যবহৃত লেখা ভালো মূলত ফাংশন রয়েছে যাও স্পট যেখানে নোড হওয়া উচিত, এবং তারপর আমরা নোড সঠিক আছে সন্নিবেশ করছি যাচ্ছে. চলুন শুরু করা যাক যে শুরু করছেন. 

সুতরাং আমরা একটি নোড * নেড়িকুত্তা = রুট আছে; আমরা ঠিক করছি কোড আছে অনুসরণ যাচ্ছে যতক্ষণ না আমরা দেখি যে এটা আমাদের জন্য বেশ কাজ করে না. আমরা গাছ মধ্যে দিয়ে যাচ্ছে যখন বর্তমান উপাদান নাল নয়, এবং যদি আমরা দেখি যে বর্তমান এর মান সমান মান যে আমরা সন্নিবেশ করার চেষ্টা করছি - ভাল, এই এক ক্ষেত্রে যা আসলে আমরা নোডের অন্তর্ভুক্ত করা যায়নি মধ্যে ট্রি কারণ এই অর্থ আমরা একটি প্রতিলিপি মান আছে. এখানে আসলে আমরা মিথ্যা প্রত্যাবর্তন করছেন না. এখন, বর্তমান এর মান যদি অন্য মান কম, এখন আমরা জানি যে আমরা অধিকার সরানো  কারণ মান নেড়িকুত্তা ট্রি অধিকার অর্ধেক জন্যে. অন্যথায়, আমরা বাম সরাতে চলুন. মূলত আমাদের মধ্যে রয়েছে চালনার অধিকার আছে. 

এই মুহুর্তে একবার, যখন আমরা এই লুপ সম্পন্ন করেছেন, আমাদের বর্তমান পয়েন্টার করা হবে প্রতি নির্দেশ যাও নাল যাচ্ছে যদি ইতিমধ্যে ফাংশন ফিরে না করেনি. সুতরাং আমরা করছি স্থানে বর্তমান হচ্ছে যেখানে আমরা নতুন নোডের মধ্যে সন্নিবেশ করতে চান. কি করা যায় অবশেষ যাও যাও আসলে নতুন নোড নির্মাণ করা হয়, যা আমরা চমত্কার সহজেই করতে পারেন. আমরা আমাদের অতি - কুশলী বিল্ড নোড ফাংশন ব্যবহার করতে পারেন, এবং কিছু যে আমরা আগে না কি - আমরা ঠিক ধরিয়া ধরনের নেন কিন্তু এখন আমরা ঠিক নিশ্চিত করার জন্য চেষ্টা করব - আমরা নিশ্চিত যে মান নতুন নোড দ্বারা ফিরে আসলে পরীক্ষা করা হবে নাল না, কারণ আমরা যে মেমরি অ্যাক্সেস যদি এটা নাল শুরু করতে না চান. আমরা নিশ্চিত করুন যে নতুন নোডের নাল সমান হয় না তা পরীক্ষা করতে পারবেন. অথবা এর পরিবর্তে, আমরা দেখতে যদি প্রকৃতপক্ষে এটা নাল করতে পারেন, এবং যদি এটা নাল তারপর, আমরা ফিরে মিথ্যা তাড়াতাড়ি পারেন. 

এই সময়ে, আমরা তার গাছ উপযুক্ত স্পট মধ্যে নতুন নোডের তারের আছে. যদি আমরা মূল ফিরে এবং যেখানে আমরা আসলে আগে মান তারের, আমরা দেখতে যে ভাবে আমরা এটি ছিল করছেন যখন আমরা গাছ 3 লাগাতে চেয়েছিল আমরা মূল বাম সন্তানের ব্যবহার. যখন আমরা গাছ 9 করা, আমরা root-র অধিকার সন্তানের অ্যাক্সেস ছিল. আমরা ঊর্ধ্বতন একটি পয়েন্টার যাতে গাছ মধ্যে একটি নতুন মান স্থাপন করা আছে ছিল. স্ক্রল আপ ফিরে যাও সন্নিবেশ, যে এখানে পুরোপুরি কাজ করে যাচ্ছে না কারণ আমরা একটি ঊর্ধ্বতন পয়েন্টার নেই. কি আমরা করতে সক্ষম হতে চান এই সময়ে হয়,, পিতা বা মাতা এবং এর মান চেক দেখুন - ভাল, ভগবন্, যদি পিতা বা মাতা এর মান বর্তমান মান কম, তারপর ঊর্ধ্বতন এর ডান সন্তানের নতুন নোড হতে হবে; অন্যথায়, ঊর্ধ্বতন এর বাম সন্তানের নতুন নোডের মধ্যে হওয়া উচিত. কিন্তু, আমরা খুব কাছে এই পিতা বা মাতা পয়েন্টার না. 

যাতে এটা পেতে, আসলে আমরা এটা ট্র্যাক আছে করছেন যাচ্ছে হিসাবে আমরা গাছ দিয়ে যেতে এবং আমাদের উপরে লুপ যথাযথ স্পট খুঁজে. আমরা স্ক্রলিং দ্বারা যে ব্যাক আপ কি আমাদের সন্নিবেশ ফাংশন শীর্ষে পারেন এবং অন্য পয়েন্টার পরিবর্তনশীল ট্র্যাকিং অভিভাবক বলা হয়. আমরা প্রাথমিকভাবে নাল এটা সমান সেট চলুন, এবং তারপর প্রতিটি সময় আমরা গাছ দিয়ে যেতে, আমরা ঊর্ধ্বতন পয়েন্টার বর্তমান পয়েন্টার মেলে সেট চলুন. পিতা বা মাতা সমান বর্তমান সেট করুন. এই পথ, প্রতিটি সময় আমরা মধ্য দিয়ে যেতে হবে, আমরা যে হিসাবে বর্তমান পয়েন্টার মান বৃদ্ধি পায় তা নিশ্চিত করার জন্য চলুন পিতা বা মাতা পয়েন্টার এটি অনুসরণ করে - ট্রি বর্তমান পয়েন্টার তুলনায় মাত্র এক স্তর ওপরে বেশী. যে সমস্ত সুন্দর দেখায় ভালো. 

আমি মনে করি যে আমরা এক জিনিস পরিবর্তন করতে চাইবেন এই নোডের ফিরে নাল নির্মাণ. যাতে নোড সফলভাবে আসলে নাল ফিরে পেতে নির্মাণ, আমরা যে কোড সংশোধন করতে হবে, এখানে কারণ, আমরা নিশ্চিত যে malloc একটি বৈধ পয়েন্টার ফেরত না পরীক্ষা না. সুতরাং, যদি (ঢ = শূন্য!), তারপর - যদি malloc একটি বৈধ পয়েন্টার ফেরত তারপর, আমরা এটি আরম্ভ করা হবে; অন্যথায়, আমরা ফিরে যান এবং যে পর্যন্ত আমাদের জন্য নাল ফিরে শেষ করব. এখন সব সুন্দর দেখায় ভালো. চলুন নিশ্চিত এই প্রকৃতপক্ষে প্রনয়ন করা. বাইনারি গাছ, তার এবং উহু, আমরা কিছু উপাদান যাচ্ছে এখানে পেয়েছেন. 

আমরা একটি ফাংশন অন্তর্নিহিত ঘোষণা নোড নির্মাণের পেয়েছেন. এই কম্পাইলার দিয়ে আবার, আমরা উপরের শুরু চলুন. এর অর্থ কি হবে যে আমি নোড নির্মাণের আহ্বান আগে আসলে আমি এটি করেছি ঘোষণা করছি. যাক এর কোড ফিরে যেতে সত্যিই দ্রুত. নীচে স্ক্রোল করুন, এবং নিশ্চিত যথেষ্ট, আমার সন্নিবেশ ফাংশন ঘোষিত হয় বিল্ড নোডের উপরের ফাংশন, কিন্তু আমি এর সন্নিবেশ ভিতরে নোড নির্মাণের ব্যবহার করার চেষ্টা করছি. আমি এবং কপি ঢুকা যাচ্ছে না - এবং তারপর বিল্ড নোড ফাংশন পথ আটকান শীর্ষে আপ এখানে. এই ভাবে আশা, যে কাজ করা. এর দিন যাক এই অন্য যান. এখন এটি সমস্ত প্রনয়ন. সমস্ত ভাল. 

কিন্তু এই সময়ে, আমরা আমাদের সন্নিবেশ ফাংশন বলা আসলে আছে না. আমরা শুধু জানি যে এটা কম্পাইল করা, তাই আসুন যান এবং কিছু কল ইন করা চলুন শুরু করা যাক আমাদের প্রধান কাজ যে. এখানে, আমরা মন্তব্য 5, 8, এবং 2 আউট, এবং তারপর আমরা তারের আপ না ডাউন তাদের এখানে. এর কিছু কল সন্নিবেশ করা যাক, এবং আসুন এছাড়াও স্টাফ একই ধরনের যে আমরা ব্যবহৃত ব্যবহার যখন আমরা নিশ্চিত যে সব ঢোকানো হয়নি সঠিকভাবে শুরু করতে এই printf কল করেছে. আমি কপি এবং পেস্ট করুন চলেছি, পরিবর্তে রয়েছে এবং আমরা সন্নিবেশ করতে যাচ্ছেন. এবং পরিবর্তে 6, 10, এবং 1, আমরা 5, 8, এবং 2 ব্যবহার চলুন. এই আশা গাছ মধ্যে 5, 8, এবং 2 সন্নিবেশ করা উচিত. সঙ্কলন. সমস্ত ভাল. এখন আমরা আসলে আমাদের প্রোগ্রাম চালানো হবে. 

সবকিছু ফিরে মিথ্যা. সুতরাং, 5, 8, এবং 2, এবং না যাওয়া এটা মনে হয় রয়েছে তাদের খুঁজে পান না. যাচ্ছে কি করছেন? চলুন জুম আউট. প্রথম সমস্যা ছিল যে সন্নিবেশ মিথ্যা প্রত্যাবর্তন করলো, এবং এটা ভালো যে কারণ আমরা আমাদের রিটার্ন মিথ্যা কলে বামে, দেখতেও এবং আমরা ফিরে আসলে সত্য না. আমরা যে সেট আপ করতে পারেন. দ্বিতীয় সমস্যা হল এখন, এমনকি যদি আমরা না - এই সংরক্ষণ, এই প্রস্থান করার জন্য, আবার না চালানো হলে, আছে তারপর কম্পাইল এটি চালানোর জন্য - আমরা দেখতে যে অন্য কিছু এখানে ঘটেছে. 5, 8, এবং 2 এখনও পাওয়া গাছ ছিল না. সুতরাং, কি করছেন? 

চলুন এই সময়ে একটি কোড কটাক্ষপাত. চলুন আমরা যদি এই জিনিসটা দেখতে পারেন. আমরা ঊর্ধ্বতন নাল না দিয়ে শুরু. আমরা বর্তমান পয়েন্টার সমান রুট পয়েন্টার সেট, এবং আমরা আমাদের কাজ উপায় গাছ মাধ্যমে ডাউন চলুন. যদি বর্তমান নোড নাল নয় তাহলে, আমরা জানি যে আমরা একটু বিট নিচে নামাও পারেন. আমরা সমান বর্তমান পয়েন্টার হতে আমাদের অভিভাবক পয়েন্টার সেট, মান চেক - যদি মান একই আমরা ফিরে মিথ্যা. যদি মান কম আমরা অধিকার সরানো; অন্যথায়, আমরা বাঁদিকে সরানো. তারপর আমরা একটি নোড নির্মাণের. আমি কিছুক্ষন জুম করব. এবং এখানে, আমরা মান তারের পর্যন্ত একই হতে চেষ্টা চলুন. যাচ্ছে কি করছেন? চলুন যদি সম্ভবত Valgrind আমাদের একটি ইংগিত দিতে পারে দেখুন. 

আমি শুধু Valgrind কারণ দ্রুত Valgrind রান ব্যবহার করার জন্য পছন্দ এবং বলা আছে যদি কোনো স্মৃতি ভুল থাকে. যখন আমরা কোডের উপর Valgrind চালানো, হিসাবে আপনি দেখতে পারেন অধিকার here--Valgrind./binary_tree--and আঘাত লিখুন. আপনি যে আমরা কোন মেমরি ত্রুটি আছে কি না, যাতে দেখে মনে হচ্ছে সবকিছু ঠিক এতদূর. আমরা কিছু তথ্য ফাঁসের মেমরি, যা আমরা জানি আছে না, কারণ আমরা না আমাদের নোড কোনো মুক্ত ঘটছে. চলুন GDB কি আসলে যাচ্ছে দেখতে চালানোর চেষ্টা. আমরা সময় gdb না. / Binary_tree করব. এটা বুট করার পরে, শুধুমাত্র জরিমানা আপ. যাক এর সন্নিবেশ উপর একটি বিভাজক পয়েন্ট সেট. যাক এর সাথে সঞ্চালিত হয়েছে. দেখে মনে হচ্ছে আমরা আসলে বলা সন্নিবেশ না. মনে হচ্ছে সমস্যা ছিল যে আমি যখন পরিবর্তিত প্রধান এখানে নিচে - এইসব রয়েছে থেকে printf কল সব - আমি আসলে এই পরিবর্তন কখনই সন্নিবেশ কল. এখন আমি কি এটা ব্যবহার করে দেখুন. চলুন সঙ্কলন. সমস্ত দেখতেও ভাল আছে. এখন এর এটি চালানোর চেষ্টা দিন, দেখুন কি ঘটে. ঠিক আছে! সবকিছু পরিষ্কার - পরিচ্ছন্ন দেখায় সেখানে ভাল. 

চূড়ান্ত জিনিস সম্পর্কে চিন্তা করা হয়, সেখানে কোনো এই সন্নিবেশ যাও প্রান্ত ক্ষেত্রে? এবং এটি সক্রিয় করে যে, ভাল, এক প্রান্ত ক্ষেত্রে যে সবসময় আমার মনে আকর্ষণীয় হয়, কি যদি আপনার গাছ খালি এবং আপনি এই সন্নিবেশ ফাংশন কল? এটি কাজ করবে? ওয়েল, আমি কি এটা ব্যবহার করে দেখুন. - Binary_tree গ. - আমাদের এই পরীক্ষা করতে বলছে, না আমরা আমাদের প্রধান ফাংশন নামা চলুন, এবং বদলে তারের ভালো এই নোডের আপ, আমরা শুধুমাত্র আপনার সমগ্র মন্তব্য জিনিস যাচ্ছে, এবং পরিবর্তে নোড নিজেদেরকে আপ তারের, আমরা শুধু এগিয়ে যান এবং এই সব মুছে দিতে পারেন. আমরা প্রবেশ করাতে একটি কল সবকিছু করতে যাচ্ছেন. সুতরাং, এর কাজ করি - পরিবর্তে 5, 8, এবং 2, আমরা 7, সন্নিবেশ 3, এবং 9 চলুন. এবং তারপর আমরা আরও 6 হিসাবে ভাল সন্নিবেশ করতে চাইবেন. সংরক্ষণ করুন. প্রস্থান. বাইনারি ট্রি না. এটা সব প্রনয়ন. আমরা শুধু এটা হিসাবে চালানো হয় এবং কি দেখতে পারেন, কিন্তু এটা সত্যিই গুরুত্বপূর্ণ হতে যাচ্ছে এটা নিশ্চিত করুন যে করা আমরা কোন মেমরি ত্রুটি নেই, এই হল আমাদের প্রান্ত ক্ষেত্রে যে আমরা জানি সে সম্পর্কে এক. 

চলুন শুরু করা যাক, নিশ্চিত হয়ে নেবেন যে এটা Valgrind অধীন ভাল কাজ করে, যা আমরা শুধু Valgrind. / binary_tree চলমান দ্বারা করব. দেখে মনে হচ্ছে সত্যিই আমরা এক প্রসঙ্গ থেকে একটি ত্রুটি আছে - আমরা এই সেগমেন্টেশন ফল্ট আছে. কি হয়েছিল? Valgrind আসলে আমাদেরকে বলে যেখানে এটা. একটি সামান্য বিট জুম আউট. দেখে মনে হচ্ছে এটা আমাদের সন্নিবেশ ফাংশন কি ঘটছে সে, যেখানে আমরা সন্নিবেশ একটি আকার 4 অবৈধ পঠিত আছে, লাইন 60. চলুন ফিরে যান এবং কি হচ্ছে এখানে দেখুন. জুম আউট সত্যিই দ্রুত. আমি নিশ্চিত যে এটা পর্দার প্রান্ত তাই আমরা সবকিছু দেখতে পারেন না যেতে করতে চাই. অল্প যে টানুন. ঠিক আছে. স্ক্রোল ডাউন, এবং সমস্যার সঠিক এখানে. যদি আমরা পেতে নিচে কি হয় এবং আমাদের বর্তমান নোড ইতিমধ্যে নাল, আমাদের পিতা বা মাতা নোড হল নাল, তাই যদি আমরা খুব উপরের ডান, এখানে তাকান আপ - যদি এই সময় লুপ আসলে কখনও করুন কারণ আমাদের বর্তমান মান নাল - আমাদের রুট হল নাল তাই বর্তমান হয় নাল - তারপর আমাদের পিতা বা মাতা বর্তমান বা একটি বৈধ মান সেট না পরার, তাই, এছাড়াও ঊর্ধ্বতন নাল হতে হবে. আমরা যে জন্য চেক মনে রাখতে প্রয়োজন আমরা সময় দ্বারা পেতে এখানে নিচে, এবং আমরা শুরু ঊর্ধ্বতন এর মান অ্যাক্সেস. তাই, কি? ওয়েল, যদি পিতা বা মাতা হয় নাল - যদি (পিতা বা মাতা == NULL) - তারপর আমরা জানি যে, হতে গাছ মধ্যে কিছু আছে অবশ্যই. আমরা চেষ্টা করে root-এ এটি সন্নিবেশ করা আবশ্যক. আমরা শুধুমাত্র root-র সমান নতুন নোডের সেটিং দ্বারা তা করতে পারে. তারপর এই সময়ে, আমরা এইসব অন্যান্য জিনিসের মধ্য দিয়ে যেতে চান, আসলে না. পরিবর্তে, এখানে ডান, হয় আমরা একটি অন্যথায়--অন্যথায় যদি করতে পারেন, অথবা আমরা সবকিছু মেশা একটি অন্যথায় এখানে যেতে পারেন, কিন্তু এখানে শুধু আমরা ব্যবহার করি অন্য উপায় এবং এটি যে করব. এখন, আমরা নিশ্চিত করতে আমাদের যে পিতা বা মাতা নাল না পরীক্ষা চলুন তারপর আগে আসলে তার ক্ষেত্র অ্যাক্সেস করার চেষ্টা. এটি আমাদের সেগমেন্টেশন ফল্ট এড়ানো সম্ভব হবে. সুতরাং, আমরা প্রস্থান করার জন্য, জুম আউট, কম্পাইল, রান. 

কোনো ত্রুটি, কিন্তু আমরা এখনও মেমরি তথ্য ফাঁসের একটি গুচ্ছ আছে কারণ আমরা আমাদের নোড কোনো মুক্ত ছিল না. কিন্তু, যদি আমরা যেতে এখানে আপ এবং আমরা আমাদের আউটে তাকান, আমরা দেখতে যে ভাল, আমাদের টিপে সব ভালো, দেখতেও সত্য ফিরে, যা ভাল হয়. টিপে সব সত্য, এবং তারপর উপযুক্ত কল এছাড়াও রয়েছে সত্য. 

গুড জব! দেখে মনে হচ্ছে আমরা সফলভাবে লিখিত সন্নিবেশ করেছি. আমরা সকলে এই সপ্তাহে সমস্যা সেট এর জন্য স্পেসিফিকেশন আছে. এক মজা চ্যালেঞ্জ সম্পর্কে ভাবতে হয় কিভাবে আসলে আপনি যেতে করতে হবে এবং বিনামূল্যে এই গাছ বিভিন্ন নোডের মধ্যে সমস্ত. আমরা তাই বিভিন্ন উপায়ে করতে পারেন, কিন্তু আমি যে আপনি চলে যাবেন আপ পরীক্ষা করা, এবং মজার একটি চ্যালেঞ্জ হিসাবে, এবং চেষ্টা করে নিশ্চিত করুন যে আপনি কি নিশ্চিত করতে পারবেন না যে এই Valgrind প্রতিবেদনে ত্রুটি এবং কোন তথ্য ফাঁসের ফেরৎ. 

গুড লাক এই সপ্তাহে এর Huffman কোডিং সমস্যা সেট, এবং আমরা আপনাকে দেখতে পরের সপ্তাহে করব! [CS50.TV]