Cây nhị phân trong Python là gì?
Trong bài viết này, chúng ta đã khám phá chiến lược triển khai Cây nhị phân trong Ngôn ngữ lập trình Python với lời giải thích đầy đủ và các hoạt động khác nhau như duyệt, tìm kiếm và xóa Show Mục lục
Cây nhị phân là gì? Cây nhị phân là loại cấu trúc dữ liệu thừa kế đặc biệt được xác định bằng các nút. Về cơ bản, phiên bản mở rộng của danh sách liên kết. Đó là cấu trúc dữ liệu cây trong đó mỗi nút được phép có tối đa hai nút con, thường được gọi là Con trái và Con phải. Băm, định tuyến dữ liệu cho lưu lượng mạng, nén dữ liệu và cây tìm kiếm nhị phân là một số ứng dụng của nó Dữ liệu, cây con trái và cây con phải là ba tính năng quan trọng trong cây nhị phân. Mỗi dữ liệu nằm trong ô Dữ liệu với con trỏ bên trái trỏ đến cây con bên trái tiếp theo và ô Dữ liệu bên phải với con trỏ bên phải trỏ đến tám cây con tiếp theo **Một số thuật ngữ chính. - ** Nguồn gốc. - Nút trên cùng
Cây nhị phân với tất cả các nút bên trong (tất cả các nút trừ nút lá) có hai con và tất cả các nút lá có cùng độ sâu
Mọi cây có chênh lệch tối đa giữa chiều cao cây con bên phải và bên trái là 1 3) Cây nhị phân hoàn chỉnh Tất cả cây nhị phân trong đó mọi nút được lấp đầy hoàn toàn bằng nút 2 hoặc 0 4) Cây nhị phân suy biến Mỗi cây nhị phân, trong đó mỗi nút bên trong chỉ có một nút con duy nhất Ứng dụng của cây nhị phân
Triển khai Quy tắc. -
đầu ra. - 20,24,35,40,55,60 Cấu trúc của cây. -
**Giải trình. - ** Ở đây, chúng ta định nghĩa một lớp BinarTree, trong đó có 3 phương thức được định nghĩa
Các phương thức Bây giờ trong hàm chính khi chúng ta tạo một đối tượng của lớp trong gốc, chúng ta chuyển giá trị 40, mà chúng ta muốn là phần tử gốc. Trong dòng tiếp theo, chúng ta gọi phương thức insert() với đối tượng và truyền giá trị 35, giá trị này đưa luồng chương trình đến hàm chèn, ở đó chúng ta kiểm tra xem giá trị mới lớn hơn hay nhỏ hơn giá trị gốc của nó với (if value
Bây giờ chúng ta gọi hàm chèn với giá trị 55, quy trình tương tự như quy định ở trên cũng diễn ra ở đây, nhưng ở đây 50>35 (vì trước đó. giá trị đã được cập nhật bằng cách sử dụng self. left=BinaryTree(35) và 50 là giá trị mới), do đó, luồng chuyển sang điều kiện elif theo đó nó tự thấy. quyền thực sự bằng Không, do đó, nó cập nhật nó thành 55 và tự. giá trị đến 55
Tương tự, phần còn lại của hàm chèn được gọi và thực thi trên mọi giá trị mà cây nhị phân cuối cùng thu được hoạt động ngangKhi, chúng tôi in các giá trị của mọi nút ở đây, chúng tôi đang sử dụng truyền tải theo thứ tự trước trong đó hầu hết phần tử con bên trái đầu tiên được in, sau đó là gốc, sau đó là phần tử con bên phải đi ngang. -
PostOrder Traversal. - Ở đây nút con Trái được truy cập trước, sau đó đến nút con Phải và sau đó là nút Gốc Số phút thay đổi trong phương thức PrintTree() như sau
đầu ra. - 24,20,35,60,55,40 Duyệt đơn đặt hàng trước Ở đây Root được truy cập trước, sau đó đến nút con bên trái và sau đó là nút con bên phải Số phút thay đổi trong phương thức PrintTree() như sau
đầu ra. - 40,35,20,24,55,60 Hoạt động tìm kiếmTìm kiếm trong cây nhị phân Tìm kiếm trong cây nhị phân là một bước rất đơn giản, vì chúng ta đã thảo luận về việc duyệt cây nhị phân, vì vậy chúng ta có thể sử dụng kỹ thuật duyệt để lấy tất cả các phần tử trong cây và tìm phần tử cần tìm. Ở đây chúng tôi đang sử dụng truyền tải đặt hàng trước, các bạn có thể sử dụng bất kỳ ai trong số họ Thao tác xóaXóa một phần tử khỏi cây nhị phân
Giải trình Các chương trình trên giải thích quy trình xóa một phần tử cụ thể khỏi cây nhị phân đã cho. Ở đây root đại diện cho nút gốc và key đại diện cho phần tử cần xóa hoặc đã được người dùng đặt hàng. 4 -> Tìm kiếm phần tử chính trong cây con trái hoặc phải Ban đầu, nó kiểm tra xem gốc (phần tử trên cùng) có trống hay không, nếu nó không trống thì nó kiểm tra phần tử khóa ít hơn phần tử gốc, nếu nó đúng thì người tìm kiếm curosr ở cây con bên trái của cây chính, -> Kiểm tra nút chính sau khi tìm thấy và cuối cùng xóa nó Trong điều kiện khác với điều kiện nếu không root. bên phải, nó kiểm tra xem có nút con nào phù hợp với nút (khóa) không và nút mới chính là nút gốc và với điều kiện nếu không phải là nút gốc. còn lại nó kiểm tra nếu không còn nút con nào để xóa thì nút gốc chính là nút đó Bây giờ nếu tồn tại cả nút con bên trái và bên phải cho nút chính sẽ bị xóa thì chúng ta thay thế nút chính bằng giá trị nhỏ nhất của cây con bên phải của nó và sau đó xóa nút nhỏ nhất trong cây con bên phải đó Với bài viết này tại OpenGenus, bạn phải có ý tưởng hoàn chỉnh về Triển khai Cây nhị phân trong Ngôn ngữ lập trình Python Cây nhị phân dùng để làm gì?Trong điện toán, cây nhị phân chủ yếu được sử dụng để tìm kiếm và sắp xếp vì chúng cung cấp phương tiện để lưu trữ dữ liệu theo thứ bậc. Một số thao tác phổ biến có thể được thực hiện trên cây nhị phân bao gồm chèn, xóa và duyệt.
Cây nhị phân trong lập trình là gì?Cây nhị phân là cấu trúc dữ liệu phi tuyến tính kiểu cây với tối đa hai con cho mỗi gốc . Mỗi nút trong cây nhị phân có tham chiếu trái và phải cùng với phần tử dữ liệu. Nút ở trên cùng của hệ thống phân cấp của cây được gọi là nút gốc. Các nút chứa các nút con khác là các nút cha.
Cây nhị phân là gì và nó hoạt động như thế nào?Cây nhị phân được tạo bởi các nút, trong đó mỗi nút chứa một con trỏ "trái", một con trỏ "phải" và một phần tử dữ liệu. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side.
Có cây tìm kiếm nhị phân trong Python không?Như tên gợi ý, tìm kiếm là thao tác chính của Cây tìm kiếm nhị phân trong Python . Nhiệm vụ chính của nó là tìm khóa trong Cây tìm kiếm nhị phân. |