Hãy vẽ một cây nhị phân có chiều cao là 4; sau đó, xây dựng mảng một chiều để biểu diễn cây này.

Để vẽ một cây nhị phân có chiều cao là 4, chúng ta có thể làm như sau. Cây nhị phân có chiều cao 4 sẽ có các cấp từ 0 đến 4, với tối đa 15 nút (nếu đầy đủ). Dưới đây là một ví dụ về cây nhị phân đầy đủ với chiều cao 4:

Biểu diễn cây nhị phân này bằng mảng một chiều

Cây nhị phân có thể được biểu diễn bằng mảng một chiều theo cách thức sau:

• Nút gốc (root) ở vị trí 1.

• Nút con trái của nút tại vị trí i sẽ ở vị trí 2*i.

• Nút con phải của nút tại vị trí i sẽ ở vị trí 2*i + 1.

Dưới đây là mảng một chiều biểu diễn cây nhị phân trên:

Index:  0  1 2  3  4  5  6 7  8  9 10 11 12 13 14 15

Value: [ , A, B, C, D, E, F, G, H, I, J, K, L, M, N, O]

Trong đó:

• A là gốc và nằm ở vị trí 1.

• B là con trái của A và nằm ở vị trí 2.

• C là con phải của A và nằm ở vị trí 3.

• D là con trái của B và nằm ở vị trí 4.

• E là con phải của B và nằm ở vị trí 5.

• F là con trái của C và nằm ở vị trí 6.

• G là con phải của C và nằm ở vị trí 7.

• H là con trái của D và nằm ở vị trí 8.

• I là con phải của D và nằm ở vị trí 9.

• J là con trái của E và nằm ở vị trí 10.

• K là con phải của E và nằm ở vị trí 11.

• L là con trái của F và nằm ở vị trí 12.

• M là con phải của F và nằm ở vị trí 13.

• N là con trái của G và nằm ở vị trí 14.

• O là con phải của G và nằm ở vị trí 15.

Như vậy, cây nhị phân với chiều cao 4 được biểu diễn bởi mảng một chiều như trên.