سیستم ثبت نام درختی

[madisline]

سلام

دوستان من میخوام یک سیستم ثبت نام کاربران بسازم. نحوه ی کار این سیستم هم به این صورت است که هر کاربر توسط معرف خود در سیستم عضو میشود. نحوه ی سیستم میخوام به گونه ایی باشه که کاربران به صورت درختی و دودویی در سیستم ثبت شوند. هر کاربر دو شاخه به نام های شاخه راست و شاخه چپ میتونه داشته باشه که زیرمجموعه هایی که معرفی میکنه در این شاخه ها قرار میگیرند. همانند سیستم های نتورک مارکتینگ.
سوال من اینه که از چه روشی برای اینکار استفاده کنم که بتونم در آینده نمودار درختی زیرمجموعه های یک عضو رو نمایش بدم. اینکارو میخوام با php و mysql انجام بدم. خودم هم با php برنامه نویسی میکنم در سطح متوسط.
خوشحال میشم که اگه ممکنه مقاله یا نمونه کدی رو در این رابطه بهم معرفی کنید.
​

 

[shirani]

شما باید یک چیزی بذاری مثل رادیو باتم که انتخاب کنه فردی که ثبت نام میکنه و بعد یک if که اگه مثلاً راست پر بود فقط چپ نشون بده و ...

 

[madisline]

شما باید یک چیزی بذاری مثل رادیو باتم که انتخاب کنه فردی که ثبت نام میکنه و بعد یک if که اگه مثلاً راست پر بود فقط چپ نشون بده و ...

ممنون از جوابت. ببین مشکل بزرگتر از این حرفهاست. بذار بیشتر توضیح بدم.
در این سیستم شخص ثبت نام کننده بایستی نام کاربری معرف خودش رو وارد کنه. سپس سیستم بررسی میکنه که مثلا اگه سمت راست معرف خالی بود اونو در سمت راست بذاره و یا اگر هم پر بود بیاد و سمت چپ بذاره. با این بخش مشکلی ندارم.
مسئله اینکه که هر کاربر بایستی در بخش کاربریش بتونه نمودار زیرمجموعه هاش رو تا مثلا 5 مرحله پایینی ببینه. بعد اگه مثلا خواست زیرمجموعه هایش رو که پایین از مرحله پنجم هستند ببینه کافیه که نام اون زیرمجموعش رو جستجو کنه تا بتونه 5 مرحله از زیرمجموعه های اون عضو رو ببینه و به همین ترتیب. حالا من میخوام بدونم اطلاعات و دیتابیس رو چکونه باید بسازم که بتونم این ساختار دودویی رو شبیه سازی کنم. اینکه فلان کاربر زیرمجموعه ی چه کسانی هست و زیرمجموعه هاش چه کسانی هستند.
​

 

[shirani]

من هم خودم از اینجا به بعدش مشکل داشتم ولش کردم

 

[madisline]

ممنون. کسی دیگه ایی نیست که تو این زمینه تجربه داشته باشه؟

 

[mosi20]

سلام
من یه بار یه سیستم میخواستم بنویسم حالا یادم نیست کدهاش را چیکار کردم
ولی طرز کار را تا حدی یادمه
یه تیبل باید بزاری که داخلش زیر مجموعه های هر عضوی را بریزی
چجوری بریزی؟
اول اینکه حتما باید معلوم کنی این زیر مجموعه کلا در طرف چپ فرد اصلی قرار داره یا در طرف راست هستش
دوم باید بگی این فرد نسبت به فرد بالاییش سمت راست هست یا چپ
سوم برای هر جایگاهی در زیر مجموعه ها باید شماره گذاری داشته باشی یعنی برای فرد اول از ردیف ۵ زیر مجموعه های هر فردی باید یه عدد به عنوان شماره ی جایگاهش که کلا برای هر فردی در اینجایگاه ثابت است تولید کنی و ذخیره کنی
برای نمای هم از جاوا اسکریپت کمک گرفته بودم و اول یه چارت کامل تا ۵ زیر مجموعه را ترسیم کرده بودم و جایگاه ها را خالی گذاشته بودم.
سپس با جاوا اسکریپت با توجه به اینکه هر جایگاه یه شماره ی مشخص داشته جایگاه ها را پر میکردم.
خیلی سخت هستش ولی من تا اینجاش را انجام دادم
که طرف زنگ زد و کنسل کرد.
۱ ماه کامل روی این چند خط که اینجا نوشتم فکر کردم پس حداقل ۱۰ دقیقه وقت بزار و بخون و کامل متوجه بشو که چی گفتم.

 

[zoghal]

شما برای ایجاد یک درخت اختیاج به این فیلد ها دارید

1- id
2- parentid
3-flag
4.name
5.....

حالا نود اول شامل این مقادر هست

node 1 [ id =1 , parentid = 0 , flag = 0 , name = saleh ]

