Giải thuật và lập trình - C: II. Kiểu dữ liệu trừu tượng cây


Đăng ký nhận thông báo về những video mới nhất

II. KIỂU DỮ LIỆU TRỪU TƯỢNG CÂY

Để hoàn tất định nghĩa kiểu dữ liệu trừu tượng cây, cũng như đối với các kiểu dữ liệu trừu tượng khác, ta phải định nghĩa các phép toán trừu tượng cơ bản trên cây, các phép toán này được xem là các phép toán "nguyên thủy" để ta thiết kế các giải thuật sau này.

Các phép toán trên cây

  ► Hàm PARENT(n,T) cho nút cha của nút n trên cây T, nếu n là nút gốc thì hàm cho giá trị NULL. Trong cài đặt cụ thể thì NULL là một giá trị nào đó do ta chọn, nó phụ thuộc vào cấu trúc dữ liệu mà ta dùng để cài đặt cây.

  ► Hàm LEFTMOST_CHILD(n,T) cho nút con trái nhất của nút n trên cây T, nếu n là lá thì hàm cho giá trị NULL.

  ► Hàm RIGHT_SIBLING(n,T) cho nút anh em ruột phải nút n trên cây T, nếu n không có anh em ruột phải thì hàm cho giá trị NULL.

  ► Hàm LABEL_NODE(n,T) cho nhãn tại nút n của cây T.

  ► Hàm ROOT(T) trả ra nút gốc của cây T. Nếu Cây T rỗng thì hàm trả về NULL.

  ► Hàm CREATEi(v,T1,T2,..,Ti),với i=0..n, thủ tục tạo cây mới có nút gốc là n được gán nhãn v và có i cây con T1,..,Ti. Nếu n= 0 thì thủ tục tạo cây mới chỉ gồm có

1 nút đơn độc là n có nhãn v. Chẳng hạn, giả sử ta có hai cây con T1 và T2, ta muốn thiết lập cây mới với nút gốc có nhãn là v thì lời gọi thủ tục sẽ là CREATE2(v,T1,T2).


Nếu bạn có điều thắc mắc, bạn hãy comment cho V1Study để được giải đáp.
Bài viết này được chia sẻ bởi LongDT. Nếu bạn muốn chia sẻ bài viết, bạn hãy Đăng ký làm thành viên!
« Prev
Next »
Copied !!!