Các thuật toán thao tác cơ bản trên cây nhị phân tìm kiếm trong C/C++

Cây nhị phân tìm kiếm (Binary Search Tree – BST) là một cấu trúc khá phổ biến và vô cùng quan trọng đối với ngôn ngữ lập trình C/C++. Vì vậy trong bài viết này, Isinhvien sẽ chia sẻ đến các bạn các thuật toán thao tác cơ bản trên cây nhị phân tìm kiếm: Duyệt cây theo thứ tự, tìm kiếm một phần tử trên cây, thêm một phần tử trên cây, xóa một phần tử trên cây, tạo và xóa cây nhị phân tìm kiếm. Trước khi đi vào bài này thì hãy chắc rằng bạn đã nắm rõ về các khái niệm của cây và cây nhị phân tìm kiếm. Nếu chưa thì hãy tham khảo qua bài viết Tất tần tật về cây trong ngôn ngữ lập trình của Isinhvien nhé!

Tóm Tắt

Duyệt cây theo thứ tự

Thao tác duyệt cây trên cây nhị phân tìm kiếm trọn vẹn giống như trên cây nhị phân. Đặc biệt là khi duyệt theo thứ tự giữa, trình tự những nút duyệt qua sẽ cho ta một dãy những nút theo thứ tự tăng dần của khóa .

Hàm duyệt cây:

void  DuyetGiua(Tree  T)   {
      if  (T != NULL)    
      {  DuyetGiua( (*T).left );
         cout << (*T).key << " ";
         DuyetGiua( (*T).right );    
      }   
}

Cây nhị phân tìm kiếm

Sau khi duyệt cây nhị phân trên sẽ cho ra kết quả sau:

Bạn đang đọc: Các thuật toán thao tác cơ bản trên cây nhị phân tìm kiếm trong C/C++

1 2 3 4 5 6 7 8 9

Tìm kiếm một phần tử trên cây

Giả sử ta cần tìm kiếm một phân tử có giá trị x, ta hoàn toàn có thể triển khai như sau

Hàm tìm một phần tử trên cây:

TNODE *searchNode(TREE T, Data X) 
{ 
      if (T) { 
          if ( T -> Key == X) return T; 
          if (T -> Key > X) return searchNode( T -> Left, X); 
          else return searchNode(T-> Right, X);
      }  
return NULL; 
}

Ta cũng hoàn toàn có thể kiến thiết xây dựng một hàm tìm kiếm không đệ quy như sau :

TNODE * searchNode(TREE Root, Data x) 
{ 
   NODE *p = Root; 
   while (p != NULL) { 
        if(x == p->Key) return p; 
        else if(x < p->Key) p = p-> Left; 
        else p = p-> Right; 
   } 
return NULL; 
}

Thêm một phần tử vào cây

Việc thêm một thành phần X vào cây phải bảo vệ điều kiện kèm theo ràng buộc của BST. Ta hoàn toàn có thể thêm vào nhiều chỗ khác nhau trên cây, nhưng nếu thêm vào một nút lá sẽ là tiện nghi nhất do ta hoàn toàn có thể thực hiên quy trình tương tự như như thao tác tìm kiếm. Khi chấm hết quy trình tìm kiếm cũng chính là lúc tìm được chỗ cần thêm. Hàm insert sẽ trả về giá trị – 1, 0, 1 khi không đủ bộ nhớ, gặp nút cũ hay thành công xuất sắc .

Hàm thêm một phần tử vào cây

int insertNode(TREE &T, Data X) 
{
    if(T) { 
       if(T->Key == X) return 0; //đã có 
       if(T->Key > X) return insertNode(T-> Left, X); 
       else return insertNode(T-> Right, X); 
     } 
     T =new Tnode; 
     if(T == NULL) return -1; //thiếu bộ nhớ 
     T-> Key = X; 
     T-> Left = NULL;
     T-> Right = NULL;
     return 1; //thêm vào thành công 
}

Xóa một phần tử trên cây

Việc hủy một phần tử ra khỏi cây phải đảm bảo điều kiện ràng buộc của cây nhị phân tìm kiếm Có 3 trường hợp khi hủy nút X có thể xảy ra:

Xem thêm: Bài 2 – Cấu trúc thư mục Laravel – ITCOM

X là nút lá: chỉ đơn giản hủy X vì nó không móc nối đến phần tử nào khác
X chỉ có 1 con (trái hoặc phải): trước khi hủy X ta móc nối cha của X với con duy nhất của nó
X có đủ cả 2 con: ta không thể hủy trực tiếp do X có đủ 2 con. Do đó, ta sẽ hủy gián tiếp. Thay vì hủy X, ta sẽ tìm một phần tử thế mạng Y. Phần tử này có tối đa một con. Thông tin lưu tại Y sẽ được chuyển lên lưu tại X. Sau đó, nút bị hủy thật sự sẽ là Y giống như 2 trường hợp đầu. Vấn đề là phải chọn Y sao cho khi lưu Y vào vị trí của X, cây vẫn là CNPTK. Ta có thể chọn 1 trong 2 phần tử: Phần tử nhỏ nhất trên cây con phải hoặc phần tử lớn nhất trên cây con trái.

Việc lựa chọn thành phần nào là thành phần thế mạng trọn vẹn nhờ vào vào ý thích của ngƣời lập trình. Ở đây, tất cả chúng ta sẽ chọn thành phần lớn nhất trên cây con trái làm thành phần thế mạng .

Hàm delNode trả về giá trị 1 khi hủy thành công xuất sắc hoặc o nếu không có X trong cây .

int delNode(TREE &T, Data X) 
{ 
   if(T==NULL) return 0; 
   if(T->Key > X) return delNode (T->Left, X); 
   if(T->Key < X) return delNode (T->Right, X); 
   else { //T->Key == X 
     TNode* p = T; 
     if (T->Left == NULL) T = T->Right; 
     else if (T->Right == NULL) T = T->Left; 
     else { //T có cả 2 con 
        TNode* q = T->Right; 
        searchStandFor(p, q);
     } delete p; 
   } 
}

Trong đó hàm searchStandFor dùng để tìm thành phần thế mạng cho nút p, được viết như sau :

void searchStandFor(TREE &p, TREE &q) 
{ 
    if(q->Left) searchStandFor(p, q->Left); 
    else { 
      p->Key = q->Key;
      p = q; q = q->Right; 
    } 
}

Tạo và xóa cây nhị phân tìm kiếm

Tạo cây nhị phân

Để tạo một cây nhị phân tìm kiếm, ta có thể lặp lại quá trình thêm một phần tử vào một cây rỗng.

Xem thêm: Laravel Broadcasting hoạt động ra sao

Xóa toàn bộ cây

Việc xóa hàng loạt cây hoàn toàn có thể được thực thi trải qua thao tác duyệt cây theo thứ tự sau. Nghĩa là ta sẽ hủy cây con trái, cây con phải rồi mới hủy nút gốc .

void removeTree(TREE &T) 
{
   if(T) { 
      removeTree(T->Left); 
      removeTree(T->Right); 
      delete(T); 
   }
}

Isinhvien hy vọng sau bài viết này sẽ giúp các bạn hiểu hơn về thuật toán của những thao tác trên cây nhị phân này và có thể áp dụng nó cho việc học tập cũng như công việc của mình. Đừng quên theo dõi Isinhvien để cập nhật các kiến thức bổ ích mỗi ngày nhé! Chúc các bạn thật nhiều sức khỏe và gặt hái được nhiều thành công trong cuộc sống!

Source: https://final-blade.com
Category: Kiến thức Internet

admin

final-blade.com