Vẽ Cây Nhị Phân Tìm Kiếm

     

Mục lục nội dung

Cây nhị phânDuyệt cây nhị phânCây nhị phân tìm kiếmHủy nút bên trên cây nhị phân search kiếm
Cây nhị phân cùng cây nhị phân tìm kiếm | Khiêm Lê

Cây nhị phân là một cấu trúc dữ liệu đặc biệt mà vào môn kết cấu dữ liệu và giải thuật các các bạn sẽ được học, nó được sử dụng rất rộng lớn rãi trong lập trình sẵn vì những ứng dụng của nó. Trong nội dung bài viết này, mình sẽ ra mắt đến chúng ta về cây nhị phân với một phiên bạn dạng đặc biệt của chính nó là cây nhị phân search kiếm. Trước tiên, ta cần phải biết được cây là gì?


Cấu trúc cây

Cấu trúc cây (Tree) là một tập vừa lòng các phần tử gọi là nút (node), từng cây tất cả một nút nơi bắt đầu (root) đựng nhiều nút con, từng nút nhỏ lại là một trong tập hợp các nút khác hotline là cây bé (subtree).

Bạn đang xem: Vẽ cây nhị phân tìm kiếm


*
*
Binary tìm kiếm Tree

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

Thêm bộ phận vào cây nhị phân kiếm tìm kiếm

Để thêm phần tử vào cây nhị phân tra cứu kiếm, ta bắt buộc thêm vào cây nhưng mà vẫn bảo đảm an toàn được cây này vẫn là cây nhị phân search kiếm. Lấy ví dụ như thêm thành phần 12 vào cây trong hình trên, mình sẽ phải chèn vào vị trí bên trái 13. Hàm thông qua tìm vị trí phù hợp và chèn của bản thân như sau:

void AddNode(Tree &root, Node *node) if (root) if (root->data == node->data) // ví như bị trùng quý hiếm 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); // cung cấp cây nhỏ bên phải (lớn hơn nút hiện tại tại) else root = node; // Đã tìm thấy vị trí yêu thích hợp, thêm node vào

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

Như đã ra mắt ở trên, để tìm một phần tử trong cây nhị phân kiếm tìm kiếm, họ sẽ tiến hành tương tự việc tìm và đào bới kiếm nhị phân. Nếu như nút bắt buộc tìm nhỏ tuổi hơn nút vẫn xét, chúng ta sẽ search cây nhỏ bên trái, ngược lại bọn họ sẽ tìm kiếm trong cây bé bên phải, nếu như đúng nút đề nghị tìm thì mình vẫn trả về add của nút đó. Mình sẽ sở hữu thuật toán sau:

Node *FindNode(Tree root, int x) if (root) if (root->data == x) // kiếm tìm thấy return root; if (x root->data) return FindNode(root->left, x); // search cây con bên trái return FindNode(root->right, x); // search cây bé bên yêu cầu return NULL; // không tìm thấy

Hủy nút trên cây nhị phân search kiếm

Để diệt một nút tất cả khóa X vào cây nhị phân tìm kiếm kiếm, họ cần xử lý ba trường phù hợp sau:

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. Lấy ví dụ như xóa nút 15 đi không ảnh hưởng gì đến những nút khác.Nút X có 1 cây con, họ chỉ đề xuất nối nút phụ thân của X cùng với nút nhỏ của X. Ví dụ xóa nút 13 đi, ta chỉ việc nối nút 18 cùng 15 lại, tiếp đến xóa nút 13 đi.Nút X có khá đầy đủ 2 cây con: bởi vì X có rất đầy đủ 2 nút cần nếu ta xóa đi, ta có khả năng sẽ bị mất toàn cục cây con. Vị đó họ cần tìm thành phần thế mạng mang lại X nhưng mà vẫn bảo vệ được cây nhị phân search kiếm, kế tiếp mới xóa X đi.

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

Nút nạm mạng là nút tất cả khóa nhỏ nhất (trái nhất) của cây nhỏ bên đề xuất x.Nút gắng mạng là nút gồm khóa lớn nhất (phải nhất) của cây con bên trái x.

Xem thêm: Cậu Thích Tôi Gọi Cậu Là Gì ? Đừng Bỏ Qua Bài Viết Này Nhé! Cậu Thích Tôi Gọi Cậu Là Gì

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 phong cách 1, bộ phận lớn duy nhất của cây con bên trái là 15, vậy thì cầm cố 18 bởi 15 rồi xóa đi nút 15 cuối. Phương pháp 2, phần tử bé dại nhất của cây con bên phải là 23, vậy 18 đang thay bởi 23 cùng xóa nút 23 kia đi.

Đối với nhì trường hợp đầu tiên khá solo giản, buộc phải mình đang lồng nó vào code luôn luôn ở phần dưới, mình sẽ giải quyết cách tìm thành phần thế mạng nghỉ ngơi trường vừa lòng 3 trước với theo cả nhì cách. Theo phong cách 1, bản thân sẽ làm cho như sau:

