Cấu trúc dữ liệu tree - Cây

Trang 1

Môn: CẤU TRÚC DỮ LIỆU

Chương 5: CÂY (TREE)

Trang 2

NỘI DUNG CHƯƠNG 5

1. Khái niệm cây – Biểu diễn cây

2. Cây nhị phân (Binary Tree)

1. Định nghĩa

2. Biểu diễn và các thao tác

3. Cây nhị phân tìm kiếm (Binary Searching Tree)

3. Cây cân bằng (Balanced Tree)

1. Định nghĩa – Cấu trúc dữ liệu

2. Các thao tác trên cây cân bằng

BÀI TẬP

Trang 3

1.Khái niệm cây – Biểu diễn cây

1.1 Định nghĩa cây

1.2 Một số khái niệm liên quan

1.2.a Bậc của 1 cây

1.2.g Chiều cao (chiều sâu) của 1 cây

1.2.h Nút trước, nút sau của 1 nút

1.2.i Nút cha, nút con của 1 nút

1.2.j Chiều dài đường đi của 1 nút

1.2.k Chiều dài đường đi của 1 cây

1.2.l Rừng

Trang 4

 Hoặc là tập hợp khác rỗng trong đó có 1 nút duy nhất làm

nút gốc (Root’s Node), các nút còn lại được phân thành

các nhóm trong đó mỗi nhóm là 1 cây con (Sub-Tree)

 Các cây con cũng có thể là tập rỗng hay khác rỗng trong đó

có 1 nút là gốc cây con

Trang 5

1.Khái niệm cây – Biểu diễn cây (tt)

1.2 Một số khái niệm liên quan

 Nút gốc (root’s tree) là nút không phải là nút gốc cây con của

bất kỳ 1 cây con nào khác trong cây (nút không làm gốc cây

con)

1.2.d Nút kết thúc

Nút kết thúc hay còn gọi nút lá (leaf’s node) là nút có bậc = 0 (nút

không có nút cây con)

Trang 6

1.2 Một số khái niệm liên quan (tt)

1.2.e Nút trung gian

 Nút trung gian hay còn gọi nút giữa (interior’s node) là nút không

phải là nút gốc và cũng không phải nút kết thúc (nút có bậc khác không và là nút gốc của cây con nào đó trong cây)

1.2.f Mức của 1 nút

 Mức của 1 nút (node’s level) bằng mức của nút gốc cây con

chứa nó +1.

 Mức của nút gốc = 1

1.2.g Chiều cao (chiều sâu) của 1 cây

 Chiều cao (chiều sâu) của 1 cây (tree’s height | tree’s depth) là

mức cao nhất của 1 nút trong cây

1.2.h 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)

Trang 7

1.2.i Nút cha, nút con của 1 nút

 Nút B được gọi là nút cha (parent’s node) của nút C nếu nút B

là nút trước của nút B và mức của nút C lớn hơn mức của B

là 1 mức Khi đó nút C được gọi là nút con (child’s node) của B

1.2.j 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

Trang 8

1.2.k 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 Chiều dài đường đi ngoài bằng tổng chiều

1.2.l Rừng.

 Rừng (forest) là tập hợp các cây

 Khi cây mất gốc  rừng

Trang 9

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 N-phâ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 N-phân tương tự cấu trúc dữ liệu đa

typedef struct NTOneNode * NTType ;

Để quản lý cây, chỉ cần quản lý địa chỉ nút gốc NTType NTree;

Trang 11

2 Cây nhị phân (Binary Tree)

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

typedef BinTOneNode * BinTType;

 Để quản lý cây nhị phân chỉ cần quản lý địa chỉ nút gốc

BinTType BinTree;

Trang 12

2.2 Biểu diễn và các thao tác (tt)

Các thao tác trên cây nhị phân bao gồm:

a Khởi tạo cây nhị phân

b Tạo mới 1 nút

c Thêm 1 nút vào cây nhị phân

d Duyệt qua các nút trên cây nhị phân

e Tính chiều cao của cây

f Tính số nút của cây

g Hủy 1 nút trên cây nhị phân

Trang 13

2.2 a Khởi tạo cây nhị phân

Khởi tạo cây nhịn phân: cho con trỏ quản lý địa chỉ nút gốc về con

