Bài giảng "Cấu trúc dữ liệu - Chương 7: Cây" trình bày các nội dung: Cấu trúc cây, cấu trúc cây nhị phân, cấu trúc cây nhị phân tìm kiếm, cấu trúc cây nhị phân tìm kiếm cân bằng. Mời các bạn cùng tham khảo nội dung chi tiết.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu - Chương 7: Cây
- Chương 7: CÂY (Tree)
- Nội dung
2
Cấu trúc cây (Tree)
Cấu trúc cây nhị phân (Binary Tree)
Cấu trúc cây nhị phân tìm kiếm (Binary Search Tree)
Cấu trúc cây nhị phân tìm kiếm cân bằng (AVL Tree)
Chương 7: Cây (Tree)
- Tree – Đinh nghi
̣ ̃a
3
Cây là một tập gồm 1 hay nhiều nút T, trong đó có một nút
đặc biệt được gọi là gốc, các nút còn lại được chia thành
những tập rời nhau T1, T2 , ... , Tn theo quan hệ phân cấp
trong đó Ti cũng là một cây
A tree is a set of one or more nodes T such that:
i. there is a specially designated node called a root
ii. The remaining nodes are partitioned into n disjointed set of nodes
T1, T2,…,Tn, each of which is a tree
Chương 7: Cây (Tree)
- Tree – Ví dụ
4
Sơ đồ tổ chức của một công ty
Công ty A
R&D Kinh doanh Taøi vuï Saûn xuaát
Noäi ñòa Quoác teá TV CD Amplier
Chaâu aâu Myõ Caùc nöôùc
Chương 7: Cây (Tree)
- Tree – Ví dụ
5
Cây thư mục
Chương 7: Cây (Tree)
- Tree – Ví dụ
6
Chương 7: Cây (Tree)
- Tree – Ví dụ
̉
Có phai là cây không
Chương 7: Cây (Tree)
- Tree – Ví dụ
8
̉
Có phai là cây không
Không vì trong cấu trúc cây không tồn tại chu trình
Chương 7: Cây (Tree)
- Tree Một số khái niệm cơ bản
9
Bậc của một nút (Degree of a Node of a Tree):
Là số cây con của nút đó. Nếu bâc cua môt nu
̣ ̉ ̣ ́t bằng 0 thì
̣ ̀ nút lá (leaf node)
nút đó goi la
Bậc của một cây (Degree of a Tree):
Là bậc lớn nhất của các nút trong cây. Cây có bậc n thì gọi là
cây nphân
Nút gốc (Root node): Cạnh J gốc
Là nút không có nút cha nút
Z A
Nút lá (Leaf node):
Là nút có bậc bằng 0 B R D
Q K A F L Lá
Chương 7: Cây (Tree)
- Tree Một số khái niệm cơ bản t3
10 t1 t2
Nút nhánh:
Là nút có bậc khác 0 và không phải là gốc
Mức của một nút (Level of a Node):
Mức (T0) = 0, với T0 là gốc
Gọi T1, T2, T3, ... , Tn là các cây con của T0:
Mức(T1) = Mức(T2) = ... = Mức(Tn) = Mức(T0) + 1
We define the level of the node by taking the level of the root node as 0, and
incrementing it by 1 as we move from the root towards the subtrees.
Chiều cao của cây (độ sâu) (Height – Depth of a Tree):
Là mức cao nhất của nút + 1 (mức cao nhất của 1 nút có trong
cây)
Chương 7: Cây (Tree)
- Tree Một số khái niệm cơ bản
11
Nút trước, nút sau của 1 nút
Nút T được gọi là nút trước của 1 nút (ancestor’s node)
của nút S nếu cây con có gốc là T chứa cây con có gốc là
S. Khi đó S được gọi là nút sau của nút T (descendant’s
node)
Chiều dài đường đi của 1 nút
Chiều dài đường đi của 1 nút là số đỉnh (số nút) tính từ nút
gốc để đi đến nút đó.
Chiều dài đường đi của nút gốc luôn =1, chiều dài đường
đi tới 1 nút bằng chiều dài đường đi tới nút cha của nó + 1
Chương 7: Cây (Tree)
- Tree Một số khái niệm cơ bản
12
Chiều dài đường đi của 1 cây
Chiều dài đường đi của 1 cây (path’s length of the tree) là
tổng tất cả các chiều dài đường đi của tất cả các nút trên
cây (chiều dài đường đi trong internal path’s length).
Tính chiều dài đường đi ngoài (external path’s length)
bằng cách mở rộng tất cả các nút của cây sao cho các nút
của cây có cùng bậc (thêm vào các nút giả) với bậc của
cây.
Rừng.
Rừng (forest) là tập hợp các cây.
Khi cây mất gốc rừng
Chương 7: Cây (Tree)
- Tree – Ví dụ
- Leaf node?
- Degree of a Nodes of a Tree?
- Degree of a Tree?
- Level of a Node?
- Height – Depth of a Tree?
Chương 7: Cây (Tree)
- Trắc nghiệm
14
The depth of a tree is the _______ of a tree
a) number of nodes on the tree
b) number of levels of a tree
c) number of branches
d) level
Give the binary tree with root A. The root has left child B and
right child C. B has left child D and right child E. There are
no other nodes in the tree. The height of the tree is _______.
a) 0
b) 3
c) 1
d) 2
Chương 7: Cây (Tree)
- Một số khái niệm cơ bản
15
Độ dài đường đi từ gốc đến nút x:
Px = số nhánh cần đi qua kể từ gốc đến x
Độ dài đường đi tổng của cây:
PT PX
X T
trong đó Px là độ dài đường đi từ gốc đến X
Độ dài đường đi trung bình: PI = PT/n (n là số nút trên cây T)
Rừng cây: là tập hợp nhiều cây trong đó thứ tự các cây là
quan trọng
Chương 7: Cây (Tree)
- Tree – Ví dụ
16
Chương 7: Cây (Tree)
- Depthfirst Search
17
1.3. Biểu diễn cây
Dùng đồ thị, Dùng giản đồ tập hợp, Sử dụng dạng phân cấp chỉ
số
BIỂU DIỄN CÂY TRONG BỘ NHỚ MÁY TÍNH
Để biểu diễn cây trong bộ nhớ máy tính dùng danh sách liên kết.
Để biểu diễn cây Nphân dùng danh sách có N mối liên kết để
quản lý N địa chỉ nút con.
Cấu trúc dữ liệu của cây Nphân tương tự cấu trúc dữ liệu đa liên
kết.
const int N = 100;
typedef struct NTNode
{ T Key;
NTNode * SubNode[N];
}NTOneNode;
typedef struct NTOneNode * NTType;
Để quản lý cây, chỉ cần quản lý địa chỉ nút gốc NTType NTree;
Chương 7: Cây (Tree)
- Depthfirst Search
18
2.2. Biểu diễn và các thao tác
Để biểu diễn cây nhị phân trong bộ nhớ máy tính dùng danh sách có 2
mối liên kết để quản lý địa chỉ 2 nút con (cây con trái và cây con phải).
Như vậy cấu trúc dữ liệu của cây nhị phân tương tự cấu trúc dữ liệu
của danh sách liên kết đôi nhưng cách thức liên kết khác:
struct TNode
{
int Info;
struct TNode *pL,*pR;
};
Để quản lý cây nhị phân chỉ cần quản lý địa chỉ nút gốc
typedef TNode *TREE;
TREE T;
Chương 7: Cây (Tree)
- Nội dung
19
Cấu trúc cây (Tree)
Cấu trúc cây nhị phân (Binary Tree)
Cấu trúc cây nhị phân tìm kiếm (Binary Search Tree)
Cấu trúc cây nhị phân tìm kiếm cân bằng (AVL Tree)
Chương 7: Cây (Tree)
- Binary Tree – Đinh nghi
̣ ̃a
20
Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con (cây có
bậc là 2)
Chương 7: Cây (Tree)
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
