Trăn rừng

Tải ngay

Chuyển đến trang

Tìm kiếm bên trong tài liệu

Bạn đang đọc bản xem trước miễn phí
Các trang 9 đến 14 are not shown in this preview.

Bạn đang đọc bản xem trước miễn phí
Trang 18 đến 24 are not shown in this preview.

Bạn đang đọc bản xem trước miễn phí
Trang 28 đến 31 are not shown in this preview.

Bạn đang đọc bản xem trước miễn phí
Trang 35 đến 53 are not shown in this preview.

Thưởng cho sự tò mò của bạn

Mọi thứ bạn muốn đọc

Bất cứ lúc nào. bất cứ nơi nào. Bất kỳ thiết bị

Không cam kết. Hủy bỏ bất cứ lúc nào

Chia sẻ tài liệu này

Chia sẻ hoặc nhúng tài liệu

Chia sẻ lựa chọn

• Chia sẻ với Email, mở ứng dụng thư khách

điều hướng nhanh

• Trang Chủ

• Sách

• sách nói

• Các tài liệu

  , tích cực

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 với nút 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 con tùy ý

Chúng tôi tạo cấu trúc dữ liệu dạng cây trong python bằng cách sử dụng khái niệm nút os đã thảo luận trước đó. Chúng tôi chỉ định một nút làm nút gốc và sau đó thêm các nút khác làm nút con. Dưới đây là chương trình tạo nút gốc

Tạo gốc

Chúng ta chỉ cần tạo một lớp Node và thêm gán giá trị cho nút. Điều này trở thành cây chỉ có một nút gốc

Ví 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 đoạn mã trên được thực thi, nó tạo ra kết quả sau -

10

Chèn vào cây

Để chèn vào cây, chúng ta sử dụng cùng một lớp nút đã 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 trái hoặc nút phải. Cuối cùng, lớp PrintTree được sử dụng để in cây

Ví 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 đoạn mã trên được thực thi, nó tạo ra kết quả sau -

3 6 12 14

Đi ngang qua một cái cây

Cây có thể được duyệt qua bằng cách quyết định trình tự truy cập từng nút. Như chúng ta có thể thấy rõ ràng, 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à cây con bên phải tiếp theo. Hoặc chúng ta cũng có thể truy cập cây con bên phải trước và cây con bên trái tiếp theo. Theo đó, có các tên khác nhau cho các phương pháp duyệt cây này

Thuật toán duyệt cây

Truyền tải 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]. Nghĩa là chúng ta không thể truy cập ngẫu nhiên vào 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

• Travers theo thứ tự

• Đặt hàng trước

• Travers sau đặt hàng

Travers theo thứ tự

Trong phương pháp duyệt này, cây con bên trái được thăm trước, sau đó đến gốc và sau đó là cây con bên phải. Chúng ta nên luôn nhớ rằng mỗi nút có thể đại diện cho một cây con

Trong chương trình python dưới đây, chúng tôi sử dụng lớp Node để tạo các trình giữ chỗ cho nút gốc cũng như các nút trái và phải. Sau đó, chúng ta tạo một hàm chèn để thêm dữ liệu vào cây. Cuối cùng, logic truyền tải theo thứ tự được triển khai bằng cách tạo một danh sách trống và thêm nút bên trái trước, sau đó là nút gốc hoặc nút cha

Cuối cùng, nút bên trái được thêm vào để hoàn thành quá trình truyền tải theo thứ tự. Xin lưu ý rằng quá trình này được lặp lại cho mỗi cây con cho đến khi tất cả các nút được duyệt qua

Ví 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 đoạn mã trên được thực thi, nó tạo ra kết quả sau -

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

Đặt hàng trước

Trong phương pháp duyệt này, nút gốc được thăm trước, sau đó đến cây con bên trái và cuối cùng là cây con bên phải

Trong chương trình python dưới đây, chúng tôi sử dụng lớp Node để tạo các trình giữ chỗ cho nút gốc cũng như các nút trái và phải. Sau đó, chúng ta tạo một hàm chèn để thêm dữ liệu vào cây. Cuối cùng, logic truyền tải theo đơn đặt hàng trước được triển khai bằng cách tạo một danh sách trống và thêm nút gốc trước, sau đó là nút bên trái

Cuối cùng, nút bên phải được thêm vào để hoàn thành quá trình truyền tải Đơn đặt hàng trước. Xin lưu ý rằng, quá trình này được lặp lại cho mỗi cây con cho đến khi tất cả các nút được duyệt qua

Ví 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 đoạn mã trên được thực thi, nó tạo ra kết quả sau -

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

Travers sau đặt hàng

Trong phương pháp truyền tải này, nút gốc được truy cập cuối cùng, do đó có tên. Đầu tiên, chúng ta duyệt 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 Node để tạo các trình giữ chỗ cho nút gốc cũng như các nút trái và phải. Sau đó, chúng ta tạo một hàm chèn để thêm dữ liệu vào cây. Cuối cùng, logic truyền tải theo thứ tự sau được triển khai bằng cách tạo một danh sách trống và thêm nút bên trái trước, sau đó là nút bên phải

Cuối cùng, nút gốc hoặc nút cha được thêm vào để hoàn thành quá trình truyền tải theo thứ tự sau. Xin lưu ý rằng, quá trình này được lặp lại cho mỗi cây con cho đến khi tất cả các nút được duyệt qua