Cộng đồng chia sẻ tri thức Lib24.vn

Cấu trúc dữ liệu & thuật toán - Traversal cây

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 14:04:13


Mục lục
* * * * *

Traversal là một quá trình để truy cập tất cả các nút của cây và cũng có thể in các giá trị của chúng. Bởi vì, tất cả các nút được kết nối thông qua các cạnh (liên kết), chúng tôi luôn bắt đầu từ nút gốc (đầu). Đó là, chúng ta không thể truy cập ngẫu nhiên một nút trong cây. Có ba cách chúng ta sử dụng để đi qua một cái cây -

  1. Theo thứ tự
  2. Đặt hàng trước
  3. Traversal sau đặt hàng

Nói chung, chúng tôi duyệt qua một cây để tìm kiếm hoặc định vị một mục hoặc khóa cụ thể trong cây hoặc để in tất cả các giá trị mà nó chứa.

Theo thứ tự

Trong phương thức truyền tải này, cây con bên trái được truy cập trước, sau đó là gốc và sau đó là cây con bên phải. Chúng ta nên luôn nhớ rằng mỗi nút có thể đại diện cho một cây con chính nó.

Nếu một cây nhị phân được duyệt theo thứ tự , đầu ra sẽ tạo ra các giá trị khóa được sắp xếp theo thứ tự tăng dần.

Cấu trúc dữ liệu & thuật toán - Traversal cây

Chúng tôi bắt đầu từ A , và sau traversal trong trật tự, chúng tôi chuyển sang cây con của nó trái B . B cũng được sắp xếp theo thứ tự. Quá trình diễn ra cho đến khi tất cả các nút được truy cập. Đầu ra của truyền tải thứ tự của cây này sẽ là -

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

Thuật toán

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Đặt hàng trước

Trong phương thức truyền tải này, nút gốc được truy cập trước, sau đó là cây con bên trái và cuối cùng là cây con bên phải.

Chúng tôi bắt đầu từ A và theo dõi giao dịch đặt hàng trước, trước tiên chúng tôi truy cập vào chính A và sau đó di chuyển sang cây con B bên trái của nó . B cũng được đặt hàng trước. Quá trình diễn ra cho đến khi tất cả các nút được truy cập. Đầu ra của giao dịch đặt hàng trước của cây này sẽ là -

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

Thuật toán

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Traversal sau đặt hàng

Trong phương thức truyền tải này, nút gốc được truy cập lần cuối, do đó có tên. Đầu tiên chúng ta đi qua cây con bên trái, sau đó là cây con bên phải và cuối cùng là nút gốc.

Chúng tôi bắt đầu từ A và theo dõi giao dịch sau khi đặt hàng, trước tiên chúng tôi truy cập vào cây con B bên trái . B cũng được đặt hàng sau khi đặt hàng. Quá trình diễn ra cho đến khi tất cả các nút được truy cập. Đầu ra của giao dịch sau đặt hàng của cây này sẽ là -

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

Thuật toán

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

Được cập nhật: 25 tháng 3 lúc 12:57:23 | Lượt xem: 603