CAÂY NHỊ PHÂN

Mục lục nội dung

Cây nhị phânDuyệt cây nhị phânCây nhị phân kiếm tìm kiếmHủy nút trên cây nhị phân tìm kiếm kiếm
Cây nhị phân với cây nhị phân tra cứu kiếm | Khiêm Lê

Cây nhị phân là một cấu tạo dữ liệu đặc biệt mà vào môn cấu trúc 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 rãi trong xây dựng vì những ứng dụng của nó. Trong nội dung bài viết này, mình sẽ reviews đến các bạn về cây nhị phân cùng một phiên bạn dạng đặc biệt của nó là cây nhị phân kiếm tìm kiếm. Trước tiên, ta cần biết được cây là gì?


Cấu trúc cây

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

Bạn đang xem: Caây nhị phân


*
*
Binary tìm kiếm Tree

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

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

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

void AddNode(Tree &root, Node *node) if (root) if (root->data == node->data) // nếu bị trùng cực hiếm thì không thêm return; if (node->data root->data) // cung ứng cây con bên trái (nhỏ rộng nút hiện tại) AddNode(root->left, node); else AddNode(root->right, node); // cung cấp cây nhỏ bên bắt buộc (lớn rộng nút hiện nay tại) else root = node; // Đã tìm kiếm thấy vị trí ưng ý hợp, thêm node vào

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

Như đã reviews ở trên, nhằm tìm một phần tử trong cây nhị phân kiếm tìm kiếm, bọn họ sẽ thực hiện tương tự việc tìm kiếm kiếm nhị phân. Nếu như như nút buộc phải tìm bé dại hơn nút vẫn xét, họ sẽ tìm kiếm cây bé bên trái, ngược lại bọn họ sẽ tìm kiếm trong cây con bên phải, nếu đúng nút đề nghị tìm thì mình sẽ trả về địa chỉ cửa hàng của nút đó. Mình sẽ có 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); // kiếm tìm cây nhỏ bên trái return FindNode(root->right, x); // tìm kiếm cây bé bên yêu cầu return NULL; // không kiếm thấy

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

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

Nút X là nút lá, ta xóa đi nhưng không làm ảnh hưởng đến các nút khác. Lấy ví dụ xóa nút 15 đi không tác động gì đến các nút khác.Nút X có 1 cây con, bọn họ chỉ cần nối nút phụ thân của X cùng với nút con của X. Ví dụ như xóa nút 13 đi, ta chỉ việc nối nút 18 cùng 15 lại, sau đó xóa nút 13 đi.Nút X có không thiếu thốn 2 cây con: do X có vừa đủ 2 nút nên nếu ta xóa đi, ta sẽ ảnh hưởng mất toàn bộ cây con. Vày đó bọn họ cần tìm phần tử thế mạng đến X mà lại vẫn đảm bảo được cây nhị phân search kiếm, tiếp đến mới xóa X đi.

Đối với nhì trường hòa hợp đầu thì dễ, mặc dù nhiên, với trường hợp vật dụng 3, họ cần phải giải quyết vấn đề tìm phần tử thế mạng mang lại x, bọn họ sẽ có hai cách triển khai như sau:

Nút cụ mạng là nút có khóa bé dại nhất (trái nhất) của cây bé bên cần x.Nút chũm mạng là nút có khóa lớn số 1 (phải nhất) của cây nhỏ bên trái x.

Xem thêm: Chiều Cao Và Cân Nặng Của Lionel Messi Cao Bao Nhiêu ? Lộ Chiều Cao Messi

Lấy ví dụ cho các bạn dễ phát âm hơn, hình phía trên, xóa đi bộ phận 18 theo cách 1, phần tử lớn tuyệt nhất của cây bé bên trái là 15, vậy thì vắt 18 bởi 15 rồi xóa đi nút 15 cuối. Phương pháp 2, phần tử nhỏ dại nhất của cây con bên bắt buộc là 23, vậy 18 đang thay bằng 23 cùng xóa nút 23 kia đi.

Đối với nhì trường hợp trước tiên khá đối chọi giản, nên mình sẽ lồng nó vào code luôn ở phần dưới, mình sẽ giải quyết và xử lý cách tìm bộ phận thế mạng ở trường hòa hợp 3 trước cùng theo cả nhì cách. Theo cách 1, mình sẽ có tác dụng như sau:

Trường hợp 1

// nút p. Là nút buộc phải thay thế, tree là cây vẫn xét (cây bên phải)void FindAndReplace1(Tree &p, Tree &tree) if (tree->left) // chưa phải nhỏ tuổi nhất (trái nhất) FindAndReplace1(p, tree->left); // tiếp tục 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 sẽ làm cầm cố mạng bị xóa tree = tree->right; // nút trái không còn tuy nhiên nút phải rất có thể còn nên ta nên nối chúng lại Đối với trường vừa lòng này, chúng ta phải call hàm FindAndReplace1(p, root->right) vào hàm DeleteNode sống phía trên. Trường hợp thứ hai thì ngược lại.

Trường thích hợp 2

// nút phường là nút bắt buộc thay thế, tree là cây sẽ xét (cây mặt trái)void FindAndReplace2(Tree &p, Tree &tree) if (tree->right) // không phải lớn tốt nhất (phải nhất) FindAndReplace2(p, tree->right); // liên tục tìm else // tree là nút trái tuyệt nhất p->data = tree->data; // copy data p. = tree; // trỏ nút phường vào nút tree sẽ làm nạm mạng bị xóa tree = tree->left; // nút phải không còn tuy nhiên nút trái rất có thể còn bắt buộc ta đề nghị nối bọn 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 vừa lòng 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 đã 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 lúc này (root) là nút nên xóa Node *p = root; // cất giữ nút buộc phải xóa kiêng bị ghi đè if (!root->left) root = root->right; // trường hợp 1 else if (!root->right) root = root->left; // trường đúng theo 2 else FindAndReplace1(p, root->right); // giải pháp 1 // FindAndReplace2(p, root->left); // giải pháp 2 delete p; // xóa nút else cout "Not found! "; // không tìm thấy phần tử cần xóa

Tổng kết

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

Cảm ơn các bạn đã theo dõi bài xích viết, giả dụ thấy nội dung bài viết này hay, đừng quên share cho mọi bạn cùng biết nhé! Cảm ơn những 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) // xử trí nút cội (root) NLR(root->left); NLR(root->right); void LNR(Tree root) if (root) LNR(root->left); // cách xử trí nút nơi bắt đầu (root) LNR(root->right); void LRN(Tree root) if (root) LRN(root->left); LRN(root->right); // giải pháp 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; p. = tree; tree = tree->right; void FindAndReplace2(Tree &p, Tree &tree) if (tree->right) FindAndReplace2(p, tree->right); else p->data = tree->data; p. = 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! ";