Ninja IT

Cây nhị phân

Cây nhị phân

Cây là một cấu trúc dữ liệu liên kết giữa node cha xuống node con. Cây nhị phân là cây mà mỗi nút chỉ có hai nút con.

Biểu diễn cây nhị phân

Có hai cách thường dùng để biểu diễn cây nhị phân là sử dụng liên kết hoặc sử dụng mảng.
Ví dụ cây như sau được biểu diễn bằng bảng:

    50
   ↙  ↘
  30   90
  ↙↘   ↙↘
20 40 1 100

1
2

// index    0   1   2   3   4   5   6
int a[] = { 50, 30, 90, 20, 40, 1, 100 };

Ta có sẽ sắp xếp một cây theo từng hàng từ trái qua phải. Hàng đầu có 1 phần tử, hàng hai có 2 phần tử, hàng thứ ba có 4 phần tử, hàng thứ n có n*2 phần tử.
Phần tử thứ i có 2 con là 2*i + 1 và 2*i + 2.

Biểu diễn cây nhị phân sử dụng liên kết

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

typedef struct Node {
  int data;
  struct Node* left;
  struct Node* right;
} Node;

int main() {
  Node node1 = {.data = 50};
  Node node2 = {.data = 30};
  Node node3 = {.data = 90};
  Node node4 = {.data = 20, .left = NULL, .right = NULL};
  Node node5 = {.data = 40, .left = NULL, .right = NULL};
  Node node6 = {.data = 1, .left = NULL, .right = NULL};
  Node node7 = {.data = 100, .left = NULL, .right = NULL};

  node1.left = &node2;
  node1.right = &node3;

  node2.left = &node4;
  node2.right = &node5;

  node3.left = &node6;
  node3.right = &node7;
}

Duyệt cây nhị phân

Có 3 loại gồm in thứ tự trước, thứ tự giữa và thứ tự sau.
Ví dụ về in các phần tử thứ tự trước sẽ in ra 50 30 20 40 90 1 100

1
2
3
4
5
6
7
8

void printBinaryTree(Node* node) {
  if (node == NULL) {
    return;
  }
  printf("%d ", node->data);
  printBinaryTree(node->left);
  printBinaryTree(node->right);
}