13
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 25
Các khái niệm và thuật ngữ cơ bản
Các thuật ngữ liên quan
! Mức h của cây đầy đủ bậc d có d
h
nút
! VD. mức h=2 của cây bậc 3 có bao nhiêu nút ?
! h mức đầu tiên của cây đầy đủ bậc d có số nút
là:
! 1 + d + d
2
+ d
3
+ … + d
h-1
= (d
h
-1)/(d –1)
! 3 mức đầu tiên của cây bậc 3 có bao nhiêu nút ?
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 26
Tổng quan về cây nhị phân
! Định nghĩa
! Cách thức lưu trữ cây
! Các phương pháp duyệt cây
14
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 27
Tổng quan về cây nhị phân
Định nghĩa
! Cây nhị phân là cây có bậc = 2
*

16
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 31
Tổng quan về cây nhị phân
Cách thức lưu trữ cây, sử dụng mảng
*
0
/
a
b
c
d
-1-1d6
-1-1c5
-1-1b4
-1-1a3
65/2
43-1
21*0
Con phảiCon tráiNút#
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 32
Tổng quan về cây nhị phân
Cách thức lưu trữ cây, sử dụng mảng
// Định nghĩa các cấu trúc dữ liệu
typedef struct tagBT_NODE {
intData;
intLeft;// chỉ số nút con trái
intRight;// chỉ số nút con phải
} BT_NODE;// binary tree node
BT_NODE tree[N];// cây nhị phân có N nút
17