Giải phương trình bậc nhất ax + b = 0 trong C / C++ 
Lệnh Alert trong Javascript Tìm node Max và Min trong cây nhị phân tìm kiếm
Trong bài viết này, codehow sẽ hướng dẫn các bạn cách tìm node Max và Min trong cây nhị phân tìm kiếm. Bởi cây nhị phân tìm kiếm sinh ra là để tìm kiếm, vậy nên việc tìm kiếm node Max và Min là một chuyện đơn giản.
Chúng ta sẽ cùng nhau tìm hiểu về cách tìm node Max và Min trước, sau đó mình sẽ đưa ra ví dụ để thực hiện bằng ngôn ngữ C++. Hãy bắt đầu cùng mình thôi nhé!!
Tìm node Max và Min trong cây nhị phân tìm kiếm
Như các bạn đã biết thì cây nhị phân tìm kiếm là một cấu trúc lưu trữ dữ liệu đặc biệt dưới dạng cây. Các cây con bên trái luôn nhỏ hơn hoặc bằng node gốc, tương tự như vậy các cây con luôn lớn hơn hoặc bằng node gốc.
Ví vậy nếu chúng ta muốn tìm giá trị Max thì duyệt sang cây bên phải và tìm giá trị Min thì duyệt sang cây bên trái.
Tìm node Max trong cây nhị phân tìm kiếm
Như đã nói thì cây nhị phân tìm kiếm luôn luôn lưu giá trị của node lớn hơn node gốc. Vì vậy chỉ cần duyệt cây con bên phải là có thể tìm được node Max rồi. Cụ thể như sau:
- Kiểm tra xem node bên phải có tồn tại hay không, nếu không có thì node gốc chính là node Max.
- Trong trường hợp có tồn tại thì ta duyệt sang bên phải bằng cách gọi đệ quy, cứ như vậy cho đến khi hết cây ta sẽ được node Max.
int TimMax(TREE t)
{
// CÁCH TỐI ƯU NHẤT
// nếu node cha mà không tồn cây con phải - thì node cha này chính là node ngoài cùng nhất của cây con phải - cũng chính là node có giá trị lớn nhất
if (t->pRight == NULL)
{
return t->data;
}
return TimMax(t->pRight); // duyệt đến node cuối cùng nhất bên cây con phải ==> để tìm giá trị lớn nhất
}Tìm node Min trong cây nhị phân tìm kiếm
Đối với tìm node Min cũng được thực hiện tương tự. Nếu node bên trái của node gốc bằng NULL thì node gốc chính là node Min. Ngược lại nếu tồn tại node bên trái thì ta thực hiện gọi đệ quy để duyệt hết cây con bên trái và tìm node Min.
//hàm tìm giá trị MIN
int TimMin(TREE t)
{
// CÁCH TỐI ƯU NHẤT
// nếu node cha mà không tồn cây con trái - thì node cha này chính là node ngoài cùng nhất của cây con trái - cũng chính là node có giá trị nhỏ nhất
if (t->pLeft == NULL)
{
return t->data;
}
return TimMin(t->pLeft); // duyệt đến node cuối cùng nhất bên cây con trái ==> để tìm giá trị nhỏ nhất
}Ví dụ tìm node Max và Min trong cây nhị phân tìm kiếm
Để hiểu rõ hơn thì mình sẽ thực hiện một ví dụ tìm node Max và Min trong cây nhị phân tìm kiếm. Cụ thê các yêu cầu của chương trình như sau:
- Xây dựng cấu trúc cây nhị phân tìm kiếm và cấu trúc node.
- Tạo hàm thêm node vào cây.
- Tạo hàm duyệt cây.
- Hàm tìm node Max trong cây nhị phân tìm kiếm.
- Hàm tìm node Min trong cây nhị phân tìm kiếm.
- Tạo menu với các yêu cầu trên cho người dùng lựa chọn.
Bây giờ chúng ta sẽ đi thực hiện từng yêu cầu ở trên nhé.
Bước 1: Xây dựng cấu trúc cây nhị phân tìm kiếm và cấu trúc node.
// khai báo cấu trúc 1 cái node trong cây nhị phân tìm kiếm
struct node
{
int data; // dữ liệu chứa trong 1 cái node
struct node *pLeft; // con trỏ liên kết với cái node bên trái <=> cây con trái
struct node *pRight; // con trỏ liên kết với cái node bên phải <=> cây con phải
};
typedef struct node NODE;
typedef NODE* TREE;
// hàm khởi tạo cây nhị phân tìm kiếm
void KhoiTaoCay(TREE &t)
{
t = NULL;
}Bước 2: Tạo hàm thêm node vào cây.
// hàm thêm 1 cái phần tử vào cây
void ThemNodeVaoCay(TREE &t, int x)
{
// nếu cây rỗng
if (t == NULL)
{
NODE *p = new NODE;
p->data = x;
p->pLeft = NULL;
p->pRight = NULL;
t = p;
}
else
{
// nếu phần tử thêm vào mà nhỏ hơn nút gốc thì sẽ duyệt qua bên trái
if (x < t->data)
{
ThemNodeVaoCay(t->pLeft, x);
}
else if (x > t->data)
{
ThemNodeVaoCay(t->pRight, x);
}
}
}Bước 3: Tạo hàm duyệt cây.
// hàm xuất phần tử trong cây nhị phân tìm kiếm
void NLR(TREE t)
{
if (t != NULL)
{
// xử lí
cout << t->data << " ";
NLR(t->pLeft);
NLR(t->pRight);
}
}Bước 4: Hàm tìm node Max trong cây nhị phân tìm kiếm.
int TimMax(TREE t)
{
// CÁCH TỐI ƯU NHẤT
// nếu node cha mà không tồn cây con phải - thì node cha này chính là node ngoài cùng nhất của cây con phải - cũng chính là node có giá trị lớn nhất
if (t->pRight == NULL)
{
return t->data;
}
return TimMax(t->pRight); // duyệt đến node cuối cùng nhất bên cây con phải ==> để tìm giá trị lớn nhất
}Bước 5: Hàm tìm node Min trong cây nhị phân tìm kiếm.
//hàm tìm giá trị MIN
int TimMin(TREE t)
{
// CÁCH TỐI ƯU NHẤT
// nếu node cha mà không tồn cây con trái - thì node cha này chính là node ngoài cùng nhất của cây con trái - cũng chính là node có giá trị nhỏ nhất
if (t->pLeft == NULL)
{
return t->data;
}
return TimMin(t->pLeft); // duyệt đến node cuối cùng nhất bên cây con trái ==> để tìm giá trị nhỏ nhất
}Bước 6: Tạo menu với các yêu cầu trên cho người dùng lựa chọn.
// hàm nhập cây nhị phân tìm kiếm
void Menu(TREE &t)
{
int luachon;
while(true)
{
cout << "\n\n\t\t ============ MENU ============";
cout << "\n1. Nhập phần tử cho cây";
cout << "\n2. Duyệt cây";
cout << "\n3. Giá trị MAX";
cout << "\n4. Giá trị MIN";
cout << "\n0. Thoát";
cout << "\n\n\t\t ============= END =============";
cout << "\nNhập lựa chọn của bạn: ";
cin >> luachon;
if (luachon == 1)
{
int x;
cout << "\nNhập giá trị: ";
cin >> x;
ThemNodeVaoCay(t, x);
}
else if (luachon == 2)
{
cout << "\nCây nhị phân tìm kiếm\n";
NLR(t);
}
else if (luachon == 3)
{
cout << "\nGiá trị MAX: "<<TimMax(t);
}
else if (luachon == 4)
{
cout << "\nGiá trị MAX: "<<TimMin(t);
}
else
{
break;
}
}
}Dưới đây là chường trình mình đã viết sẵn bằng ngôn ngữ C++, các bạn có thể tham khảo nhé.
#include<iostream>
using namespace std;
// khai báo cấu trúc 1 cái node trong cây nhị phân tìm kiếm
struct node
{
int data; // dữ liệu chứa trong 1 cái node
struct node *pLeft; // con trỏ liên kết với cái node bên trái <=> cây con trái
struct node *pRight; // con trỏ liên kết với cái node bên phải <=> cây con phải
};
typedef struct node NODE;
typedef NODE* TREE;
// hàm khởi tạo cây nhị phân tìm kiếm
void KhoiTaoCay(TREE &t)
{
t = NULL;
}
// hàm thêm 1 cái phần tử vào cây
void ThemNodeVaoCay(TREE &t, int x)
{
// nếu cây rỗng
if (t == NULL)
{
NODE *p = new NODE;
p->data = x;
p->pLeft = NULL;
p->pRight = NULL;
t = p;
}
else
{
// nếu phần tử thêm vào mà nhỏ hơn nút gốc thì sẽ duyệt qua bên trái
if (x < t->data)
{
ThemNodeVaoCay(t->pLeft, x);
}
else if (x > t->data)
{
ThemNodeVaoCay(t->pRight, x);
}
}
}
// hàm xuất phần tử trong cây nhị phân tìm kiếm
void NLR(TREE t)
{
if (t != NULL)
{
// xử lí
cout << t->data << " ";
NLR(t->pLeft);
NLR(t->pRight);
}
}
//Hàm tìm giá trị MAX
//------cách 1------------
// int MAX = INT_MIN; // gán cho biến MAX là giá trị nhỏ nhất của kiểu integer
// //// hàm tìm phần tử lớn nhất trong cây
// void TimMax(TREE t)
// {
// if (t != NULL)
// {
// // xử lí
// if (MAX < t->data)
// {
// MAX = t->data; // cập nhật lại giá trị cho biến MAX
// }
// TimMax(t->pLeft);
// TimMax(t->pRight);
// }
// }
int TimMax(TREE t)
{
// CÁCH TỐI ƯU NHẤT
// nếu node cha mà không tồn cây con phải - thì node cha này chính là node ngoài cùng nhất của cây con phải - cũng chính là node có giá trị lớn nhất
if (t->pRight == NULL)
{
return t->data;
}
return TimMax(t->pRight); // duyệt đến node cuối cùng nhất bên cây con phải ==> để tìm giá trị lớn nhất
}
//hàm tìm giá trị MIN
int TimMin(TREE t)
{
// CÁCH TỐI ƯU NHẤT
// nếu node cha mà không tồn cây con trái - thì node cha này chính là node ngoài cùng nhất của cây con trái - cũng chính là node có giá trị nhỏ nhất
if (t->pLeft == NULL)
{
return t->data;
}
return TimMin(t->pLeft); // duyệt đến node cuối cùng nhất bên cây con trái ==> để tìm giá trị nhỏ nhất
}
// hàm nhập cây nhị phân tìm kiếm
void Menu(TREE &t)
{
int luachon;
while(true)
{
cout << "\n\n\t\t ============ MENU ============";
cout << "\n1. Nhập phần tử cho cây";
cout << "\n2. Duyệt cây";
cout << "\n3. Giá trị MAX";
cout << "\n4. Giá trị MIN";
cout << "\n0. Thoát";
cout << "\n\n\t\t ============= END =============";
cout << "\nNhập lựa chọn của bạn: ";
cin >> luachon;
if (luachon == 1)
{
int x;
cout << "\nNhập giá trị: ";
cin >> x;
ThemNodeVaoCay(t, x);
}
else if (luachon == 2)
{
cout << "\nCây nhị phân tìm kiếm\n";
NLR(t);
}
else if (luachon == 3)
{
cout << "\nGiá trị MAX: "<<TimMax(t);
}
else if (luachon == 4)
{
cout << "\nGiá trị MAX: "<<TimMin(t);
}
else
{
break;
}
}
}
int main()
{
TREE t;
KhoiTaoCay(t);
Menu(t);
cout<<"\n---------------------------------\n";
cout<<"Chương trình này được đăng tại codehow.net";
}Kết quả:
