Chúng ta được cho thứ tự Inorder và Preorder của một cây nhị phân. Mục tiêu là xây dựng cây từ các thứ tự duyệt đã cho.
Duyệt Inorder − Trong loại duyệt cây này, cây con trái được duyệt trước, theo sau là nút và cuối cùng là cây con phải.
Inorder (tree root)
- Duyệt cây con trái của nút trỏ bởi root, gọi inorder(root->left).
- Ghé thăm root.
- Duyệt cây con phải của nút trỏ bởi root, gọi inorder(root->right).
Duyệt Preorder − Trong loại duyệt này, nút được ghé thăm trước, theo sau là cây con trái và cuối cùng là cây con phải.
Preorder (tree root)
- Ghé thăm root.
- Duyệt cây con trái của nút trỏ bởi root, gọi inorder(root->left).
- Duyệt cây con phải của nút trỏ bởi root, gọi inorder(root->right).
Thứ tự Inorder và Preorder của cây dưới đây được cho:
Inorder
2-3-4-5-6-8-10
Preorder
4-3-2-5-8-6-10
Bây giờ chúng ta sẽ xây dựng lại cây trên từ preorder và inorder đã cho.
Inorder
2-3-4-5-6-8-10
Preorder
5-3-2-4-8-6-10
- Như chúng ta biết preorder ghé thăm nút gốc trước, nên giá trị đầu tiên luôn đại diện cho gốc của cây. Từ chuỗi trên, 5 là gốc của cây.
Preorder
5 -3-2-4-8-6-10
- Từ inorder, chúng ta biết cây con trái của một nút được duyệt trước nó, theo sau là cây con phải. Do đó, tất cả giá trị bên trái của 5 trong inorder thuộc cây con trái và tất cả giá trị bên phải thuộc cây con phải.
Inorder
2-3-4 ← 5 → 6-8-10
- Bây giờ làm tương tự cho cây con trái.
Preorder của cây con trái là 3-2-4. Vậy 3 trở thành gốc.
Inorder chia thêm thành 2 ← 3 → 4.
- Bây giờ làm tương tự cho cây con phải.
Preorder của cây con phải là 8-6-10. Vậy 8 trở thành gốc.
Inorder chia thêm thành 6 ← 8 → 10.
Vậy, theo cách này chúng ta đã xây dựng lại cây gốc từ preorder và inorder đã cho.