Binary tree (cây nhị phân) là một cấu trúc phân cấp trong đó mỗi node có tối đa hai con (children), gọi là left và . Nó có một duy nhất; các node không có con là (lá). Nó là nền tảng cho BST, heap, và cây biểu thức.
Binary tree (cây nhị phân) là một cấu trúc phân cấp trong đó mỗi node có tối đa hai con (children), gọi là left và . Nó có một duy nhất; các node không có con là (lá). Nó là nền tảng cho BST, heap, và cây biểu thức.
right 1 độ sâu 0 (root)
/ \
2 3 độ sâu 1
/ \
4 5 độ sâu 2 (leaf: 4,5,3)
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder(n): # left, node, right -> 4 2 5 1 3
if n:
inorder(n.left); print(n.val); inorder(n.right)
def preorder(n): # node, left, right -> 1 2 4 5 3
if n:
print(n.val); preorder(n.left); preorder(n.right)
def postorder(n): # left, right, node -> 4 5 2 3 1
if n:
postorder(n.left); postorder(n.right); print(n.val)
Một phép duyệt theo tầng (level-order, BFS) dùng một queue và thăm từng độ sâu một.
| Phép duyệt | Thứ tự | Ứng dụng phổ biến |
|---|---|---|
| Inorder | L, N, R | xuất sắp xếp của một BST |
| Preorder | N, L, R | sao chép/tuần tự hóa cây |
| Postorder | L, R, N | xóa cây, tính biểu thức |
| Level-order | theo độ sâu | BFS, đường đi ngắn nhất trên cây |
Mỗi phép duyệt thăm mỗi node một lần → thời gian O(n), không gian stack O(h) với h là chiều cao.
Binary tree mô hình hóa dữ liệu có tính phân cấp tự nhiên (hệ thống file, parse tree, decision tree) và là nền tảng của các cấu trúc tìm kiếm và sắp xếp hiệu quả.
Nắm vững bốn phép duyệt là thiết yếu — hầu hết các bài toán cây trong phỏng vấn là biến thể của một trong số chúng.