Trường hòa hợp 1

// nút p. Là nút phải thay thế, tree là cây đã xét (cây mặt phải)void FindAndReplace1(Tree &p, Tree &tree) if (tree->left) // chưa phải nhỏ dại nhất (trái nhất) FindAndReplace1(p, tree->left); // thường xuyên tìm else // tree là nút trái tuyệt nhất p->data = tree->data; // copy data p = tree; // trỏ nút p. Vào nút tree đã làm cố kỉnh 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 buộc phải ta cần nối bọn chúng lại Đối với trường vừa lòng này, các bạn phải hotline hàm FindAndReplace1(p, root->right) trong hàm DeleteNode ở phía trên. Ngôi trường hợp thứ 2 thì ngược lại.

Xem thêm: Cách Tìm Nhạc Trong Video Trên Điện Thoại Iphone, Cách Tìm Nhạc Trong Video Trên Điện Thoại

Trường hợp 2

// nút p là nút đề nghị thay thế, tree là cây đã xét (cây mặt trái)void FindAndReplace2(Tree &p, Tree &tree) if (tree->right) // chưa hẳn lớn độc nhất vô nhị (phải nhất) FindAndReplace2(p, tree->right); // thường xuyên tìm else // tree là nút trái tốt nhất p->data = tree->data; // copy data p = tree; // trỏ nút phường vào nút tree đang làm nắm mạng bị xóa tree = tree->left; // nút phải không thể tuy nhiên nút trái có thể còn cần ta nên nối bọn chúng lại Và trong hàm DeleteNode, các các bạn sẽ gọi hàm FindAndReplace(p, root->left). Bây giờ, tổng đúng theo lại, bọn họ đã rất có thể dể dàng xóa một nút khỏi cây nhị phân tra cứu kiếm, mình vẫn code như sau:

void DeleteNode(Tree &root, int x) if (root) if (x > root->data) DeleteNode(root->right, x); else if (x root->data) DeleteNode(root->left, x); else // nút hiện tại (root) là nút yêu cầu xóa Node *p = root; // lưu lại nút nên xóa kị bị ghi đè if (!root->left) root = root->right; // trường đúng theo 1 else if (!root->right) root = root->left; // trường hòa hợp 2 else FindAndReplace1(p, root->right); // cách 1 // FindAndReplace2(p, root->left); // phương pháp 2 delete p; // xóa nút else cout "Not found! "; // không tìm kiếm thấy bộ phận cần xóa

Tổng kết

Vậy là qua bài viết này, bản thân đã ra mắt đến chúng ta về cấu tạo cây, cây nhị phân và cây nhị phân kiếm tìm kiếm. Đương nhiên, mình không hẳn “master” và mình cũng không thể làm sao mà nỗ lực được hết tất cả các triết lý đồ thị tốt thuật toán, vì thế sai sót là tất yêu tránh khỏi, hy vọng các bạn góp ý thêm.

Cảm ơn các bạn đã theo dõi bài bác viết, nếu như thấy nội dung bài viết này hay, chớ quên chia sẻ cho mọi người cùng biết nhé! Cảm ơn các bạn!

Source code

struct Node int data; Node *left; Node *right;;typedef Node *Tree;Node *CreateNode(int init) Node *p = new Node; p->data = init; p->left = NULL; p->right = NULL; return p;void CreateTree(Tree &root) root = NULL;void DestroyTree(Tree &root) if (root) DestroyTree(root->left); DestroyTree(root->right); delete root; void AddNode(Tree &root, Node *node) if (root) if (root->data == node->data) return; if (node->data root->data) AddNode(root->left, node); else AddNode(root->right, node); else root = node; Node *FindNode(Tree root, int x) if (root) if (root->data == x) return root; if (x root->data) return FindNode(root->left, x); return FindNode(root->right, x); return NULL;void PrintTree(Tree root)// print tree using LNR if (root) PrintTree(root->left); cout root->data " "; PrintTree(root->right); void NLR(Tree root) if (root) // cách xử trí nút cội (root) NLR(root->left); NLR(root->right); void LNR(Tree root) if (root) LNR(root->left); // xử lý nút gốc (root) LNR(root->right); void LRN(Tree root) if (root) LRN(root->left); LRN(root->right); // xử lý nút gốc (root) void FindAndReplace1(Tree &p, Tree &tree) if (tree->left) FindAndReplace1(p, tree->left); else p->data = tree->data; phường = tree; tree = tree->right; void FindAndReplace2(Tree &p, Tree &tree) if (tree->right) FindAndReplace2(p, tree->right); else p->data = tree->data; phường = tree; tree = tree->left; void DeleteNode(Tree &root, int x) if (root) if (x > root->data) DeleteNode(root->right, x); else if (x root->data) DeleteNode(root->left, x); else Node *p = root; if (!root->left) root = root->right; else if (!root->right) root = root->left; else FindAndReplace1(p, root->right); // FindAndReplace2(p, root->left); delete p; else cout "Not found! ";