<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

<b>TRƯỜNG ĐẠI HỌC TÀI NGUYÊN VÀ MÔI TRƯỜNG TP.HCMKHOA: HỆ THỐNG THÔNG TIN VÀ VIỄN THÁM</b>

<b>---MÔN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT</b>

<i><b>Đề tài: Khái niệm và định nghĩa cây nhị phân</b></i>

<b>Giáo viên hướng</b>

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

<b>+ Tiểu Luận</b>

<i><b>TP Hồ Chí Minh, tháng 2 năm 2024</b></i>

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

3. Định nghĩa cấu trúc cây...4

4. Duyệt cây nhị phân...5

4.1. Duyệt tiền tự...5

4.2. Duyệt trung tự...6

4.3. Duyệt hậu tự...6

5. Hủy cây nhị phân...6

III. CÂY NHỊ PHÂN TÌM KIẾM...7

1. Thêm phần tử vào cây nhị phân tìm kiếm...8

2. Tìm một phần tử trong cây nhị phân tìm kiếm...8

3. Hủy nút trên cây nhị phân tìm kiếm...9

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

<b>PHẦN MỞ ĐẦU</b>

Cây nhị phân là một cấu trúc dữ liệu cơ bản và phổ biến trong khoa học máy tính. Nó được sử dụng để lưu trữ và tổ chức dữ liệu một cách hiệu quả, giúp việc truy cập và xử lý dữ liệu trở nên đơn giản và nhanh chóng hơn.

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

<b>PHẦN NỘI DUNGI. CẤU TRÚC CÂY</b>

Cấu trúc cây (Tree) là một tập hợp các phần tử gọi là nút (node), mỗi cây có một nút gốc (root) chứa nhiều nút con, mỗi nút con lại là một tập hợp các nút khác gọi là cây con (subtree). Các khái niệm cơ bản về cây:

 Bậc của nút: là số nút con của nút đó. Ví dụ bậc của nút A là 3, bậc của nút C là 1, bậc của nút G là 0…

 Bậc của cây: là bậc lớn nhất của nút trong cây đó, cây bậc n sẽ được gọi là cây n – phân. Ví dụ cây trong hình trên có bậc 3, gọi là cây tam phân, cây có bậc 2 gọi là cây nhị phân…  Nút lá: nút lá là nút có bậc bằng 0. Ví dụ các nút lá: B, G, H,

K, L, F

 Nút nhánh: là nút có bậc khác 0 mà khơng phải nút gốc (hay còn gọi là nút trung gian). Ví dụ các nút C, D, E

 Mức của nút: là số nguyên đếm từ 0, các nút ngang hàng nhau thì có cùng mức. Nút gốc A có mức là 0, mức 1 gồm các nút B, C, D, nút 3 gồm H, K, L.

 Chiều cao (chiều sâu): là mức lớn nhất của các nút lá. Ví dụ cây trên có nút lá bậc lớn nhất là H, K, L mức 3, vậy chiều cao của cây là 3.

 Độ dài đường đi đến nút x: là số nhánh (cạnh nối hai nút) cần đi qua tính từ nút gốc đến nút x. Hay độ dài đường đi đến nút mức i chính là i. Ví dụ nút E có độ dài đường đi là 2.

 Khi bạn đã nắm được các khái niệm cơ bản này, chúng ta hãy đến luôn với cây nhị phân.

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

<b>II. CÂY NHỊ PHÂN</b>

Cây nhị phân là một trường hợp đặc biệt của cấu trúc cây và nó cũng phổ biến nhất. Đúng như tên gọi của nó, cây nhị phân có bậc là 2 và mỗi nút trong cây nhị phân đều có bậc khơng q 2.

<b>1. Các khái niệm</b>

Có một số khái niệm khác về cây nhị phân các bạn cần nắm như sau:

đều có bậc 2. Ví dụ như hình trên, hoặc hình trên bỏ đi nút H và I cũng là cây nhị phân đúng.

