Cây nhị phân là một cấu trúc dữ liệu đặc biệt được sử dụng cho mục đích lưu trữ dữ liệu. Cây nhị phân có một điều kiện đặc biệt là mỗi nút có thể có tối đa hai nút con. Cây nhị phân có những lợi ích của cả mảng có thứ tự và danh sách được liên kết vì tìm kiếm nhanh như trong một mảng được sắp xếp và thao tác chèn hoặc xóa cũng nhanh như trong danh sách được liên kết.
Đây là minh họa về cây nhị phân với một số thuật ngữ mà chúng ta đã thảo luận bên dưới -
Điều khoản quan trọng
Sau đây là các điều khoản quan trọng đối với cây.
-
Đường dẫn - Đường dẫn đề cập đến chuỗi các nút dọc theo các cạnh của cây.
-
Gốc - Nút ở ngọn cây gọi là gốc. Chỉ có một gốc trên mỗi cây và một đường dẫn từ nút gốc đến bất kỳ nút nào.
-
Cha mẹ - Bất kỳ nút nào ngoại trừ nút gốc đều có một cạnh hướng lên trên một nút được gọi là nút cha.
-
Con - Nút bên dưới một nút nhất định được kết nối bởi cạnh của nó hướng xuống được gọi là nút con của nó.
-
Lá - Nút không có bất kỳ nút con nào được gọi là nút lá.
-
Cây phụ - Cây con đại diện cho con của một nút.
-
Tham quan - Tham quan đề cập đến việc kiểm tra giá trị của một nút khi quyền điều khiển ở trên nút.
-
Di chuyển ngang qua - Đi ngang có nghĩa là đi qua các nút theo một thứ tự cụ thể.
-
Cấp độ - Mức của một nút thể hiện sự sinh ra của một nút. Nếu nút gốc ở cấp 0, thì nút con tiếp theo của nó ở cấp 1, nút cháu của nó ở cấp 2, v.v.
-
Phím - Khóa đại diện cho giá trị của một nút dựa trên đó hoạt động tìm kiếm sẽ được thực hiện cho một nút.