Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Thêm Node vào cây nhị phân tìm kiếm
Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu của cây nhị phân tìm kiếm và cách thêm một Node vào cây nhị phân tìm kiếm.
Chúng ta sẽ tìm hiểu lần lượt về cấu trúc một Node trong cây và khởi tạo cho cây như thế nào. Sau đó sẽ thực hiện thêm Node vào cây.
1. Cấu trúc dữ liệu của cây nhị phân tìm kiếm
Như các bạn đã học ở bài trước thì cây nhị phân tìm kiếm là một cấu trúc dữ liệu, vì vậy ta cần khởi tạo cấu trúc dữ liệu cho nó. Trong phần này ta có khởi tạo cấu trúc của một Node và khởi tạo cây.
Khởi tạo Node
Trong một Node ta có ba thành phần như sau:
Bài viết này được đăng tại [free tuts .net]
- Data là giá trị của Node
- pLeft là con trỏ trỏ đến cây con bên trái Node
- pRight là con trỏ trỏ đến cây con bên phải Node
struct node
{
int data; // dữ liệu của node ==> dữ liệu mà node sẽ lưu trữ
struct node *pLeft; // node liên kết bên trái của cây <=> cây con trái
struct node *pRight; // node liên kết bên phải của cây <=> cây con phải
};Khởi tạo cây
Để làm việc được với cây ta cần khởi tạo cây và gán giá trị cho nó như danh sach liên kết đơn vậy.
Chúng ta sẽ tạo một cây t có tham số truyền vào cho hàm khởi tạo cây là một con trỏ *Node (đây là node vừa được khởi tạo ở trên). Trong hàm KhoiTaoCay() ta thực hiện cho khởi tạo cây bằng rỗng: t = null
/* khởi tạo cây */
void KhoiTaoCay(TREE &t)
{
t = NULL; // cây rỗng
}2. Thêm Node vào cây nhị phân tìm kiếm
Sau khi chúng ta đã tạo cấu trúc dữ liệu cho cây, ta sẽ thực hiện thêm Node vào cây nhị phân tìm kiếm.
Trong hàm ThemNodeVaoCay() ta truyền hai tham số là cây t và Node x.
Để thêm Node mới vào cây ta cần xét hai trường hợp:
Trường hợp 1: Trong cây không có phần tử nào (cây rỗng).
Ta sử dụng struct dode tạo một Node mới để thêm vào cây, sau đó thêm dữ liệu x vào data (p->data = x).
Khởi tạo cho con trỏ pLeft và pRight bằng Null. Vì cây ban đầu không có phân tử nào, vì vậy phần tử đầu tiên khi thêm vào chính là phần tử gốc t = p
Trường hợp 2: Trong cây có tồn tại phần tử.
Khi này trong cây đã có phần tử, cũng như đã có phần tử gốc (root). Vì vậy khi ta thêm Node mới vào cần so sánh Node này với Node gốc để có thể thêm chính xác vị trí cần thêm.
Như ta đã học ở bài trước thì một phần tử khi được thêm vào nếu nhỏ hơn phần tử gốc thì nằm ở bên cây con trái và nếu lớn hơn phần tử gốc thì nằm ở bên cây con phải.
Trong trường hợp này ta sẽ sử dụng đệ quy để thực hiện gọi lại hàm ThemNodeVaoCay() duyệt qua trái để thêm phần tử x nếu x < root và duyệt qua phải nếu x > root
/* hàm thêm phần tử x vào cây nhị phân */
void ThemNodeVaoCay(TREE &t, int x)
{
// nếu cây rỗng
if (t == NULL)
{
NODE *p = new NODE; // khởi tạo 1 cái node để thêm vào cây
p->data = x;// thêm dữ liệu x vào data
p->pLeft = NULL;
p->pRight = NULL;
t = p;// node p chính là node gốc <=> x chính là node gốc
}
else // cây có tồn tại phần tử
{
// nếu phần tử thêm vào mà nhỏ hơn node gốc ==> thêm nó vào bên trái
if (t->data > x)
{
ThemNodeVaoCay(t->pLeft, x); // duyệt qua trái để thêm phần tử x
}
else if (t->data < x) // nếu phần tử thêm vào mà lớn hơn node gốc ==> thêm nó vào bên phải
{
ThemNodeVaoCay(t->pRight, x); // duyệt qua phải để thêm phần tử x
}
}
}3. Kết luận
Như vậy là chúng ta đã tìm hiểu xong về cấu trúc dữ liệu của cây nhị phân tìm kiếm, cũng như cách thêm một Node vào cây. Đây là bước đầu tiên để tạo dữ liệu cho cây. Ở bài tiếp theo mình sẽ thực hiện duyệt cây để có thể kiếm tra được các thao tác của ta trên cây đúng hay sai. Các bạn chú ý theo dõi nhé!!