lá đều bằng nhau. Ví dụ hình trên, tất cả các nút lá đều có mức 3.

<small></small> Cây nhị phân tìm kiếm (sẽ tìm hiểu bên dưới)

chênh lệch không quá 1 so với cây con bên phải.

<b>2. Định nghĩa cấu trúc nút</b>

Nhìn vào hình, ta có thể dễ dàng phân tích được rằng, mỗi nút trong cây nhị phân sẽ gồm 3 thành phần như sau:

<small></small> Thành phần dữ liệu: có thể là bất kỳ kiểu dữ liệu nào. <small></small> Thành phần liên kết trái: lưu trữ địa chỉ của nút gốc của

cây con bên trái. Kiểu dữ liệu là con trỏ trỏ vào node.

<small></small> Thành phân liên kết phải: lưu trữ địa chỉ của nút gốc của cây con bên phải. Kiểu dữ liệu là con trỏ trỏ vào node.

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

Chúng ta sẽ có struct lưu trữ một node như sau – ở đây để đơn giản mình sử dụng kiểu dữ liệu int cho thành phần dữ liệu của

Khi tạo một nút node mới, chúng ta cần phải gán lại các thành phần của node để nó khơng nhận giá trị rác, tránh lỗi không mong muốn. Chúng ta sẽ tạo một biến động cho node và trả về địa chỉ của node đó, mình sẽ có đoạn code tạo node như sau:

Node CreateNode int * ( init)

<b>3. Định nghĩa cấu trúc cây</b>

Để quản lý một cái cây, bạn chỉ cần quản lý được nút gốc, bạn có thể đi được đến các nhánh và lá của nó từ đó. Trên thực tế bạn khơng cần phải định nghĩa một kiểu dữ liệu nào để quản lý cả, tuy nhiên, để cho code rõ ràng hơn, bạn nên định nghĩa một kiểu dữ liệu cây nữa.

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

typedef Node Tree* ;

Lúc này, khi tạo một cây, bản chất là nó sẽ tạo cho bạn một con trỏ có thể trỏ vào một node.

Tree myTree;

Vì nó là con trỏ nên các bạn gán nó bằng NULL để tránh lỗi, nhưng để mọi thứ rõ ràng hơn, mình sẽ dùng hàm tạo cây đơn

<b>4. Duyệt cây nhị phân</b>

Có 3 cách duyệt cây nhị phân:

<small></small> Duyệt tiền tự (NLR): duyệt nút gốc, duyệt tiền tự cây con trái, duyệt tiền tự cây con phải.

<small></small> Duyệt trung tự (LNR): duyệt trung tự cây con trái, duyệt nút gốc, duyệt trung tự cây con phải.

<small></small> Duyệt hậu tự (LRN): duyệt hậu tự cây con trái, duyệt hậu tự cây con phải, duyệt nút gốc.

Để bạn hiểu rõ hơn ba cách duyệt này, chúng ta sẽ sử dụng lại hình ảnh cây nhị phân trên:

<small></small> Duyệt tiền tự: A B D H I E K L C F M N G O P

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

<b>5. Hủy cây nhị phân</b>

Để hủy đi cây nhị phân, các bạn cũng thực hiện duyệt và xóa đi các nút của cây, tuy nhiên, các bạn dễ thấy rằng, nếu ta duyệt tiền tự và trung tự, khi xóa nút nhánh thì sẽ bị mất ln địa chỉ của các nút con. Do đó, việc hủy cây nhị phân bắt buộc phải duyệt hậu tự. Hay nói cách khác, bạn phải xóa các phần tử là nút lá xóa dần lên đến nút gốc.

Chúng ta sẽ có hàm hủy như sau:

void DestroyTree Tree( &root)

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

