Binary Tree đại diện sử dụng mảng

Question

Hãy xem xét các mảng sau đây, được tuyên bố đã đại diện cho một cây nhị phân:

[1, 2, 5, 6, -1, 8, 11]

Cho rằng các chỉ số có giá trị -1 cho biết phần tử gốc, tôi đã ở dưới câu hỏi:

a) Điều này thực sự được thể hiện như thế nào?

Chúng ta có nên theo công thức dưới đây (source from this link) để tìm ra cây không? Ba công thức đơn giản cho phép bạn đi từ các chỉ số phụ huynh đến các chỉ số của con của nó và ngược lại:

* if index(parent) = N, index(left child) = 2*N+1 
* if index(parent) = N, index(right child) = 2*N+2 
* if index(child) = N, index(parent) = (N-1)/2 (integer division with truncation) 

Nếu chúng ta sử dụng công thức trên, sau đó chỉ số (root) = 3, chỉ số (con bên trái) = 7, không tồn tại.

b) Điều quan trọng là phải biết đó là cây nhị phân hoàn chỉnh hay không?

Answer 1

Cho một mảng, bạn có thể nghĩ ra bất kỳ số cách nào để mảng đó đại diện cho cây nhị phân. Vì vậy, không có cách nào để biết, bạn phải đi đến nguồn gốc của mảng đó (bất kể đó là gì).

Một trong những cách đó là cách đống nhị phân thường được biểu diễn, theo liên kết của bạn. Nếu đây là biểu diễn được sử dụng, -1 sẽ không phải là phần tử gốc. Và nút ở vị trí 3 sẽ không có con, nghĩa là nó sẽ là một chiếc lá.

Và, vâng, điều quan trọng là phải biết liệu đó có phải là cây hoàn chỉnh hay không.

Nói chung, bạn không nên cố gắng tìm ra một số dữ liệu có ý nghĩa như thế nào. Bạn sẽ được cung cấp tài liệu hoặc mã nguồn sử dụng dữ liệu. Nếu bạn không có điều đó và bạn thực sự cần phải đảo ngược kỹ sư, bạn có thể cần biết nhiều hơn về dữ liệu. Quan sát hành vi của mã sử dụng nó sẽ giúp bạn. Hoặc dịch ngược mã.

Answer 2

Nó có thể không phải là một cây nhị phân hoàn chỉnh, nhưng nó có thể không phải là một tùy ý. Bạn có thể đại diện cho một cái cây, trong đó ít nhất một vài lá ngoài cùng bên phải còn thiếu (hoặc, nếu bạn trao đổi quy ước cho trẻ em trái và phải, ít nhất một số lá còn lại ở bên trái còn thiếu).

Bạn không thể đại diện này trong mảng của bạn:

A 
/\ 
    B C 
//
D E 

Nhưng bạn có thể đại diện này

A 
/\ 
    B C 
/\ 
D E 

hay này:

A 
/\ 
    B C 
    /\ 
    D E 

(cho qua, có 2k +1 là ngay trẻ em và 2k + 2 số bên trái con)

Bạn chỉ cần biết số lượng nút trong ba.

Answer 3

N = 0 phải là nút gốc do các quy tắc được liệt kê, nó không có cha mẹ. Không thể tạo 0 từ một trong hai biểu thức (2 * N + 1) hoặc (2 * N + 2), giả sử không có âm N.

Lưu ý, chỉ mục không phải là giá trị được lưu trữ trong mảng, đó là vị trí trong mảng. Đối [1, 2, 5, 6, -1, 8, 11] Index 0 = 1 Index 1 = 2 Index 2 = 5 vv

Nếu nó là một cây hoàn chỉnh, sau đó -1 là một giá trị và cây hợp lệ là

1 
/\ 
    2 5 
/\/\ 
6 -1 8 11 

-1 cũng có thể là con trỏ "NULL", cho biết không có giá trị tồn tại ở nút đó.

Vì vậy, cây sẽ trông như thế

1 
/\ 
    2 5 
//\ 
6 8 11