Trang 14

B3: BTNode ->BinTLeft = NULL

B4: BTNode ->BinTRight = NULL

B5: BTNode -> Key = NewData

BKT: Kết thúc

Key

BTNode

Trang 15

2.2 b Tạo mới 1 nút (tt)

Cài đặt thuật toán trong C++

BinTType BinTreeCreateNode(T NewData)

{

BinTType BTnode = new BinTOneNode;

if (BTnode != NULL)

{

BTnode-> BinTLeft = NULL;

BTnode-> BinTRight = NULL;

BTnode-> Key = NewData;

}

return (BTnode);

}

Trang 16

2.2 c Thêm 1 nút vào cây nhị phân (Thêm trái nhất) – Thuật toán

Trang 17

2.2 c Thêm 1 nút vào cây nhị phân (Thêm trái nhất)

Cài đặt thuật toán bằng C++

BinTType BinTreeAddLeft (BinTType &BTTree, T NewData)

BinTType Lnode = BTTree;

while (Lnode->BinTLeft != NULL)

Trang 18

2.2 c Thêm 1 nút vào cây nhị phân (Thêm phải nhất)-Thuật toán

Trang 19

2.2 c Thêm 1 nút vào cây nhị phân (Thêm phải nhất)

Cài đặt thuật toán bằng C++

BinTType BinTreeAddRight (BinTType &BTTree, T NewData)

BinTType Rnode = BTTree;

while (Rnode->BinTRight != NULL)

Trang 20

2.2 d Duyệt qua các nút trên cây nhị phân

 Duyệt theo thứ tự nút gốc trước (Preoder): nút gốc được duyệt

trước, sau đó mới duyệt đến 2 nút con Có 2 cách:

 Duyệt nút gốc, duyệt cây con bên trái, duyệt cây con bên phải

( Root - Left - Right )

 Duyệt nút gốc, duyệt cây con bên phải, duyệt cây con bên trái

( Root - Right - Left )

 Duyệt theo thứ tự nút gốc giữa ( Inoder ): duyệt 1 trong 2 cây con

trước rồi duyệt nút gốc sau đó mới duyệt cây con còn lại Có 2

cách:

 Duyệt cây con bên trái, duyệt nút gốc, duyệt cây con bên phải

( Left - Root - Right )

 Duyệt cây con bên phải, duyệt nút gốc, duyệt cây con bên trái

( Right - Root - Left )

 Duyệt theo thứ tự nút gốc sau ( Postoder ): Nút gốc sẽ được duyệt

sau cùng sau khi duyệt 2 cây con.

 Duyệt cây con bên trái, duyệt cây con bên phải, duyệt nút

gốc( Left – Right - Root )

 Duyệt cây con bên phải, duyệt cây con bên trái, duyệt nút

gốc( Right - Left- Root )

Trang 21

2.2 d Duyệt qua các nút trên cây nhị phân – (Left-Root-Right)

Trang 22

2.2 d Duyệt qua các nút trên cây nhị phân – (Left-Root-Right)

Cài đặt thuật toán trong C++

void BinTreeLRootRTravelling(BinTType BTTree)

Trang 23

2.2 e Tính chiều cao của cây

int HTL = BinTreeHeight(BTree -> BinTLeft);

int HTR = BinTreeHeight(BTree -> BinTRight);

if (HTL > HTR)

return (HTL +1)

return (HTR +1);

}

Trang 24

2.2 f Tính số nút của cây

Tính số nút của cây tương tự tính chiều cao của cây, số nút của cây con + 1.

Dùng cách tính đệ quy số nút của cây con

int NNL = BinTreeNumNode(BTree -> BinTLeft);

int NNR = BinTreeNumNode(BTree -> BinTRight);

return (NNL + NNR +1);

}

Trang 25

2.2 g Hủy 1 nút trên cây nhị phân

 Việc hủy 1 nút trong cây có thể làm cho cây trở thành rừng

 Nếu tiến hành hủy các nút lá  không có vấn đề gì xảy ra

 Nếu hủy 1 nút không phải là nút lá cần phải chuyển các nút

con của nút cần hủy qua các nút khác rồi mới tiến hành hủy

 Nếu nút cần hủy chỉ có 1 nút gốc cây con thì chuyển nút gốc

