Như đã đề cập ở bài đầu tiên trong loạt bài về cấu trúc dữ liệu cây. Khi làm việc với cấu trúc dữ liệu cây ta thường làm việc với cây nhị phân. Tuy nhiên, để làm việc một cách dễ dàng hơn với cây nhị phân bạn đọc hãy chắc chắn đã nắm được vững những khái niệm và tính chất của một cây tổng quát ở bài 1.

1.Cây nhị phân và cây nhị phân tìm kiếm

1.1 Cây nhị phân là gì?

Cây nhị phân là cây mà mỗi nút chỉ có tối đa 2 cây con. Cây nhị phân cũng là cấu trúc thường gặp nhất trong cấu trúc cây. Một cây tổng quát hoàn toàn có thể được biểu diễn thông qua cây nhị phân.

Ngoài cây nhị phân thông thường ra, tồn tại một dạng đặc biệt của cây nhị phân đó là cây nhị phân tìm kiếm. Chúng ta sẽ làm việc chủ yếu trên cây nhị phân tìm kiếm!

1.2 Cây nhị phân tìm kiếm là gì?

Cây nhị phân tìm kiếm (BST) là một dạng đặc biệt của cây nhị phân trong đó thỏa mãn theo nguyên tắc:

Cây nhị phân tìm kiếm ứng với n khóa k1, k2, k3…kn là cây nhị phân mà mỗi nút đều được gán một khóa sao cho với mỗi một nút k:

  • Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút k
  • Mọi khóa trên cây con phải đều lớn hơn khóa trên nút k

Các phép toán trên cây nhị phân tìm kiếm:

  • Chèn phần tử vào cây
  • Duyệt cây
  • Xóa phần tử
  • Tìm kiếm phần tử
  • Sắp xếp

Các phép toán trên được nêu rõ hơn trong những bài tiếp theo, trong bài này ta sẽ cùng cài đặt cấu trúc cây để tiện thao tác với những phép toán ở trên!

2.Một số tính chất cây nhị phân

Dưới đây là một số tính chất của cây nhị phân:

  • Số nút nằm ở mức i ≤ 2i
  • Chiều cao của cây là mức cao nhất + 1.
  • Chiều cao của cây ≥ log2 (số nút trong cây)
  • Số nút lá ≤ 2h-1, với h là chiều cao của cây
  • Số nút trong ≤ 2h-1
  • Đường đi (path): Tên các nút của quá trình đi từ nút gốc theo các cây con đến một nút nào đó

3.Biểu diễn cây nhị phân tìm kiếm bằng C/C++

3.1 Biểu diễn cây nhị phân thông qua node

Để biểu diễn cây nhị phân trong C/C++ ta cần có một node bao gồm các thành phần đó là: thành phần dữ liệu của node, thành phần địa chỉ nút gốc của cây con trái trong bộ nhớ và thành phần địa chỉ nút gốc của cây con phải trong bộ nhớ.

Trong hình trên:

  • A, B, C, D, E G là thành phần dữ liệu của node.
  • Các node luôn có 2 con trỏ để trỏ đến cây con trái và cây con phải.
  • Trong trường hợp không tồn tại cây con trái (hoặc cây con phải) của 1 node thì con trỏ của node đó sẽ được trỏ về giá trị NULL

Đoạn code dưới đây sẽ giúp ta khai báo một node trong cây nhị phân bằng C/C++

typedef struct Node{
    //khai bao du lieu cua node co kieu du lieu int
    int data;
    //khai bao con tro den cay con trai
    Node* left;
    //khai bao con tro den cay con phai
    Node* right;
};
typedef struct Node* Tree;
Tree root;

3.2 Hàm khởi tạo cây nhị phân

Cây nhị phân khi mới được khởi tạo sẽ chưa có node nào vì vậy việc khởi tạo cây chỉ đơn giản là ta sẽ gán cho con trỏ quản lý node gốc (hay root) của cây về giá trị NULL.

void Init (Tree &root){  
    //gan node goc ve NULL
    root = NULL;
}

3.3 Hàm tạo một node mới trong cây nhị phân

Như đã đề cập ở phần trên, một node của cây nhị phân bao gồm: thành phần dữ liệu của node, thành phần địa chỉ nút gốc của cây con trái trong bộ nhớ và thành phần địa chỉ nút gốc của cây con phải trong bộ nhớ. Vì vậy mà ta cần có một hàm tạo node để khai báo các thành phần trên.

Node* CreateNode (int x){
    //tao node moi
    Node* p = new Node;
    //neu node p duoc cap phat bo nho
    if (p != NULL){
        //gan cay con trai va cay con phai mac dinh bang NULL
        p->left = NULL;
        p->right = NULL;
        //gan data bang x
        p->data = x;
    }
    //tra ve node p
    return p;
}

4.Chương trình hoàn chỉnh cài đặt cây nhị phân bằng C/C++

Chương trình dưới đây sử dụng lại tất cả các hàm trên để đưa ra một chương trình hoàn chỉnh về việc cài đặt cây nhị phân trong C/C++

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    //khai bao du lieu cua node co kieu du lieu int
    int data;
    //khai bao con tro den cay con trai
    Node* left;
    //khai bao con tro den cay con phai
    Node* right;

};
typedef struct Node* Tree;
Tree root;

void Init (Tree &root){   
    //gan node goc ve NULL
    root = NULL;
}

Node* CreateNode (int x){
    //tao node moi
    Node* p = new Node;
    //neu node p duoc cap phat bo nho
    if (p != NULL){
        //gan cay con trai va cay con phai mac dinh bang NULL
        p->left = NULL;
        p->right = NULL;
        //gan data bang x
        p->data = x;
    }
    //tra ve node p
    return p;
}
int main(){
    //tao cay voi node goc la root
    Tree root;
    //khoi tao cay
    Init(root);
}

Chú ý rằng, chương trình dưới đây chỉ dừng lại ở mức cài đặt một cấu trúc cây. Các thao tác với cây nhị phân sẽ được nêu rõ hơn ở những bài tiếp theo!