‫بدست آوردن برگهای یک درخت توسط Recursive CTE

سه شنبه 17 اردیبهشت 1392

‫بدست آوردن برگهای یک درخت توسط Recursive CTE <br/> امروز در یک تالار سوالی مطرح شد با این عنوان "چگونه می‌توانم گره‌های برگ یک شاخه را بدست بیاورم". خب راه حلی که فورا به ذهنم رسید استفاده از یک query بازگشتی (recursive) بود.

امروز در یک تالار سوالی مطرح شد با این عنوان "چگونه می‌توانم گره‌های برگ یک شاخه را بدست بیاورم". خب راه حلی که فورا به ذهنم رسید استفاده از یک query بازگشتی (recursive) بود.
به  ساختار سلسله مراتبی زیر توجه بفرمایید:

گره هایی که با رنگ سبز علامت گذاری شده اند را گره‌های برگ می‌نامیم چون که آن گره‌ها بدون زیر شاخه هستند.
فرض کنید از ما خواسته شده است با داشتن گره A تمام برگهای این شاخه را بدست بیاوریم.
دو مرحله را باید طی کنیم ابتدا تمام گره هایی که زیر شاخه گره A هستند را باید بدست آورد سپس توسط یک گزاره گره‌های برگ را فیلتر کنیم.

در واقع گره هایی برگ هستند که پدر هیچ گره‌ی دیگری نباشند. 

declare @t table
(id char(1) primary key,
parent char(1));

insert @t values 
('A',null),                                   --Level 1
('B', 'A'), ('C', 'A'),                       --Level 2
('D', 'B'), ('E', 'B'),('R','B'), ('F', 'C'), --Level 3
('G', 'D'),  --Level 4
('H', 'G'), ('I', 'G');                       --Level 5

;with cte as
(
select id, rnk=0 from @t
where parent = 'A'
 
union all
 
select t.id, rnk+1
from cte join @t t
on cte.id = t.parent
)
select *
  from cte
 where not exists
       (select *
          from @t
         where parent = cte.id);


و حالا به درخت زیر توجه بفرمایید:

هدف پیدا کردن برگ هایی از شاخه مورد نظر است که در پایین‌ترین سطح قرار گرفته باشند. برای این منظور از همان query بازگشتی استفاده کرده و با کمک تابع dense_ranke گره‌های مورد نظر را بدست میاوریم.
;with cte as
(
select id, rnk=0 from @t
where parent = 'A'

union all

select t.id, rnk+1
from cte join @t t
on cte.id = t.parent
)
select *
from
(
   select *, dense_rank() over(order by rnk desc) rk
     from cte
)t
where rk = 1


ایمان مدائنی

نویسنده 1299 مقاله در برنامه نویسان

کاربرانی که از نویسنده این مقاله تشکر کرده اند

تاکنون هیچ کاربری از این پست تشکر نکرده است

در صورتی که در رابطه با این مقاله سوالی دارید، در تاپیک های انجمن مطرح کنید