Câu hỏi:

01/10/2024 159

Cho mảng số nguyên dương A = [5, 8, 7, 4, 9, 2).

a) Xây dựng cây nhị phân với mảng số nguyên dương trên.

b) Sử dụng phép toán duyệt trước, duyệt giữa, duyệt sau để xuất thứ tự các giá trị trên

cây nhị phân được xây dựng ở câu a).

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

Cho mảng số nguyên dương A = [5, 8, 7, 4, 9, 2).

a) Xây dựng cây nhị phân với mảng số nguyên dương: A = [5, 8, 7, 4, 9, 2).

- Phần tử đầu tiên 5 là gốc.

- lớn hơn 5, đặt vào cây con phải của 5.

- 7 nhỏ hơn 8, đặt vào cây con trái của 8.

- 4 nhỏ hơn 5, đặt vào cây con trái của 5.

- 9 lớn hơn 8, đặt vào cây con phải của 8.

- 2 nhỏ hơn 4, đặt vào cây con trái của 4.

                        Media VietJack

b) Sử dụng phép toán duyệt trước, duyệt giữa, duyệt sau để xuất thứ tự các giá trị trên cây nhị phân được xây dựng ở câu a).

- Duyệt trước (Pre-order traversal):

Duyệt nút gốc -> Duyệt cây con trái -> Duyệt cây con phải

Thứ tự: 5 -> 4 -> 2 -> 8 -> 7 -> 9

- Duyệt giữa (In-order traversal):

Duyệt cây con trái -> Duyệt nút gốc -> Duyệt cây con phải

Thứ tự: 2 -> 4 -> 5 -> 7 -> 8 -> 9

- Duyệt sau (Post-order traversal):

Duyệt cây con trái -> Duyệt cây con phải -> Duyệt nút gốc

Thứ tự: 2 -> 4 -> 7 -> 9 -> 8 -> 5

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

Mảng một chiều để biểu diễn các giá trị trong cây nhị phân như sau:

[2, 24, 11, None, 3, 8, 9]

Lời giải

Cách biểu diễn các giá trị của cây bằng mảng một chiều theo ba phép duyệt:

a) Duyệt trước (Pre-order): Thăm nút gốc trước, sau đó là cây con bên trái và cuối cùng là cây con bên phải. [20,24,14,None,None,None,None,None,None,None,None]

b) Duyệt giữa (In-order): Thăm cây con bên trái trước, sau đó là nút gốc và cuối cùng là cây con bên phải. None,None,None,None]

c) Duyệt sau (Post-order): Thăm cây con bên trái trước, sau đó là cây con bên phải và kết thúc ở nút gốc. [None]

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP