Duyệt cây đa cấp trên MS SQL Server

Tôi là lập trình viên thường làm việc trên hệ quản trị cơ sở dữ liệu MS SQL Server. Tình cờ tôi có dịp "đụng" vấn đề duyệt cây đa cấp khá hay nên muốn chia sẻ kinh nghiệm qua bài viết này.
Nội dung trích xuất từ tài liệu:
Duyệt cây đa cấp trên MS SQL ServerDuyệt cây đa cấp trên MS SQL ServerNguồn:quantrimang.comTôi là lập trình viên thường làm việc trên hệ quản trị cơ sở dữ liệu MS SQL Server.Tình cờ tôi có dịp đụng vấn đề duyệt cây đa cấp khá hay nên muốn chia sẻ kinhnghiệm qua bài viết này. Chương trình ở đây viết bằng script Transact-SQL, đươngnhiên các bạn cũng có thể chuyển sang bất kỳ ngôn ngữ lập trình nào tùy thích.Qui tắc duyệt cây đề cập ở đây là theo chiều sâu, duyệt từ trái sang phải, thứ tự duyệtđược thể hiện bằng các chữ số bên trong các node ở hình 1.Bảng Tree lưu trữ thông tin của cây đa cấp có cấu trúc như sau: Column Data Type Size Allow Null Description Name NodeID Int No Khóa chính của bảng Tree NodeName varchar 20 No Tên node ParentID Int Yes Mã của node cha gần nhất WoodenLeg varchar 100 Yes Cột giả hỗ trợ khi sắp xếp dữ liệuScrip tạo bảng Tree như sau:Create Table Tree(NodeID int Primary Key,NodeName varchar(20) Not Null,ParentID int Null,WoodenLeg varchar(100) Null);Dữ liệu trong bảng Tree mô tả cây đa cấp ở hình 1 được thể hiện ở hình 2. Qui tắc tạo dữliệu như sau: NodeName NodeName ParentID WoodenLeg 1 Root Node Null 1 2 Node 1 1 12 3 Node 2 1 13 4 Node 3 1 14 5 Node 4 1 15 6 Node A 2 126 7 Node B 2 127 8 Node C 3 138 9 Node D 3 139 10 Node E 3 1310 11 Node F 5 1511 12 Node G 5 1512 13 Node X 11 151113 14 Node Y 11 151114 15 Node Z 11 151115 Hình 2: Dữ liệu mô tả cấu trúc cây đa cấp (Đừng quan tâm đến giá trị column WoodenLeg, tôi sẽ giải thích ở phần sau)* NodeID của node cha sẽ nhỏ hơn NodeID của node con. Đối với các node cùng cấp,NodeID của node trái sẽ nhỏ hơn NodeID của node phải.Đọc đến đây, các bạn có thể thắc mắc nếu NodeID của một cây có sẵn có giá trị khôngthoả điều kiện trên thì chúng ta có sắp xếp được hay không. Câu trả lời là hoàn toàn cóthể, vì khi đó chúng ta có thể tạo thêm một column mới với các giá trị thoả điều kiện. Vìmuốn giữ tính đơn giản cho bài viết nên cho phép tôi không nêu ra cách tính cho trườnghợp này. Nếu có bất kỳ thắc mắc gì, các bạn có thể liên hệ trực tiếp với tôi.* Đối với node gốc (Root Node) thì ParentID = Null. Các node thứ cấp còn lại sẽ cóParentID bằng NodeID của node cha gần nhất.Chúng ta dễ dàng nhận thấy, không thể sử dụng bất kỳ các cột NodeID hay NodeNamehay ParentID để hiển thị danh sách các Node theo thứ tự duyệt trên. Trong bài viết này,tôi sẽ dùng cột WoodenLeg với các giá trị đặc biệt để làm việc đó. Giá trị cộtWoodenLeg được tính như sau:* Nếu là node gốc (Root Node) thì WoodenLeg = NodeID* Các node thứ cấp còn lại thì WoodenLeg = WoodenLeg của node cha gần nhất +NodeID của node đó. (dấu + trong biểu thức trên là phép ghép/cộng chuỗi ký tự)Với cách tính trên, ta tính được giá trị cột WoodenLeg cho từng node như sau: NodeName Biểu thức Kết quả Mô tả Root node 1 1 Vì nó là node gốc - 1 là giá trị của cột WoodenLeg của node cha của Node 1 (Root Node 1 1+2 12 Node) - 2 là NodeID của Node 1 Node 2 1+3 13 - Giải thích tương tự ... Hình 3: Bảng mô tả cách tính giá trị cột WoodenLeg (Các bạn có thể xem giá trị WoodenLeg của tất cả các node ở hình 2)Script để tính giá trị cột WoodenLeg:* Trường hợp 1: Cập nhật ngay cột này khi vừa thêm 1 node vào cây§ Khi thêm node gốc:Insert Into TreeValues (1, Root Node, Null, 1);§ Khi thêm node thứ cấp:Insert Into TreeValues(2, Node 1, 1, Null); -- Node 1 là node con của Root NodeUpdate TreeSet Tree.WoodenLeg = Cast(T.WoodenLeg As varchar(100)) +Cast(Tree.NodeID As varchar(100))From Tree, Tree TWhere (Tree.ParentID = T.NodeID) And(Tree.NodeID = 2); -- 2 là NodeID của Node 1 vừa-- được thêm vào table Tree* Trường hợp 2: Cập nhật giá trị cột này khi có nhu cầu hiển thị theo thứ tự duyệt cây-- Xóa tất cả giá trị của cột WoodenLeg trong bảngUpdate TreeSet WoodenLeg = Null;-- Gán giá trị column WoodenLeg cho node gốcUpdate TreeSet WoodenLeg = NodeIDWhere ParentID Is Null;-- Node có ParentID = Null là node gốc/* G ...