Hướng dẫn how are binary trees implemented in python? - cây nhị phân được thực hiện như thế nào trong python?
|
Cây đại diện cho các nút được kết nối bởi các cạnh. Nó là một cấu trúc dữ liệu phi tuyến tính. Nó có các thuộc tính sau - Show
Chúng tôi tạo một cấu trúc dữ liệu cây trong Python bằng cách sử dụng nút OS Concept được thảo luận trước đó. Chúng tôi chỉ định một nút là nút gốc và sau đó thêm nhiều nút hơn làm nút con. Dưới đây là chương trình để tạo nút gốc. Tạo rootChúng tôi chỉ tạo một lớp nút và thêm gán một giá trị cho nút. Điều này trở thành cây chỉ có một nút gốc. Thí dụclass Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def PrintTree(self):
print(self.data)
root = Node(10)
root.PrintTree()
Đầu raKhi mã trên được thực thi, nó sẽ tạo ra kết quả sau - 10 Chèn vào một cái câyĐể chèn vào một cây, chúng tôi sử dụng cùng một lớp nút được tạo ở trên và thêm một lớp chèn vào nó. Lớp chèn so sánh giá trị của nút với nút cha và quyết định thêm nó dưới dạng nút bên trái hoặc nút bên phải. Cuối cùng, lớp printtree được sử dụng để in cây. Thí dụclass Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def insert(self, data):
# Compare the new value with the parent node
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()
Đầu raKhi mã trên được thực thi, nó sẽ tạo ra kết quả sau - 3 6 12 14 Chèn vào một cái câyĐể chèn vào một cây, chúng tôi sử dụng cùng một lớp nút được tạo ở trên và thêm một lớp chèn vào nó. Lớp chèn so sánh giá trị của nút với nút cha và quyết định thêm nó dưới dạng nút bên trái hoặc nút bên phải. Cuối cùng, lớp printtree được sử dụng để in cây. Đi qua một cái câyCây có thể được đi qua bằng cách quyết định một chuỗi để truy cập từng nút. Vì chúng ta có thể thấy rõ chúng ta có thể bắt đầu tại một nút sau đó truy cập cây con bên trái trước và bên phải tiếp theo. Hoặc chúng ta cũng có thể ghé thăm cây con bên phải trước và bên trái cây con tiếp theo. Theo đó, có những tên khác nhau cho các phương pháp truyền tải cây này.
Thuật toán truyền tải câyTraversal là một quá trình để truy cập tất cả các nút của cây và cũng có thể in các giá trị của chúng. Bởi vì, tất cả các nút được kết nối thông qua các cạnh (liên kết), chúng tôi luôn bắt đầu từ nút gốc (đầu). Đó là, chúng ta không thể truy cập ngẫu nhiên một nút trong cây. Có ba cách mà chúng ta sử dụng để đi qua một cái cây. Theo đơn đặt hàng Traversal đặt hàng trước Thí dụclass Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
else data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Inorder traversal
# Left -> Root -> Right
def inorderTraversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))
Đầu raKhi mã trên được thực thi, nó sẽ tạo ra kết quả sau - [10, 14, 19, 27, 31, 35, 42] Traversal là một quá trình để truy cập tất cả các nút của cây và cũng có thể in các giá trị của chúng. Bởi vì, tất cả các nút được kết nối thông qua các cạnh (liên kết), chúng tôi luôn bắt đầu từ nút gốc (đầu). Đó là, chúng ta không thể truy cập ngẫu nhiên một nút trong cây. Có ba cách mà chúng ta sử dụng để đi qua một cái cây.Theo đơn đặt hàng Traversal đặt hàng trước Traversal sau đơn đặt hàng Thí dụclass Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Preorder traversal
# Root -> Left ->Right
def PreorderTraversal(self, root):
res = []
if root:
res.append(root.data)
res = res + self.PreorderTraversal(root.left)
res = res + self.PreorderTraversal(root.right)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))
Đầu raKhi mã trên được thực thi, nó sẽ tạo ra kết quả sau - [27, 14, 10, 19, 35, 31, 42] Theo đơn đặt hàngTraversal đặt hàng trước Traversal sau đơn đặt hàng Trong phương pháp truyền tải này, cây con bên trái được truy cập trước, sau đó là gốc và sau đó là cây con bên phải. Chúng ta nên luôn luôn nhớ rằng mọi nút có thể đại diện cho chính một cây con. Thí dụclass Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
else if data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))
Đầu raKhi mã trên được thực thi, nó sẽ tạo ra kết quả sau - [10, 19, 14, 31, 42, 35, 27] Cây nhị phân được thực hiện như thế nào?Thực hiện cây nhị phân Nếu giá trị của nút mới thấp hơn nút hiện tại, hãy đi đến đứa trẻ bên trái. Nếu giá trị của nút mới lớn hơn nút hiện tại, hãy đến đúng đứa trẻ. Khi nút hiện tại là NULL, chúng tôi đã đến một nút lá, chúng tôi chèn nút mới ở vị trí đó.if the new node's value is lower than the current node's, go to the left child. if the new node's value is greater than the current node's, go to the right child. when the current node is null, we've reached a leaf node, we insert the new node in that position.
Làm thế nào để Python thực hiện tìm kiếm nhị phân?Thực hiện tìm kiếm nhị phân trong Python.. # Phương pháp chức năng tìm kiếm nhị phân lặp đi lặp lại Triển khai Python .. # Nó trả về chỉ mục của n trong danh sách đã cho1 nếu có,. # khác trả về -1 .. def Binary_Search (list1, n):. thấp = 0 .. cao = len (list1) - 1 .. mid = 0 .. trong khi thấp Cây tìm kiếm nhị phân là gì và nó được thực hiện như thế nào?Cây tìm kiếm nhị phân là cấu trúc dữ liệu cây nhị phân dựa trên nút có các thuộc tính sau: Subtree bên trái của nút chỉ chứa các nút có các phím nhỏ hơn phím của nút.Subtree bên phải của một nút chỉ chứa các nút có các phím lớn hơn phím của nút.a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys lesser than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key.
Làm thế nào để cây hoạt động trong Python?Cây là một cấu trúc dữ liệu trong đó các mục dữ liệu được kết nối bằng các tham chiếu theo cách phân cấp.Mỗi cây bao gồm một nút gốc mà từ đó chúng ta có thể truy cập từng phần tử của cây.Bắt đầu từ nút gốc, mỗi nút chứa 0 hoặc nhiều nút được kết nối với nó khi còn nhỏ.data items are connected using references in a hierarchical manner. Each Tree consists of a root node from which we can access each element of the tree. Starting from the root node, each node contains zero or more nodes connected to it as children. |