của cây con này thành nút gốc của cây con cha của nút cần hủy

 Trong trường hợp nút cần hủy có 2 nút gốc cây con, thì phải

chuyển 2 nút gốc cây con này thành nút gốc cây con của nút khác Tuỳ từng trường hợp cụ thể mà đưa ra cách chọn phù hợp

Trang 26

2.3 Cây nhị phân tìm kiếm (Binary Searching Tree)

2.3.1 Khái niệm – Cấu trúc dữ liệu

 Cây nhị phân tìm kiếm là cây nhị phân có thành phần khóa của

mọi nút lớn hơn tất cả thành phần khóa của tất cả các nút trong cây con trái của nó và nhỏ hơn thành phần khóa của tất cả các nút trong cây con phải của nó.

 Cấu trúc dữ liệu của cây nhị phân tìm kiếm là cấu trúc dữ liệu

biểu diễn cây nhị phân nói chung.

typedef struct BSTNode

{ T Key;

BSTNode * BSTLeft;

BSTNode * BSTRight;

} BSTOneNode;

typedef BSTOneNode * BSTType;

 Để quản lý các cây nhị phân tìm kiếm chúng ta cần quản lý địa

chỉ nút gốc của cây: BSTType BSTree;

Trang 27

2.3.1 Khái niệm – Cấu trúc dữ liệu (tt)

 Khóa nhận diện của cây tìm kiếm đôi một khác nhau (không

có hiện tượng trùng khóa)

 Nếu cần quản lý các nút có khóa trùng nhau trong cây nhị

phân tìm kiếm thì có thể mở rộng cấu trúc bằng cách thêm

thành phần Count ghi nhận số khóa trùng:

typedef struct BSENode

typedef BSEOneNode * BSEType;

 Nút bên trái nhất là nút có giá trị khóa nhận diện nhỏ nhất và

nút phải nhất là nút có giá trị khóa nhận diện lớn nhất

Trang 28

2.3.2 Các thao tác trên cây nhị phân tìm kiếm

2.3.2.a Tìm kiếm trên cây

2.3.2.b Thêm vào một nút trên cây

2.3.2.c Loại bỏ 1 nút trên cây

2.3.2.d Hủy toàn bộ cây

Trang 29

2.3.2.a Tìm kiếm trên cây nhị phân tìm kiếm BST

 Tìm kiếm trong cây có tồn tại nút có khóa (Key) là SearchData

hay không

 Dùng thuật toán tìm kiếm nhị phân vì do đặc điểm của cây nhị

phân tìm kiếm thì tại 1 nút nểu Key của nút này khác với

SearchData:

 Nếu SearchData > Key của nút tìm ở cây con bên phải

 Nếu SearchData < Key của nút tìm ở cây con bên trái

Trang 30

2.3.2.a Tìm kiếm trên cây nhị phân tìm kiếm BST (tt)

Cài đặt thuật toán

BSTType BSTSearching (BSTType BSTree, T SearchData)

{

BSTType CurrNode = BSTree;

while (CurrNode !=NULL & CurrNode->Key != SeachData)

{

if (CurrNode ->Key > SearchData)

CurrNode = CurrNode ->BSTLeft;

Trang 31

2.3.2.b Thêm vào một nút trên cây nhị phân tìm kiếm

 Giả sử thêm vào 1 nút có thành phần dữ liệu là NewData vào

cây nhị phân tìm kiếm sao cho sau khi thêm, cây vẫn là cây nhị phân tìm kiếm

 Bao gồm các thao tác tìm kiếm vị trí thêm và thêm nút vào

cây

 Thao tác chỉ thêm được nếu không có hiện tượng trùng khóa,

do đó nếu NewData trùng với Key của 1 trong các nút trong

cây thì không thực hiện thêm.

Trang 32

2.3.2.b Thêm vào một nút trên cây nhị phân tìm kiếm (tt)

B6.1: AddLeft = False

B6.2: If (CurrNode->BSTRight != NULL)

CurrNode = CurrNode->BSTRight B8: Lặp lại B5

Trang 33

2.3.2.b Thêm vào một nút trên cây nhị phân tìm kiếm (tt)

BSTType BSTAddNode (BSTType &BSTree, T NewData)

{ BSTType NewNode = BinTreeCreateNode(NewData);

if (NewNode == NULL) return (NewNode);

if (BSTree == NULL) BSTree = NewNode;

if (CurrNode->BSTRight != NULL)

CurrNode = CurrNode->BSTRight;

else break;

} }

if (AddLeft == 1) CurrNode->BSTLeft = NewNode;

else CurrNode->BSTRight = NewNode;

}

