Đi ngang có nghĩa là đến thăm tất cả các nút của cây. Có ba phương pháp tiêu chuẩn để duyệt qua các Binary Trees. Những điều này như sau:
- Preorder Traversal
- Postorder Traversal
- Inorder Traversal
Các bài viết liên quan:
Preorder Traversal: Việc duyệt trước của Binary Trees là một quá trình đệ quy. Quá trình đi ngang của cây được đặt hàng trước là:
- Thăm Root.
- Duyệt cây con bên trái theo thứ tự trước.
- Duyệt qua cây con bên phải theo thứ tự trước.
Postorder Traversal: Truyền qua thứ tự của Binary Trees là một quá trình đệ quy. Đường đi ngang qua thứ tự bưu điện của một cái cây là:
- Di chuyển qua cây con bên trái theo thứ tự.
- Duyệt cây con bên phải trong thứ tự.
- Thăm Root.
Inorder Traversal: Inorder Traversal của Binary Trees là một quá trình đệ quy. Đường đi ngang qua không gian của một cái cây là:
- Đi ngang trong inorder cây con bên trái.
- Thăm gốc cây.
- Di chuyển trong inorder cây con bên phải.
Ví dụ: Xác định thứ tự trước, thứ tự đặt hàng sau và truyền qua thứ tự của Binary Trees như thể hiện trong hình:
Giải pháp: Việc đặt preorder, postorder và inorder traversal như sau:
Các thuật toán:
(a) Thuật toán để vẽ Binary Trees duy nhất khi Inorder và Preorder của cây được Cho:
- Chúng ta biết rằng gốc của Binary Trees là nút đầu tiên trong preorder của nó. Vẽ Root của cây.
- Để tìm nút con bên trái của nút gốc, trước tiên, hãy sử dụng phương thức truyền tải nhỏ hơn để tìm các nút trong cây con bên trái của Binary Trees. (Tất cả các nút được để lại cho nút gốc trong trình duyệt inorder là các nút của cây con bên trái). Sau đó, nút con bên trái của gốc thu được bằng cách chọn nút đầu tiên trong đường truyền đặt trước của cây con bên trái. Vẽ con bên trái.
- Theo cách tương tự, sử dụng duyệt nhỏ hơn để tìm các nút trong cây con bên phải của Binary Trees. Sau đó, thu được nút con bên phải bằng cách chọn nút đầu tiên trong đường duyệt đặt trước của cây con bên phải. Vẽ đúng con.
- Lặp lại các bước 2 và 3 với mỗi nút mới cho đến khi mọi nút không được truy cập trong đơn preorder. Cuối cùng, chúng tôi có được một cây độc nhất.
Ví dụ: Vẽ Binary Trees duy nhất khi trình duyệt inorder và preorder được cho như sau:
Inorder B A D C F E J H K G I
preorder A B C D E F G H J K I
Giải pháp: Chúng ta biết rằng gốc của Binary Trees là nút đầu tiên trong trình duyệt đặt hàng trước. Bây giờ, hãy kiểm tra A, trong trình duyệt nhỏ hơn, tất cả các nút ở bên trái A, là nút của cây con bên trái và tất cả các nút bên phải của A, là nút của cây con bên phải. Đọc nút tiếp theo trong đơn đặt hàng trước và kiểm tra vị trí của nó so với nút gốc, nếu nút bên trái của nút gốc, sau đó vẽ nó là nút con bên trái, nếu không thì vẽ nó là nút con bên phải. Lặp lại quá trình trên cho mỗi nút mới cho đến khi tất cả các nút của trình duyệt đặt hàng trước được đọc và cuối cùng chúng ta thu được Binary Trees như trong hình:
(b) Thuật toán để vẽ Binary Trees duy nhất khi duyệt Inorder và Post order của cây được Cho:
Chúng ta biết rằng gốc của Binary Trees là nút cuối cùng trong postorder của nó. Vẽ root của cây.
Để tìm nút con bên phải của nút gốc, trước tiên, hãy sử dụng phương pháp duyệt nhỏ hơn để tìm các nút trong cây con bên phải của Binary Trees. (Tất cả các nút nằm ngay bên phải nút gốc trong trình duyệt nhỏ hơn là các nút của cây con bên phải). Sau đó, nút con bên phải của gốc được lấy bằng cách chọn nút cuối cùng trong đường duyệt preorder của cây con bên phải.
Theo cách tương tự, sử dụng trình duyệt nhỏ hơn để tìm các nút trong cây con bên trái của Binary Trees. Sau đó, nút con bên trái được lấy bằng cách chọn nút cuối cùng trong chuyển vị trí thứ tự của cây con bên trái. Vẽ con bên trái.
Lặp lại các bước 2 và 3 với mỗi nút mới cho đến khi mọi nút không được truy cập trong thứ tự đăng. Sau khi truy cập vào nút cuối cùng, chúng tôi có được một cây duy nhất.
Ví dụ: Vẽ Binary Trees duy nhất cho đường truyền Inorder và Postorder đã cho được đưa ra như sau:
Inorder
4
6
10
12
số 8
2
1
5
7
11
13
9
3
Postorder
12
10
số 8
6
4
2
13
11
9
7
5
3
1
Giải pháp: Chúng ta biết rằng gốc của Binary Trees là nút cuối cùng trong trình duyệt thứ tự sau. Do đó, một trong nút gốc.
Bây giờ, hãy kiểm tra trình duyệt inorder, chúng ta biết rằng gốc nằm ở trung tâm, do đó tất cả các nút được để lại cho nút gốc trong chuyển ngang không hợp lệ là các nút của cây con bên trái và tất cả những gì nằm ngay với nút gốc là các nút của cây con bên phải.
Bây giờ, hãy truy cập vào nút tiếp theo từ phía sau trong duyệt inorder và kiểm tra vị trí của nó trong trình duyệt nhỏ hơn, nếu nó nằm ở bên trái của gốc thì vẽ nó làm nút con bên trái và nếu nó ở bên phải, thì vẽ nó làm nút con bên phải.
Lặp lại quá trình trên cho mỗi nút mới và chúng ta thu được Binary Trees như trong hình:
(c) Thuật toán chuyển đổi Cây chung thành Binary Trees
- Bắt đầu từ nút gốc, gốc của t
- cũng là gốc của Binary Trees.
- Child C1(from left) của nút gốc trong cây là con bên trái C1 của nút gốc trong Binary Trees, và anh chị em của C1 là con bên phải của C1, v.v.
- Lặp lại bước 2 cho mỗi nút mới.
Ví dụ: Chuyển cây sau đây như trong hình thành Binary Trees.
Bài giải: Rễ cây là rễ của Binary Trees. Do đó A là gốc của Binary Trees. Bây giờ B trở thành con trái của A trong Binary Trees, C trở thành con phải của B, D trở thành con phải của C và E trở thành con phải của D trong Binary Trees và áp dụng tương tự thuật toán ta thu được Binary Trees như được hiển thị trong hình:
