Binary Tree là một cấu trúc dữ liệu đặc biệt dùng cho mục đích lưu trữ dữ liệu. Binary Tree có điều kiện đặc biệt là mỗi nút có tối đa hai con. Binary Tree có lợi thế của cả mảng đã sắp xếp và danh sách liên kết: tìm kiếm nhanh như mảng đã sắp xếp, chèn/xóa nhanh như danh sách liên kết.
Đây là minh họa của một binary tree với một số thuật ngữ đã thảo luận dưới đây:
Thuật ngữ quan trọng
Sau đây là các thuật ngữ quan trọng liên quan đến cây:
Path (Đường đi) - Path là chuỗi các nút theo các cạnh của cây.
Root (Gốc) - Nút ở đỉnh cây gọi là root. Chỉ có một root cho mỗi cây và một đường đi từ root đến bất kỳ nút nào.
Parent (Cha) - Bất kỳ nút nào trừ root đều có một cạnh hướng lên trên đến một nút gọi là parent.
Child (Con) - Nút dưới một nút cho trước được nối bởi cạnh hướng xuống gọi là child node.
Leaf (Lá) - Nút không có child node nào gọi là leaf node.
Subtree (Cây con) - Subtree biểu diễn các nút con cháu của một nút.
Visiting (Ghé thăm) - Visiting là kiểm tra giá trị của nút khi điều khiển đang ở trên nút đó.
Traversing (Duyệt) - Traversing nghĩa là đi qua các nút theo một thứ tự cụ thể.
Levels (Cấp độ) - Cấp độ của nút biểu diễn thế hệ của nút. Nếu root ở cấp 0, con tiếp theo ở cấp 1, cháu ở cấp 2, v.v.
Keys (Khóa) - Key biểu diễn giá trị của một nút dựa trên đó thao tác tìm kiếm được thực hiện cho một nút.