Cây nhị phân được định nghĩa là cấu trúc dữ liệu dạng cây mà mỗi nút có nhiều nhất 2 nút con. Vì mỗi phần tử trong cây nhị phân chỉ có thể có 2 con nên chúng ta thường đặt tên cho chúng là con trái và con phải
Cây dưới dạng cấu trúc dữ liệu có thể nhanh chóng trở thành một chủ đề toán học phức tạp [ tham khảo wiki 👀 ], xung quanh chúng ta là những thứ thực và ảo [dữ liệu thực sự] có thể được mô hình hóa và biểu diễn bằng cây, vì vậy đây là một chủ đề rất hữu ích để
Cây là một cấu trúc dữ liệu phi tuyến tính trong đó các nút được kết nối theo cách phân cấp. Mỗi cây có một nút gốc đánh dấu điểm truy cập của tất cả các nút khác trong cây. Vì vậy, một Cây được hình thành từ một nút gốc và 0 hoặc nhiều nút con. Các cây được phân loại thành các loại khác nhau trên cơ sở cấu trúc và loại dữ liệu của chúng. Chúng là Cây nhị phân, Cây tìm kiếm nhị phân, Cây AVL, Cây B, Cây B+, Cây biểu thức, v.v.
Hình dưới đây cho thấy cấu trúc của Cây tìm kiếm nhị phân
Quảng cáo
Cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân là cây nhị phân đặc biệt bao gồm 0, 1 hoặc 2 nút con và tuân theo các quy tắc nhất định khi chèn giá trị vào nút. Cây tìm kiếm nhị phân là cây nhị phân trong đó tất cả các nút tuân theo các thuộc tính được đề cập bên dưới
- Tất cả các nút ở bên trái của nút hiện tại có giá trị nhỏ hơn nút hiện tại
- Tất cả các nút ở bên phải của nút hiện tại có giá trị lớn hơn nút hiện tại
CŨNG ĐỌC. Ví dụ về hàm danh sách Python pop[] [Người mới bắt đầu]
Ở đây, chúng ta sẽ xem cách triển khai cây tìm kiếm nhị phân từ đầu trong Python
Tạo một nút
Để tạo Cấu trúc dữ liệu cây Python nhị phân, trước tiên chúng ta sẽ phải tạo một lớp Nút đại diện cho một nút. Lớp Node này sẽ có 3 biến lớp. Biến bên trái trỏ đến nút con bên trái, biến bên phải trỏ đến nút con bên phải và biến dữ liệu chứa giá trị thực cho nút đó. Đoạn mã dưới đây cho thấy lớp đại diện cho một nút
# Implementing Python Tree Data Structure
# Creating a class for node object
class Node[object]:
# Initializing to None
def __init__[self]:
self.left = None
self.right = None
self.data = None
Triển khai chèn vào cây tìm kiếm nhị phân
Để chèn một nút vào cây tìm kiếm nhị phân, chúng ta cần đảm bảo rằng không có thuộc tính nào của cây tìm kiếm nhị phân bị vi phạm khi chèn nút
Ở đây, mỗi lệnh gọi phương thức chèn sẽ chèn một nút vào cây tìm kiếm nhị phân. Lệnh gọi chèn đầu tiên sẽ biến nút đó thành nút gốc. Tất cả các lần chèn khác sẽ diễn ra khi xem xét giá trị của nút gốc.
Mã bên dưới hiển thị chức năng chèn đặt nút vào cây sao cho không thuộc tính nào của cây tìm kiếm nhị phân bị vi phạm.
# Implementing Python Tree Data Structure
# Creating a class for node object
class Node[object]:
# Initializing to None
def __init__[self]:
self.left = None
self.right = None
self.data = None
# Inserting a node in Binary search tree
def insertion[val]:
# Condition if this is a first node then it will be considered as a root
if[root.data==None]:
print[val," Inserted as root"]
root.data=val
# Else part will be executed for all the other insertions
else:
# Pointer to move around tree to search for a place of new node
p=root
# Creating a new node and writing a value in the data part
n = Node[]
n.data=val
# Iterating to search for an appropriate place of new node
while[1]:
# if val is less than the current node p indicates that new node will be inserted on left subtree
if[val