مابقیه نود ها به این صورت باید ایتفاده بشند

لول اول درخت
node2 [ id = 2 , parentid = 1 , flag = 1 , name = ali ]
node2 [ id = 3 , parentid = 1 , flag = 2 , name = amin ]

لول دوم درخت به صورتی که به ترتیب ورود فرزند ها
node2 [ id = 4 , parentid = 3 , flag = 2 , name = mamad ]
node2 [ id = 5 , parentid = 2 , flag = 1 , name = hamid ]
node2 [ id = 6 , parentid = 2 , flag = 2 , name = reza ]
node2 [ id = 7 , parentid = 3 , flag = 1 , name = nima ]


دقیقا این رو بتونی همینطور که واست توضیح دادم رو کاغظ پیداه سازی کنی کتمل میفهمی چگونه هست

 

[zoghal]

دوباره سلام
بعد از این که این مورد رو نوشتم واست یک مقدار فکر کردم دیدم در آخر نیاز داری که این درخت رو پیمایش کنی
و همین که اسم پیمایش اومد یاد postfix , infix افتادم

و راه درست و اصولی همین هست که میگه

هر نود یا گره باید دارای این خصوصیات حتما باشه باشد.
1- شناسه اختصاصی
2- شناسه نود پدر یا گره والد
3- در صورت وجود فرزند در سمت چپ شناسه اختصاصی اون رو باید داشته باشه
4- در صورت وجود فرزند در سمت راست شناسه اختصاصی اون رو باید داشته باشه


خوب تقریبا روش بالا رو در پیش داره منتها با خصوصیاتی که هر نود داره به راحتی می تونی از نود پدر به فرزندان و برعکس و استفاده از روش های پیمایش درخت دودویی مثل infix و postfix و prefix هستید

 

[madisline]

با تشکر از mosi20 و zoghal عزیز که زحمت کشیدند و بنده رو راهنمایی کردند.
با توجه به چیزهایی که شما دوستان گفتید و همچین یکسری اطلاعاتی که از جاهای دیگه کسب کردم تقریبا متوجه شدم که ساختار رو باید به چه صورت پیاده سازی کنم.

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

اگه اشتباه نکنم برای اینکار باید 100 کوئری به بانک بفرستیم. به نظر شما این مقدار درخواست ایجاد مشکل نمیکنه؟ و اگه اینطوری باشه راه حل دیگه ایی برای اینکار هست؟

ممنون از توجه شما

 

[zoghal]

خیر اینجاست که هنر کوئری زدن مورد نیاز هست فقط با یک کوئری میتونید انجام بدید

select * from users where user_parent in (select user_id from users)

 

[mosi20]

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

 

[madisline]

zoghal عزیز میشه در مورد این کوئری بیشتر توضیح بدی؟ ممنون میشم

mosi20 عزیز من نمیخوام که همه ی شاخه رو به کاربر نشون بدم و فقط تا 5 مرحله‌ی پایینش رو نشون میدم. این موردی که من گفتم ممکنه در حالت های دیگه ایی اتفاق بیافته.
مثلا فرض کن در همون سطح صدمی که گفتم، یک جایگاه ثبت میشه. حالا سیستم باید به مجموع تمامی جایگاه‌های بالایی که با این جایگاه در ارتباط هستند یک واحد اضافه کنه تا اونها هم بفهمند که چه تعداد جایگاه زیرشون ثبت شده.
روشش رو تقریبا متوجه شدم. به اینصورت که به ترتیب از همون جایگاهی که به تازگی ثبت شده شروع میکنیم و کد والدش رو میگیرم. سپس به والد که رسیدیم کد والد بعدی رو میگیریم و به همین ترتیب تا برسیم به سرشاخه اصلی.
البته تا اونجایی که به ذهنم رسید برای اینکه تعداد زیرمجموعه های هر عضو رو بدست بیارم از 2 روش میتونم استفاده کنم.
اولیش همینی که الان گفتم. یعنی موقع ثبت جایگاه جدید، به تمامی جایگاه های مرتبط بک واحد اضافه کنم.
دومین روش هم اینه که موقع نمایش تعداد زیرمجموعه ها، این عملیات رو انجام بدم. ولی فکر کنم روش اول بهتر باشه چون حداقلش اینه که یکبار انجام میشه.
ولی باز هم تعداد کوئری ها زیاد میشه.

 

[zoghal]

خیلی ساده هست

select * from users where user_parent in (select user_id from users)

اگر تیبل شما با نام users همانند ساختاری که گفتم ایجاد کنید
هر رکورد شامل دو فیلد هست به که یکی کد کاربر یا همون user_id ودیگری کد والد رو نگه میداره
با این کوئری شما تمامی نود ها رو می تونید داشته باشید
کوئری رو ال اعملا اجرا نکنی نمی تونی به خوبی درک کنی

این روش بار ها تست شده
و جواب گو بوده

 

