Cấu trúc dữ liệu & thuật toán - Truyền qua cây
Traversal là một quá trình để truy cập tất cả các nút của cây và có thể in ra 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 ta luôn bắt đầu từ nút gốc (đầu). Tức là chúng ta không thể truy cập ngẫu nhiên vào một nút trong cây. Có ba cách mà chúng tôi sử dụng để đi qua một cái cây -
- Traversal theo thứ tự
- Đặt hàng trước Traversal
- Giao dịch sau đơn đặt hàng
Nói chung, chúng tôi đi qua một cây để tìm kiếm hoặc định vị một mục hoặc khóa nhất định trong cây hoặc để in tất cả các giá trị mà nó chứa.
Traversal theo thứ tự
Trong phương pháp duyệt này, cây con bên trái được truy cập đầu tiên, sau đó đến gốc và sau đó là cây con bên phải. Chúng ta nên nhớ rằng mỗi nút có thể đại diện cho chính một cây con.
Nếu một cây nhị phân được duyệt qua in-order, đầu ra sẽ tạo ra các giá trị khóa được sắp xếp theo thứ tự tăng dần.
Chúng tôi bắt đầu từ Avà theo dõi duyệt theo thứ tự, chúng tôi chuyển sang cây con bên trái của nó B. Bcũng được duyệt theo thứ tự. Quá trình tiếp tục cho đến khi tất cả các nút được truy cập. Đầu ra của việc đi ngang qua 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 Traversal
Trong phương pháp duyệt này, nút gốc được truy cập đầu tiên, sau đó đến 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ừ Avà sau khi duyệt đơn đặt hàng trước, trước tiên chúng tôi truy cập A chính nó và sau đó di chuyển sang cây con bên trái của nó B. Bcũng được duyệt qua đơn đặt hàng trước. Quá trình tiếp tục cho đến khi tất cả các nút được truy cập. Đầu ra của việc duyệt đơn đặ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.Giao dịch sau đơn đặt hàng
Trong phương thức truyền tải này, nút gốc được truy cập cuối cùng, do đó có tên. Đầu tiên chúng ta duyệt qua cây con bên trái, sau đó đến 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ừ Avà sau khi duyệt qua Đơn đặt hàng sau, trước tiên chúng ta truy cập vào cây con bên trái B. Bcũng được duyệt qua đơn hàng sau. Quá trình tiếp tục cho đến khi tất cả các nút được truy cập. Kết quả của việc duyệt sau đơn 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.Để kiểm tra việc triển khai C của việc duyệt cây, vui lòng nhấp vào đây .