Hướng dẫn how are binary trees represented in python? - cây nhị phân được biểu diễ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] Làm thế nào là cây được đại diện trong Python?Cây là các cấu trúc dữ liệu phi tuyến tính đại diện cho các nút được kết nối bởi các cạnh. Mỗi cây bao gồm một nút gốc làm nút cha và nút bên trái và nút phải làm nút con.nodes connected by edges. Each tree consists of a root node as the Parent node, and the left node and right node as Child nodes.
Cây nhị phân được đại diện như thế nào?Biểu diễn cây nhị phân của cây nhiều đường hoặc cây K-ary dựa trên đại diện anh chị em hàng đầu của cây. Trong đại diện này, mọi nút được liên kết với đứa con ngoài cùng bên trái và anh chị em tiếp theo (bên phải gần nhất). Đây là biểu diễn cây nhị phân của cây (đa đường) đã cho.based on first child-next sibling representation of the tree. In this representation every node is linked with its leftmost child and its next (right nearest) sibling. This is binary tree representation of the given (multiway) tree.
Làm thế nào để bạn viết cây trong Python?Để tạo một cây trong Python, trước tiên chúng ta phải bắt đầu bằng cách tạo một lớp nút sẽ đại diện cho một nút duy nhất.Lớp nút này sẽ chứa 3 biến;Đầu tiên là bên trái trỏ đến đứa trẻ bên trái, dữ liệu biến thứ hai chứa giá trị cho nút đó và biến bên phải trỏ đến đúng đứa trẻ.creating a Node class that will represent a single node. This Node class will contain 3 variables; the first is the left pointing to the left child, the second variable data containing the value for that node, and the right variable pointing to the right child.
2 loại biểu diễn cây nhị phân là gì?Các loại cây nhị phân.. Cây nhị phân đầy đủ.Một cây nhị phân đầy đủ là một loại cây nhị phân đặc biệt trong đó mọi nút cha/nút bên trong đều có hai hoặc không có con..... Cây nhị phân hoàn hảo..... Hoàn thành cây nhị phân..... Thoái hóa hoặc cây bệnh lý..... Cây nhị phân xiên..... Cây nhị phân cân bằng .. |