[madisline]

من این کوئری رو تست کردم که به شما اینو گفتم.
اسم جدول من "tree" هست و فیلدهاش یکی "title" هست که همون شناسه ی منحصربفرد هر کاربر هست و فیلد "parent" که شناسه ی والد رو نگه میداره.
پس با این حساب کوئری اینطوری میشه:

 select * from tree where parent in (select title from tree)

اینو که اجرا کردم باعث شد همه‌ی رکوردها رو برگردونه. اما بعدش فهمیدم باید به جای title شناسه ی کاربر مورد نظر رو بذارم پس اینطوری شد:

 select * from tree where parent in (select 'ali' from tree)

این کوئری هم فقط 2 رکورد برگشت داد. همونهایی که مستقیم زیر دست 'ali' بودند. اما فکر نکنم این همونی باشه که من گفته بودم.

اگه اشتباه نکنم این کوئری باید معادل این کوئری باشه:

select * form tree where parent = 'ali'

نمیدونم. شاید هم بد متوجه شده باشم. لطفا بیشتر توضیح بدید. ممنون
​

 

[zoghal]

دو حالت وجود داره
1. شما میخواهید زیر مجموعه یک نود رو در بیاری که خوب یکی میشه فرزند چپ و راست

select * form tree where parent = 'ali'

2 حالت دیگر این هست که تمامی زیر مجموعه های یک نود رو میخواهی.
البته تو این حالت استفاده از اسم برای شناسه یک نود رد میشه شما بهتره از یک فیلد auto increment استفاده کنید

چرا؟ به این دلیل هر فرزند شناسش از والدش بزرگتر میشه و این مورد نیاز ما هست
پس کوئری میشه این

select * from users where user_id > user_parent and user_parent in (select user_id from users)

 

[madisline]

شما مطمئنی که این روش کار میکنه؟ منظورم اینه خودت قبلا تستش کردی؟
من همین کاری که گفتی رو انجام دادم. در فیلد والد به جای اسم از کد شناسش استفاده کردم. فرض کن کوئریم اینجوری شد:

select * from users where user_id > 5 and user_parent in (select user_id from users)

که اینجا 5 شناسه ی یکی از کاربرهاست.
ولی این کد تمامی شناسه هایی رو که بزرگتر از 5 بودند برگشت داد. فکر نکنم اینحوری بشه.

 

[zoghal]

خوب مگر غیر از این هم باید باشد
وقتی والد کد 5 میگیره
فرزند کدی بزرگتر از 5 خواهد گرفت!

 

[madisline]

خوب مگر غیر از این هم باید باشد
وقتی والد کد 5 میگیره
فرزند کدی بزرگتر از 5 خواهد گرفت!

من فکر میکنم شما درست متوجه عملکرد سیستم نشدید.
در زیر یک مدل از نحوه‌ی قرار گیری زیرمجموعه ها رو براتون گذاشتم. حتما ببینید.
مثلا در این تصویر ما کاربر شماره‌ی 4 را داریم. اگر بخواهیم طبق چیزی که شما گفتی عمل کنیم پس باید کاربرهایی که شناسشون بزرگتر از 4 باشه زیرمجموعه های کاربر 4 باشند ولی در حالی که چنین نیست.
درضمن این حالتی که من شکلش رو کشیدم یکی از ساده ترین حالت های ممکن هستش.

​

 

[zoghal]

دوست عزیز اولا این ساختار اسمش هست btree یا binary tree یا ساختار دودویی
تو شکلی که شما نشون دادی فرض کن ما کل درخت رو بخواهیم میتونی از کوئری اول استفاده کنید

select * from users where user_parent in (select user_id from users)

حالا میخوای زیر مجموعه 2 رو بدست بیاری دقت کن تمامی زیر مجموعه 2 شماره ای که دادی از خودش بزرگتر هست
پس داریم

select * from users where user_id > 2 and user_parent in (select user_id from users)

اگر باز مشکل داشتی برو www.phpclasses.org و کلمه Binary Tree جستجو کن عنواع کلاس های آماده و روش های مختلف رو پیدا می کنید

 

[madisline]

ممنون. ولی من هم که خدمتت عرض کردم که این روشی که شما گفتی نمیتونه درست باشه.
مثلاش رو هم که گفتم. با این حساب با توجه به همین شکل و روشی که شما میگید پس باید کاربرهای 6 و 7 هم زیرمجموعه های کاربر 4 باشند که این درست نیست.
به هر حال ممنون از شما و بقیه دوستانی که راهنمایی کردند.

بالاخره پس از مدتی جستجو تونستم یک مقاله‌ی خوب در این زمینه پیدا کنم که از یک الگوریتم چرخشی برای ساختارهای دودویی استفاده میکنه. اگه جواب داد اینجا میگم بهتون تا اگه کس دیگه ایی هم خواست استفاده کنه.