Trang 34

2.3.2.c Loại bỏ 1 nút trên cây

Trang 35

2.3.2.d Hủy toàn bộ cây

Thao tác chỉ đơn giản là việc thực hiện nhiều lần thao tác hủy một

nút trên cây nhị phân tìm kiếm cho đến khi cây trở thành rỗng.Hàm thực hiện việc hủy tất cả các nút trong cây nhị phân tìm kiếm

BSTree

void BSTDelete(BSTType &BSTree)

{

BSTType DelNode = BSTree;

while (BSTDeleteNodeTRS(BSTree, DelNode->Key) == 1)

DelNode = BSTree;

return;

}

Trang 36

3 Cây cân bằng (Balanced Tree)

3.1 Định nghĩa – Cấu trúc dữ liệu

 Cây cân bằng tương đối:

 Là cây nhị phân thỏa mãn điều kiện là đối với mọi nút của

cây thì chiều cao của cây con trái và chiều cao của cây con phải của nút đó hơn kém nhau không quá 1 (theo định

nghĩa của Adelson-Velskii và Landis)

 Cây cân bằng tương đối còn gọi là cây AVL (AVL Tree)

 Cây cân bằng hoàn toàn:

 Là cây nhị phân thỏa mãn điều kiện là đối với mọi nút của

cây thì số nút của cây con trái và số nút của cây con phải

của nút đó hơn kém nhau không quá 1

 Cây nhị phân cân bằng hoàn toàn là cây nhị phân cân bằng

tương đối

Trang 37

3.1 Định nghĩa – Cấu trúc dữ liệu (tt)

 Để ghi nhận mức độ cân bằng tại mỗi nút gốc cây con, dùng

thêm thành phần Bal trong cấu trúc dữ liệu của mỗi nút

typedef struct BALNode

typedef BALOneNode * BALType;

 Để quản lý cây cân bằng, chỉ cần quản lý địa chỉ nút gốc của

cây BALType BALTree;

Trang 38

3.1 Định nghĩa – Cấu trúc dữ liệu (tt)

 Giá trị chỉ số cân bằng Bal tại 1 nút gốc của cây con trong cây

cân bằng tương đối bằng hiệu số giữa chiều cao cây con trái

và chiều cao cây con phải của nút đó

 Giá trị chỉ số cân bằng Bal tại 1 nút gốc của cây con trong cây

cân bằng hoàn toàn = hiệu số giữa số nút cây con trái và số nút cây con phải của nút đó

 Nếu tại mọi nút trong cây nhị phân mà thỏa mãn điều kiện

-1 <= Bal <= 1 thì cây là cây cân bằng Phạm vi từ -1  1 là phạm vi cho phép của chỉ số cân bằng Bal

 Nếu Bal = 0: cây con trái & cây con phải đều nhau

 Nếu Bal = -1: cây con trái nhỏ hơn cây con phải (lệch phải)

 Nếu Bal = +1: cây con trái nhỏ lớn cây con phải (lệch trái)

Trang 39

3.2 Các thao tác trên cây cân bằng

Các thao tác trên cây cân bằng áp dụng cho cây nhị phân tìm

kiếm cân bằng tương đối

3.2.a Thêm 1 nút vào cây cân bằng

3.2.b Hủy một nút khỏi cây cân bằng

Trang 40

3.2.a Thêm 1 nút vào cây cân bằng

Trang 41

3.2.b Hủy một nút khỏi cây cân bằng

Trang 42

BÀI TẬP

Bài tập trang 239, 240, 241 giáo trình “Cấu trúc dữ liệu”

Tiêu đề	Cây
Trường học	Trường Đại Học
Chuyên ngành	Cấu trúc dữ liệu
Thể loại	Bài giảng

Định dạng
Số trang	42
Dung lượng	291,5 KB