Như vậy là chúng ta đã tìm hiểu về cách tạo một nút, kết nối chúng lại thành một cây nhị phân, duyệt cây và hủy cây. Tiếp theo chúng ta sẽ tìm hiểu về cây nhị phân đặc biệt khác là cây nhị phân tìm kiếm.

<b>III. CÂY NHỊ PHÂN TÌM KIẾM</b>

Cây nhị phân tìm kiếm là cây nhị phân mà trong đó, các phần tử của cây con bên trái đều nhỏ hơn phần tử hiện hành và các phần tử của cây con bên phải đều lớn hơn phần tử hiện hành. Do tính chất này, cây nhị phân tìm kiếm khơng được có phần tử cùng giá trị.

Nhờ vào tính chất đặc biệt này, cây nhị phân tìm kiếm được sử dụng để tìm kiếm phần tử nhanh hơn (tương tự với tìm kiếm nhị phân). Khi duyệt cây nhị phân theo cách duyệt trung tự, bạn sẽ thu được một mảng có thứ tự. Chúng ta sẽ lần lượt tìm hiểu qua chúng.

<b>1. Thêm phần tử vào cây nhị phân tìm kiếm</b>

Để thêm phần tử vào cây nhị phân tìm kiếm, ta phải thêm vào cây nhưng vẫn đảm bảo được cây đó vẫn là cây nhị phân tìm kiếm. Ví dụ thêm phần tử 12 vào cây trong hình trên, mình sẽ cần chèn vào vị trí bên trái 13. Hàm duyệt tìm vị trí thích hợp và chèn của mình như sau:

