Giải thuật: Cấu trúc cây

CẤU TRÚC CÂY

I. ÐỊNH NGHĨA VÀ CÁC KHÁI NIỆM CƠ BẢN
1. Ðịnh nghĩa :
Cây (Trees) là một tập hợp hữu hạn các phần tử gọi là nút cây (Node), trong đó có một nút đặc biệt gọi là nút gốc (Root). Trên tập hợp các nút này có một quan hệ phân cấp gọi là quan hệ "cha - con".
Một nút có thể có kiểu bất ký, ta thường biểu diễn nút bằng tên nút. Tên nút có thể là một ký tự, một số hay một chuỗi và có thể được ghi trong một vòng tròn. Ta quy ước biểu diễn cây như sau: Ta viết nút cha ở dòng trên, các nút con ở dòng dưới và quan hệ "cha-con" được biểu diễn bằng một đoạn thẳng nối liền 2 nút.
Ví dụ :


Ngoài ra ta có thể định nghĩa cây một cách đệ qui như sau :
Một nút (đơn độc) là một cây và nút đó cũng là nút gốc của cây.
Nếu ta có n là một nút và T1, T2, ..., Tk là các cây với n1, n2,..., nk lần lượt là các nút gốc của các cây con thì ta có thể xây dựng một cây mới bằng cách cho n trở thành cha của các nút n1, n2,..., nk; Nghĩa là trên cây mới này n là nút gốc còn các cây T1, T2, ..., Tk là các cây con của nút n.
Ðể tiện việc quản lý, người ta cho phép tồn tại một cây không có nút nào, mà ta gọi là cây rỗng (Null tree).


2. Các khái niệm cơ bản :
Một nút đơn độc cũng là một cây.
Tập hợp rỗng cũng là một cây mà ta gọi là cây rỗng.
Mức của một nút :
+ Nút gốc : Mức 0.
+ Các nút cách nút gốc i cạnh được gọi là nút ở mức i.
Ví dụ:

Cha - con: Nút A là nút cha của nút B khi nút A ở mức i và nút B ở mức i+1. Ðồng thời có một cạnh nối giữa cặp nút A và B (ta còn gọi B là con của A).
Cha - ông (con - cháu)/ tiền bối - hậu duệ: Nếu có một đường nối từ nút A đến nút B và mức của nút A < mức của nút B thì ta nói A là cha ông (tiền bối) của B và B gọi là con cháu (hậu duệ) của A.
Anh em ruột: Các nút con của cùng một nút cha được gọi là các nút anh em ruột.
Ðường đi: Cho một dãy các nút n1, n2,..., nk sao cho ni là nút cha của ni+1 thì ta nói n1 ( n2 ( ...( nk là một đường đi từ nút n1 ( nk. Ðộ dài của đường đi bằng số nút trên đường đi trừ 1 hay bằng số cạnh trên đường đi.
Nút gốc (Root): Là nút không có nút cha.
Nút lá (leaf): Là nút không có nút con.
Chiều cao của một nút: Là độ dài đường đi từ nút đó đến nút lá xa nhất.
Ðộ sâu của một nút (mức của một nút): Là chiều dài đường đi từ nút gốc đến nút đó.
Chiều cao của một cây: Là chiều cao của nút gốc.
Bậc của một nút: Là số nút con của nút đó.
Bậc của một cây: Là bậc cao nhất của các nút trong cây.
+ Cây có bậc n được gọi là cây n - phân.
+ Rừng là một tập hợp hữu hạn các cây phân biệt.
Nếu ta phân biệt thứ tự các nút con của một cây thì ta gọi cây đó là cây có thứ tự. Ngược lại là cây không có thứ tự.
Thứ tự của các nút trong một cây có thứ tự được quy ước từ trái sang phải và từ trên xuống dưới.
Nếu A và B là 2 nút anh em ruột và A ở bên trái của B thì các nút con cháu của A là nút bên trái tất cả các nút con cháu của B.
Ðể xác định nút trái (phải) của một nút n, ta vẽ một đường đi từ nút gốc đến nút n. Nút nào nằm bên trái của đường đi thì sẽ là nút trái của nút đó, nút nào nằm bên phải của đường đi thì sẽ là nút phải của nút đó.
Ví dụ:


Thứ tự duyệt cây:
Duyệt cây là một quy tắc xử lý lần lượt tất cả các nút của một cây mà ở đó mỗi