یکی از سؤالات با فراوانی زیاد که توی انجمن‌ها و گوشه کنار اینترنت بهش بر خوردم بحث داده‌های والد و فرزندی یا همون ساختار های درختی بوده. با وجود اینکه توی خیلی از دروس دانشگاهی همین ایران در مورد ساختار های درختی و روش‌های پیمایش اون ها بحث میشه و تمرین و سؤال امتحانی ازشون میاد ولی خیلی از فارغ التحصیلان رشته نرم‌افزار دقیقاً نمیدونن ساختار های درختی چه کاربردی دارن ، البته خیلی هم جای سؤال نیست وقتی مثال‌ها و تمرین‌هایی که توی کلاس حل میشه با کاربردهای اصلی که توی دنیای واقعی وجود داره خیلی خیلی فاصله داره.

از مهمترین کاربردهایی که این ساختار های والد و فرزندی دارند بخش‌های مربوط به پیمایش وب سایت‌ها هستند که میتونه منوی آبشاری (عمودی یا افقی) یا دسته بندی کالا های یک فروشگاه یا نمایش پوشه و فایل و غیره … باشه. در واقع اگر نیاز داشته باشیم که این منو ها یا دسته بندی ها را به صورت دینامیک ایجاد کنیم و مدیر سایت بتونه توشون دخل و تصرف کنه حتماً باید بدونیم چطور باید اونها را پیمایش کنیم و توی UL/LI لیست ها که مورد نیاز اسکریپت های منو آبشاری و کنترل های درختی هستند استفاده کنیم.

من کل توضیحات پایین را به صورت عملی در قالب یک پایگاه داده Sqlite و فایل سورس برنامه و کنترل درختی jsTree به این پُست ضمیمه کردم که میتونید از اینجا دانلود کنید. اما حتماً توضیحات زیر را بخونید تا متوجه باشین کل کار چطور انجام شده.

به چند روش میشه داده‌های درختی را توی پایگاه داده قرار داد اما متداول ترین اون ها که در این پُست هم با اون کار میکنیم به این شکل هست که جدول داده شامل سه ستون اصلی (شماره رکورد یا همون ID ، نام Node و شماره رکورد یا همون ID والد) هستش. برای پیمایش داده‌ها هم از طریق یک حلقه و تابع بازگشتی عمل میکنیم و داده‌ها را نمایش میدیم.

مهمترین نکته‌ای که در زمان نمایش داده‌ها توی حلقه پیمایش و تابع بازگشتی باید رعایت کنیم این هست که باید تکنیکی را به کار ببریم تا نیاز نباشه برای هر Node و دریافت فرزندانش یک Query به پایگاه داده بزنیم. اگه تعداد والد ها و فرزند ها زیاد باشه این Query های زیاد باعث میشه Performance به شدت پایین بیاد. برای حل این مشکل یکبار همه داده‌ها را با Query از جدول میخونیم و دو آرایه با ایندکس های متفاوت والد و شماره رکورد ایجاد میکنیم. آرایه با ایندکس والد اطلاعات کامل Node خودش را نگه میداره و آرایه با ایندکس شماره رکورد نام Node و والد را نگه میداره. البته آرایه دوم فقط برای محاسبه مسیر یک Node تا ریشه کاربرد داره و میتونید اصلاً ایجادش نکنید.

دو تا ریزه کاری کوچیک دیگه هم توی سورس هست که بهتره اشاره کنم. یکی اینکه توی توابع بازگشتی متغیری که ساختار HTML مربوط به UL/LI (در تابع make_list) و متغیری که نام Node را نگه میداره (در تابع add_path) با Reference داده شده و دومی اینکه در زمان نمایش مسیر از ریشه تا Node مورد نظر چون داریم از پایین به بالا حرکت میکنیم در آخر باید آرایه را Reverse کنیم تا نمایش صحیحی از مسیر داشته باشیم. در مورد نمایش مسیر از ریشه هم طبیعیه که مثلاً باید شماره ID رکورد Node را داشته باشیم.

توجه : منظور از Node کلی هست و میتونه نام منو یا نام دسته باشه.

این یکصدمین پُست من توی این وبلاگ بود و امیدوارم با همت و تلاش بیشتر این روند را ادامه بدم.

پی نوشت : توی نظرات یکی از دوستان میخواست بدونه چطور یک node با تمام زیر شاخه هاش حذف کنیم. خوب کار سختی نیست و کافیه id اون node و زیر شاخه هاش را بدست بیاریم و query مربوط به حذف را بنویسیم :

			function list_child_ids($id,&$arr){
				global $nodes;
				$arr[] = $id;
				foreach($nodes[$id] as $node){
					if (isset($nodes[$node["c_id"]]) && is_array($nodes[$node["c_id"]]))
					list_child_ids($node["c_id"],$arr);
				}
			}
			
			function remove_node_tree($id){
				global $db_path;
				$ids = array();
				list_child_ids($id,$ids);
				
				$db = new SQLite3($db_path);
				$stm = $db->prepare("delete from countrycity where c_id in (".implode(",",$ids).")");
				$stmt->execute();
				$stmt->close();	
				$db->close();			
			}