Câu hỏi
Phương án nào sau đây biểu diễn duyệt cây theo hậu thứ tự (post-order) của cây bên dưới?
Lời giải
Cây là gì?
Cây là một cấu trúc dữ liệu mô phỏng lại hình dáng của một cây thông thường trong thực tế. Một cây gồm có:
- Nút gốc: Là nút đầu tiên, đây là nút duy nhất không có nút cha, ví dụ như hình trong câu hỏi thì nút gốc là 10.
- Cây con: Là các cây nằm bên trái hoặc phải nút gốc.
- Nút cha: Là các nút không phải là nút gốc nhưng có các nút con, ví dụ như hình trong câu hỏi thì nút cha là 3, 7, 13, 18.
- Nút lá: Là các nút không có nút con nào, ví dụ như hình trong câu hỏi thì nút lá là: 2, 4, 8, 15.
Duyệt cây là gì?
Là hành động duyệt qua tất cả các nút có trong cây, có 3 cách duyệt cây:
Duyệt cây theo hậu thứ tự (post-order)
Là một phương pháp duyệt cây nhị phân trong đó các nút được thăm theo thứ tự: trái - phải - gốc. Điều này có nghĩa là bạn sẽ thăm tất cả các nút con của một nút trước khi thăm chính nó. Cụ thể:
- Bắt đầu từ nút gốc.
- Duyệt cây con bên trái: Đi qua toàn bộ nhánh bên trái của cây con.
- Duyệt cây con bên phải: Đi qua toàn bộ nhánh bên phải của cây con.
- Duyệt nút gốc: Sau khi đã duyệt xong cả hai cây con, thăm nút gốc.
Quay trở lại câu hỏi
Dựa trên lý thuyết, chúng ta có thể áp dụng vào để trả lời câu hỏi như sau:
Duyệt hậu thứ tự:
- Duyệt nút: 10
- Duyệt nút bên trái: 3 của nút 10
- Duyệt nút: 3
- Duyệt nút bên trái: 2 của nút 3
- Duyệt nút: 2
Thăm: 2, đã thăm: [2] - Duyệt nút bên phải: 7 của nút 3
- Duyệt nút: 7
- Duyệt nút bên trái: 4 của nút 7
- Duyệt nút: 4
Thăm: 4, đã thăm: [2, 4] - Duyệt nút bên phải: 8 của nút 7
- Duyệt nút: 8
Thăm: 8, đã thăm: [2, 4, 8]
Thăm: 7, đã thăm: [2, 4, 8, 7]
Thăm: 3, đã thăm: [2, 4, 8, 7, 3] - Duyệt nút bên phải: 13 của nút 10
- Duyệt nút: 13
- Duyệt nút bên phải: 18 của nút 13
- Duyệt nút: 18
- Duyệt nút bên trái: 15 của nút 18
- Duyệt nút: 15
Thăm: 15, đã thăm: [2, 4, 8, 7, 3, 15]
Thăm: 18, đã thăm: [2, 4, 8, 7, 3, 15, 18]
Thăm: 13, đã thăm: [2, 4, 8, 7, 3, 15, 18, 13]
Thăm: 10, đã thăm: [2, 4, 8, 7, 3, 15, 18, 13, 10]
Đáp án cuối cùng là: 2, 4, 8, 7, 3, 15, 18, 13, 10
Mã nguồn Java minh hoạ:
package com.tvd12.example.tree;
import java.util.ArrayList;
import java.util.List;
class Node {
int value;
Node left, right;
public Node(int value) {
this.value = value;
left = right = null;
}
@Override
public String toString() {
return String.valueOf(value);
}
}
public class BinaryTree {
Node root;
private static int step = 0;
private static List<Node> accessedNodes = new ArrayList<>();
void postorderTraversal(Node node) {
System.out.println((++step) + ". Duyệt nút: " + node);
if (node.left != null) {
System.out.println((++step) + ". Duyệt nút bên trái: " + node.left + " của nút " + node);
postorderTraversal(node.left);
}
if (node.right != null) {
System.out.println((++step) + ". Duyệt nút bên phải: " + node.right + " của nút " + node);
postorderTraversal(node.right);
}
System.out.print("Thăm: " + node);
accessedNodes.add(node);
System.out.println(", đã thăm: " + accessedNodes);
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(10);
tree.root.left = new Node(3);
tree.root.right = new Node(13);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(7);
tree.root.left.right.left = new Node(4);
tree.root.left.right.right = new Node(8);
tree.root.right.right = new Node(18);
tree.root.right.right.left = new Node(15);
System.out.println("Duyệt hậu thứ tự: ");
tree.postorderTraversal(tree.root);
}
}
Tổng kết lại
Như vậy chúng ta đã cùng nhau trả lời câu hỏi về duyệt cây nhị phân.
Cám ơn bạn đã quan tâm đến bài viết|video này. Để nhận được thêm các kiến thức bổ ích bạn có thể:
- Đọc các bài viết của TechMaster trên facebook: https://www.facebook.com/techmastervn
- Xem các video của TechMaster qua Youtube: https://www.youtube.com/@TechMasterVietnam nếu bạn thấy video/bài viết hay bạn có thể theo dõi kênh của TechMaster để nhận được thông báo về các video mới nhất nhé.
- Chat với techmaster qua Discord: https://discord.gg/yQjRTFXb7a
Bình luận