Traversal Là Gì

Duyệt cây trong cấu trúc dữ liệu và giải thuật là gì?

Duyệt cây là một tiến trình nhằm truy cập toàn bộ các nút của một cây với cũng hoàn toàn có thể in những giá trị của các nút này. Chính vì tất cả các nút được kết nối thông qua các cạnh (hoặc những link), nên chúng ta luôn luôn bước đầu truy cập tự nút gốc. Vày đó, bọn họ không thể truy vấn ngẫu nhiên ngẫu nhiên nút như thế nào trong cây. Có cha phương thức mà chúng ta có thể sử dụng để săn sóc một cây:

Duyệt tiền đồ vật tự (Pre-order Traversal)Duyệt trung trang bị tự (In-order Traversal)Duyệt hậu vật dụng tự (Post-order Traversal)

Nói chung, bọn họ duyệt một cây để tìm kiếm tốt là nhằm xác xác định trí bộ phận hoặc khóa đã mang đến trong cây hoặc là để in tất cả giá trị cơ mà cây đó chứa.

Bạn đang xem: Traversal là gì

Duyệt trung máy tự trong cây nhị phân

Trong cách duyệt này, cây nhỏ bên trái được truy cập đầu tiên, sau đó là nút nơi bắt đầu và kế tiếp là cây bé bên phải. Chúng ta nên luôn luôn luôn nhớ rằng mỗi nút đều hoàn toàn có thể biểu diễn một cây con.

Nếu một cây nhị phân được thông qua trung đồ vật tự, kết quả tạo ra sẽ là những giá trị khóa được bố trí theo máy tự tăng dần.

*

Ở hình lấy ví dụ như minh họa trên, A là nút gốc. Với thủ tục duyệt trung đồ vật tự, bọn chúng ta ban đầu từ nút gốc A, dịch rời tới cây con bên trái B của nút gốc. Tại đây, B cũng được duyệt theo phương pháp duyệt trung đồ vật tự. Và quá trình tiếp tục cho đến khi tất cả các nút đã làm được truy cập. Tác dụng của phương pháp duyệt trung máy tự đến cây trên đã là:

D → B → E → A → F → C → G

Giải thuật cho biện pháp duyệt trung sản phẩm công nghệ tự

Duyệt tính đến khi tất cả các nút các được duyệt:Bước 1: Duyệt các cây nhỏ bên trái một cách đệ quiBước 2: truy vấn nút gốcBước 3: Duyệt các cây nhỏ bên cần một giải pháp đệ quiĐể tìm hiểu code tương đối đầy đủ của phương pháp Duyệt cây trong ngôn từ C, mời bạn click chuột vào chương: Duyệt cây trong C.

Xem thêm: Live Là Gì Tiếng Việt - Live Nghĩa Là Gì Trong Tiếng Việt

Duyệt tiền trang bị tự trong cây nhị phân

Trong phương thức duyệt tiền sản phẩm tự trong cây nhị phân, nút gốc được chú tâm đầu tiên, sau đó sẽ để mắt tới cây nhỏ bên trái và cuối cùng sẽ chuẩn y cây bé bên phải.

*

Ở hình lấy một ví dụ minh họa trên, A là nút gốc. Bọn chúng ta bắt đầu từ A, và theo cách thức duyệt tiền đồ vật tự, đầu tiên chúng ta truy cập chủ yếu nút nơi bắt đầu A này cùng sau đó dịch chuyển tới nút nhỏ bên trái B của nó. B cũng rất được duyệt theo phương pháp duyệt tiền sản phẩm công nghệ tự. Và quy trình tiếp tục cho tới khi tất cả các nút những đã được truy nã cập. Tác dụng của phương thức duyệt tiền trang bị tự cây này vẫn là:

A → B → D → E → C → F → G

Giải thuật cho biện pháp duyệt tiền thứ tự

Duyệt cho tới khi tất cả các nút mọi được duyệt:Bước 1: truy vấn nút gốcBước 2: Duyệt các cây bé bên trái một giải pháp đệ quiBước 3: Duyệt các cây bé bên bắt buộc một bí quyết đệ quiĐể tìm hiểu code không thiếu của cách Duyệt cây trong ngôn ngữ C, mời bạn bấm vào vào chương: Duyệt cây trong C.

Duyệt hậu thiết bị tự vào cây nhị phân

Trong phương pháp duyệt hậu sản phẩm tự vào cây nhị phân, nút nơi bắt đầu của cây đang được truy vấn cuối cùng, do đó bạn đề nghị chú ý. Đầu tiên, bọn họ duyệt cây nhỏ bên trái, kế tiếp sẽ chu đáo cây nhỏ bên buộc phải và ở đầu cuối là duyệt y nút gốc.

*

Ở hình ví dụ minh họa trên, A là nút gốc. Chúng ta ban đầu từ A, và theo phong cách duyệt hậu lắp thêm tự, đầu tiên họ truy cập cây con bên trái B. B cũng khá được duyệt theo cách thứ phê duyệt hậu đồ vật tự. Và quy trình sẽ thường xuyên tới khi tất cả các nút đã được truy cập. Tác dụng của cách thức duyệt hậu vật dụng tự của cây con trên sẽ là:

D → E → B → F → G → C → A

Giải thuật cho giải pháp duyệt hậu sản phẩm tự

Duyệt cho tới khi tất cả các nút đầy đủ được duyệt:Bước 1: Duyệt các cây nhỏ bên trái một giải pháp đệ quiBước 2: Duyệt những cây bé bên yêu cầu một giải pháp đệ quiBước 3: truy vấn nút gốc.Để tò mò code không hề thiếu của biện pháp Duyệt cây trong ngôn từ C, mời bạn bấm vào vào chương: Duyệt cây vào C.