Truyền qua cây nhị phân

Chuyển động của cây là một hoạt động quan trọng của cây. Cái gọi là truyền tải đề cập đến quyền truy cập vào thông tin của tất cả các nút trong cây, tức là truy cập từng nút trong cây một lần và duy nhất một lần. Chúng tôi gọi kiểu truy cập này vào tất cả các nút là truyền tải. Sau đó, hai chế độ duyệt cây quan trọng là truyền tải theo chiều sâu đầu tiên và truyền tải theo chiều rộng trước tiên, theo chiều sâu thường sử dụng đệ quy và theo chiều rộng thường sử dụng hàng đợi. Nói chung, hầu hết các thuật toán có thể được thực hiện đệ quy cũng có thể được thực hiện bằng cách sử dụng ngăn xếp.

Độ sâu truyền qua đầu tiên

Đối với cây nhị phân, Tìm kiếm đầu tiên theo chiều sâu là đi qua các nút của cây dọc theo chiều sâu của cây, tìm kiếm các nhánh của cây càng sâu càng tốt. Sau đó, có ba phương pháp quan trọng để truyền theo chiều sâu. Ba phương pháp này thường được sử dụng để truy cập các nút của cây, sự khác biệt giữa chúng nằm ở thứ tự mà mỗi nút được truy cập. Ba loại trình duyệt này được gọi là đặt hàng trước, đặt hàng trước và đặt hàng sau. Hãy đưa ra các định nghĩa chi tiết của chúng, và sau đó xem xét các ứng dụng của chúng.

Đặt hàng trước truy cập thứ tự trước đó, đầu tiên chúng ta truy cập gốc, sau đó đặt hàng trước đệ quy truy cập cây con bên trái, sau đó đặt hàng trước truy cập đệ quy gốc cây con bên phải -> cây con bên trái -> cây con bên phải
```
def preorder(self, root):
      if root == None:
          return
      print root.elem
      self.preorder(root.lchild)
      self.preorder(root.rchild)
```
Trong trình duyệt bậc giữa, chúng ta sử dụng đệ quy trình duyệt thứ tự giữa để truy cập cây con bên trái, sau đó truy cập nút gốc và cuối cùng sử dụng đệ quy trình duyệt thứ tự giữa để truy cập cây con bên phải trái -> nút gốc -> cây con bên phải
```
def inorder(self, root):
      if root == None:
          return
      self.inorder(root.lchild)
      print root.elem
      self.inorder(root.rchild)
```
Duyệt theo thứ tự sau Trong duyệt theo thứ tự, đầu tiên chúng ta sử dụng đệ quy duyệt theo thứ tự để truy cập các cây con bên trái và bên phải, và cuối cùng truy cập vào nút gốc cây con bên trái -> cây con bên phải -> nút gốc
```
def postorder(self, root):
      if root == None:
          return
      self.postorder(root.lchild)
      self.postorder(root.rchild)
      print root.elem
```

Truyền tải đầu tiên theo chiều rộng (truyền tải cấp độ)

Bắt đầu từ gốc của cây, đi ngang qua các nút của toàn bộ cây từ trái sang phải từ trên xuống dưới

def breadth_travel(self, root):
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print node.elem,
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)

PreviousCây nhị phân

Last updated 4 years ago

Was this helpful?

def breadth_travel(self, root): if root == None: return queue = [] queue.append(root) while queue: node = queue.pop(0) print node.elem, if node.lchild != None: queue.append(node.lchild) if node.rchild != None: queue.append(node.rchild)