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 để bạn tạo một nút trong Python?Tạo các nút Các nút được tạo bằng cách triển khai một lớp sẽ giữ các con trỏ cùng với phần tử dữ liệu. Trong ví dụ dưới đây, chúng tôi tạo một lớp có tên DayNames để giữ tên của các ngày trong tuần. Con trỏ NextVal được khởi tạo thành NULL và ba nút và khởi tạo với các giá trị như được hiển thị.by implementing a class which will hold the pointers along with the data element. In the below example we create a class named daynames to hold the name of the weekdays. The nextval pointer is initialized to null and three nodes and initialized with values as shown.
Làm thế nào để bạn làm một cái cây trong Python?Đầu tiên, chúng tôi đi qua cây con bên trái, sau đó là cây con bên phải và cuối cùng là nút gốc.Trong chương trình Python dưới đây, chúng tôi sử dụng lớp nút để tạo chủ sở hữu vị trí cho nút gốc cũng như các nút trái và bên phải.Sau đó, chúng tôi tạo một chức năng chèn để thêm dữ liệu vào cây.traverse the left subtree, then the right subtree and finally the root node. In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes. Then, we create an insert function to add data to the tree.
Làm thế nào để bạn tạo một cấu trúc cây nút?Nút cây.Mã để viết một nút cây sẽ tương tự như những gì được đưa ra dưới đây.Nó có một phần dữ liệu và tham chiếu đến các nút con trái và phải của nó.Nút cấu trúc {dữ liệu int;Nút cấu trúc *Retchild;Nút cấu trúc *phải;};struct node { int data; struct node *leftChild; struct node *rightChild; };
Một nút trong cây trong Python là gì?Treenode là một cấu trúc dữ liệu đại diện cho một mục của một cây, bao gồm nhiều nút như vậy.Nút trên cùng của một cây được gọi là gốc rễ và mỗi nút (ngoại trừ nút gốc) được liên kết với một nút cha.a data structure that represents one entry of a tree, which is composed of multiple of such nodes. The topmost node of a tree is called the “root”, and each node (with the exception of the root node) is associated with one parent node. |
