Ở đây chúng ta sẽ xem cách biểu diễn một cây nhị phân trong bộ nhớ máy tính. Có hai phương pháp khác nhau để biểu diễn. Chúng đang sử dụng mảng và sử dụng danh sách được liên kết.
Giả sử chúng ta có một cây như thế này -
Biểu diễn mảng lưu trữ dữ liệu cây bằng cách quét các phần tử sử dụng thời trang thứ tự mức. Vì vậy, nó lưu trữ các nút theo cấp độ. Nếu một số phần tử bị thiếu, nó sẽ để lại khoảng trống cho phần tử đó. Hình đại diện của cây trên giống như bên dưới -
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 10 | 5 | 16 | - | 8 | 15 | 20 | - | - | - | - | - | - | - | 23 |
Chỉ số 1 đang giữ gốc, nó có hai con 5 và 16, chúng được đặt ở vị trí 2 và 3. Thiếu một số con nên vị trí của chúng bị bỏ trống.
Trong biểu diễn này, chúng ta có thể dễ dàng nhận được vị trí của hai nút con của một nút bằng cách sử dụng công thức này -
$$ child_ {1} =2 * cha $$
$$ child_ {2} =\ lgroup2 * parent \ rgroup + 1 $$
Để lấy chỉ mục mẹ từ con, chúng ta phải làm theo công thức này -
$$ parent =\ begin {bmatrix} \ frac {child} {2} \ end {bmatrix} $$
Cách tiếp cận này là tốt, và chúng ta có thể dễ dàng tìm thấy chỉ mục của cha và con, nhưng nó không hiệu quả về bộ nhớ. Nó sẽ chiếm nhiều không gian mà không có sử dụng. Cách biểu diễn này phù hợp với cây nhị phân hoàn chỉnh hoặc cây nhị phân đầy đủ.
Một cách tiếp cận khác là sử dụng danh sách liên kết. Chúng tôi tạo nút cho mỗi phần tử. Nó sẽ giống như bên dưới -