void AddNode(Tree root,& Node node* ) {

if(root) {

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

if(root->data == node->data )// Nếu bị trùng giá trị thì khơng thêm

return;

if(node->data root< ->data )// Thêm vào cây con bên trái (nhỏ hơn nút hiện tại)

AddNode(root left-> , node); else

AddNode(root right,-> node );// Thêm vào cây con bên phải (lớn hơn nút hiện tại)

<small>2.</small> <b>Tìm một phần tử trong cây nhị phân tìm kiếm</b>

Như đã giới thiệu ở trên, để tìm một phần tử trong cây nhị phân tìm kiếm, chúng ta sẽ thực hiện tương tự việc tìm kiếm nhị phân. Nếu như nút cần tìm nhỏ hơn nút đang xét, chúng ta sẽ tìm cây con bên trái, ngược lại chúng ta sẽ tìm trong cây con bên phải, nếu đúng nút cần tìm thì mình sẽ trả về địa chỉ của nút đó. Mình sẽ có thuật tốn sau:

Node FindNode Tree * ( root,int x)

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

return root; x rootif( < ->data)

returnFindNode(root left-> , x );// Tìm cây con bên trái returnFindNode(root right, ); -> x // Tìm cây con bên phải }

return NULL ;// Khơng tìm thấy }

<small>3.</small> <b>Hủy nút trên cây nhị phân tìm kiếm</b>

Để hủy một nút có khóa X trong cây nhị phân tìm kiếm, chúng ta cần giải quyết ba trường hợp sau:

1. Nút X là nút lá, ta xóa đi mà khơng làm ảnh hưởng đến các nút khác. Ví dụ xóa nút 15 đi khơng ảnh hưởng gì đến các nút khác.

2. Nút X có 1 cây con, chúng ta chỉ cần nối nút cha của X với nút con của X. Ví dụ xóa nút 13 đi, ta chỉ cần nối nút 18 và 15 lại, sau đó xóa nút 13 đi.

3. Nút X có đầy đủ 2 cây con: vì X có đầy đủ 2 nút nên nếu ta xóa đi, ta sẽ bị mất tồn bộ cây con. Do đó chúng ta cần tìm phần tử thế mạng cho X mà vẫn đảm bảo được cây nhị phân tìm kiếm, sau đó mới xóa X đi.

Đối với hai trường hợp đầu thì dễ, tuy nhiên, với trường hợp thứ 3, chúng ta cần phải giải quyết vấn đề tìm phần tử thế mạng cho x, chúng ta sẽ có hai cách thực hiện như sau:

1. Nút thế mạng là nút có khóa nhỏ nhất (trái nhất) của cây con bên phải x.

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

2. Nút thế mạng là nút có khóa lớn nhất (phải nhất) của cây con bên trái x.

Lấy ví dụ cho các bạn dễ hiểu hơn, hình phía trên, xóa đi phần tử 18 theo cách 1, phần tử lớn nhất của cây con bên trái là 15, vậy thì thay 18 bằng 15 rồi xóa đi nút 15 cuối. Cách 2, phần tử nhỏ nhất của cây con bên phải là 23, vậy 18 sẽ thay bằng 23 và xóa nút 23 đó đi.

Đối với hai trường hợp đầu tiên khá đơn giản, nên mình sẽ lồng nó vào code ln ở phần dưới, mình sẽ giải quyết cách tìm phần tử thế mạng ở trường hợp 3 trước và theo cả hai cách. Theo cách 1, mình sẽ làm như sau:

<b>3.1 Trường hợp 1</b>

// nút p là nút cần thay thế, tree là cây đang xét (cây bên phải) void FindAndReplace1 Tree( & ,p Tree &tree)

if(tree left-> )// chưa phải nhỏ nhất (trái nhất) FindAndReplace1(p, tree->left );// tiếp tục tìm else// tree là nút trái nhất

{

p data tree-> = ->data ;// copy data

p tree= ;// trỏ nút p vào nút tree sẽ làm thế mạng bị xóa tree tree= ->right ;// nút trái khơng cịn tuy nhiên nút phải có thể cịn nên ta phải nối chúng lại

} }

Đối với trường hợp này, các bạn phải gọi hàm FindAndReplace1(p, root->right) trong hàm DeleteNode ở phía trên. Trường hợp thứ 2 thì ngược lại.

</div><span class="text_page_counter">Trang 15</span><div class="page_container" data-page="15">

<b>3.2. Trường hợp 2</b>

// nút p là nút cần thay thế, tree là cây đang xét (cây bên trái) void FindAndReplace2 Tree( & ,p Tree &tree)

if(tree right-> ) // chưa phải lớn nhất (phải nhất) FindAndReplace2(p, tree->right);// tiếp tục tìm else// tree là nút trái nhất

{

p data tree-> = ->data ;// copy data

p tree= ;// trỏ nút p vào nút tree sẽ làm thế mạng bị xóa tree tree= ->left;// nút phải không cịn tuy nhiên nút trái có thể cịn nên ta phải nối chúng lại

} }

Và trong hàm DeleteNode, các bạn sẽ gọi hàm FindAndReplace(p, root->left). Bây giờ, tổng hợp lại, chúng ta đã có thể dể dàng xóa một nút khỏi cây nhị phân tìm kiếm, mình sẽ code như sau:

void DeleteNode Tree( &root int x),

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

Node * =p root;// lưu lại nút cần xóa tránh bị ghi đè if(!root left-> )

root root= ->right ;// trường hợp 1 else if (!root right-> )

root root= ->left;// trường hợp 2

</div><span class="text_page_counter">Trang 17</span><div class="page_container" data-page="17">

Node *CreateNode(int init)

</div><span class="text_page_counter">Trang 23</span><div class="page_container" data-page="23">

Vậy là qua bài viết này, mình đã giới thiệu đến các bạn về cấu trúc cây, cây nhị phân và cây nhị phân tìm kiếm. Cây nhị phân là một cấu trúc dữ liệu cơ bản và quan trọng trong khoa học máy tính. Hiểu rõ các khái niệm và định nghĩa cơ bản về cây nhị phân là bước đầu tiên để học tập và sử dụng cấu trúc dữ liệu này hiệu quả.

<b>TÀI LIỆU THAM KHẢO</b>

<b>2. Chat GPT</b>

</div>