Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 1 trên tổng số 1 kết quả

Đề tài: Duyệt cây đa cấp trên MS Sql server

  1. #1
    Ngày gia nhập
    09 2006
    Bài viết
    62

    Lightbulb Duyệt cây đa cấp trên MS Sql server

    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 Name Data Type Size Allow Null Description
    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ệu

    Scrip 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ông thoả đ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ường hợ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 NodeName hay 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ột WoodenLeg đượ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
    Node 1 "1"+"2" "12" - "1" là giá trị của cột WoodenLeg của node cha của Node 1 (Root 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 Tree

    Values (1, Root Node, Null, 1);

    § Khi thêm node thứ cấp:

    Insert Into Tree

    Values(2, Node 1, 1, Null); -- Node 1 là node con của Root Node

    Update Tree

    Set Tree.WoodenLeg = Cast(T.WoodenLeg As varchar(100)) + Cast(Tree.NodeID As varchar(100))

    From Tree, Tree T

    Where (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ảng

    Update Tree

    Set WoodenLeg = Null;

    -- Gán giá trị column WoodenLeg cho node gốc

    Update Tree

    Set WoodenLeg = NodeID

    Where ParentID Is Null;

    -- Node có ParentID = Null là node gốc

    /* Gán giá trị cột WoodenLeg cho các node thứ cấp

    Ứng với mỗi lần lặp ta tính được giá trị cho các node ở cấp tương ứng

    Ví dụ ở lần lặp đầu tiên, ta tính được giá trị cho các node cấp 1, bao

    gồm: Node 1, Node 2, Node 3, Node 4.

    */

    While (1=1) -- Điều kiện thoát được thể hiện bên trong vòng lặp

    Begin

    Update Tree

    Set Tree.WoodenLeg =Cast(T.WoodenLeg As varchar(100))+ Cast(Tree.NodeID As varchar(100))

    From Tree, Tree T

    Where (Tree.ParentID = T.NodeID) And

    (Tree.WoodenLeg Is Null);

    If (@@RowCount = 0)

    -- Đã tính xong giá trị WoodenLeg cho

    -- tất cả các node trong bảng Tree

    Break;

    End

    Sau khi tính toán xong giá trị cho cột WoodenLeg, chúng ta viết script để hiển thị danh sách theo thứ tự duyệt cây như được yêu cầu:

    Select NodeName, WoodenLeg

    From Tree

    Order By WoodenLeg;

    Và kết quả thu được như mô tả trong hình 4. Sở dĩ chúng ta có được kết quả này là do cột WoodenLeg có kiểu dữ liệu là varchar nên khi so sánh các giá trị để xác định trình tự hiển thị nó sẽ tiến hành so sánh theo kiểu chuỗi ký tự. Chuỗi "126" của Node A sẽ nhỏ hơn chuỗi "13" của node 2 nên Node A sẽ đứng trước Node 2 trong danh sách.

    NodeName WoodenLeg
    Root Node 1
    Node 1 12
    Node A 126
    Node B 127
    Node 2 13
    Node E 1310
    Node C 138
    Node D 139
    Node 3 14
    Node 4 15
    Node F 1511
    Node X 151113
    Node Y 151114
    Node Z 151115
    Node G 1512
    Hình 4: Kết quả thu được từ phát biểu Select
    Như vậy thứ tự duyệt cây thông qua phát biểu Select ở trên gần giống với thứ tự duyệt cây mong đợi. Nó chỉ khác nhau khi đi đến các node con của Node 2.

    Vấn đề chúng ta đang gặp phải là do Node 2 có ba node con là Node C, Node D, Node E. Trong đó, Node C, Node D lần lượt có NodeID là 8 và 9, tức chỉ có một ký số, trong khi Node E có NodeID là 10, tức hai ký số. Vì thế, giá trị cột WoodenLeg của ba node con trên lần lượt là: "138", "139", "1310". Như đã nói ở trên, kiểu so sánh ở cột WoodenLeg là so sánh chuỗi nên chuỗi "1310" nhỏ hơn chuỗi "138" cũng như "139". Và đó là nguyên nhân dẫn đến thứ tự duyệt cây không đạt như mong đợi.

    Nếu ta lần lượt thay thế chuỗi ký số "8" và "9" (NodeID của hai Node C & D) thành 08" và "09" trong biểu thức tính giá trị WoodenLeg thì các chuỗi kết quả sẽ là: "1308", "1309", "1310". Và thứ tự duyệt cây cũng thay đổi theo hướng ta mong đợi. Điều đó cũng có nghĩa là mọi vấn đề đã được giải quyết.

    Như vậy, nếu chúng ta xác định được số ký số tối đa được dùng để lưu giá trị NodeID của bảng Tree thì chúng ta luôn kiểm soát được tình hình và kết quả thu được luôn luôn chính xác. Giả sử cây đa cấp chúng ta đang xét ở trên có không quá 1000 node, điều đó có nghĩa là số ký số được dùng tối đa cho NodeID là 3 (từ 1 đến 999). Khi đó, biểu thức tính toán cột WoodenLeg được chỉnh lại như sau (áp dụng cho cả hai trường hợp):

    ....

    Set Tree.WoodenLeg =Cast(T.WoodenLeg As varchar(100))+ SubString(00 + Cast(Tree.NodeID As varchar(100)), Len(Tree.NodeID), 3)

    ....
    Các bạn có thể thay thế cột WoodenLeg bằng biểu thức tính toán để phục vụ cho việc thể hiện thứ tự duyệt cây. Tuy nhiên, server sẽ phải làm nhiều việc hơn vì ở mỗi lần thực thi, server phải tính lại giá trị của biểu thức.

    Bài toán duyệt cây là một bài toán tổng quát mà từ đó chúng ta có thể nhân rộng để áp dụng cho rất nhiều bài toán thực tế khác. Tôi hi vọng bài viết này ít nhiều mang lại một chút kinh nghiệm bổ ích cho các bạn

    Theo Quản Trị Mạng
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    Đã được chỉnh sửa lần cuối bởi vie_kainznz : 09-09-2006 lúc 10:18 AM.
    Click here for more Info of Cviet-Translator-Group

    ! be thankful for small blessings...

Các đề tài tương tự

  1. Trả lời: 0
    Bài viết cuối: 31-08-2013, 01:18 PM
  2. Cách thức duyệt tiền tự trên cây khi duyệt từ con trái nhất rồi sang anh em ruột phải?
    Gửi bởi tyrant trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 14-09-2011, 10:53 AM
  3. MS SQL với C# Backup trên Server A và Restore ở Server B cùng cấu trúc CSDL như thế nào?
    Gửi bởi snake_programmer trong diễn đàn Thắc mắc Microsoft SQL Server & Microsoft Access
    Trả lời: 1
    Bài viết cuối: 23-08-2011, 09:19 AM
  4. ADO.NET Thứ tự của control( textbox) được duyệt khi chạy đệ quy duyệt các control trên form
    Gửi bởi caheoxanh trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 3
    Bài viết cuối: 17-06-2011, 09:12 PM
  5. Cài SQL Server trên Windows Server 2003?
    Gửi bởi nth4 trong diễn đàn Thắc mắc đại cương Database & Reporting
    Trả lời: 5
    Bài viết cuối: 23-02-2008, 12:57 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn