Hướng dẫn how do you write trees in python? - làm thế nào để bạn viết cây 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 -

• Một nút được đánh dấu là nút gốc.

• Mỗi nút khác ngoài gốc được liên kết với một nút cha.

• Mỗi nút có thể có số lượng nút chid.

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 root

Chú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 ra

Khi 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 ra

Khi 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ây

Câ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ây

• 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

Thuật toán truyền tải cây

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

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 ra

Khi 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 ra

Khi 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àng

Traversal đặ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 ra

Khi mã trên được thực thi, nó sẽ tạo ra kết quả sau -

[10, 19, 14, 31, 42, 35, 27]