Hướng dẫn how do you create a data tree in python? - làm thế nào để bạn tạo một cây dữ liệu trong python?

Tìm hiểu về cây và cách thực hiện chúng.

Rễ

Một cây như một cấu trúc dữ liệu có thể nhanh chóng trở thành một môn toán học phức tạp (kiểm tra wiki), chúng ta được bao quanh bởi những thứ thực và ảo (thực sự dữ liệu) có thể được mô hình hóa và biểu diễn bởi một cây Hiểu ngay cả ở cấp độ cơ bản.

Python là một ngôn ngữ rất phong phú về các tính năng và cấu trúc dữ liệu. Nó có rất nhiều cấu trúc dữ liệu sẵn có như từ điển Python, danh sách, tuple, set, frozenset, v.v. Ngoài ra, chúng ta cũng có thể tạo các cấu trúc dữ liệu tùy chỉnh của riêng mình bằng các lớp. Trong bài viết này, chúng tôi sẽ tìm hiểu về cấu trúc dữ liệu cây nhị phân trong Python và sẽ cố gắng thực hiện nó bằng một ví dụ.

Cây là một cấu trúc dữ liệu trong đó các mục dữ liệu được kết nối bằng các tham chiếu theo cách phân cấp. Mỗi cây bao gồm một nút gốc mà từ đó chúng ta có thể truy cập từng phần tử của cây. Bắt đầu từ nút gốc, mỗi nút chứa 0 hoặc nhiều nút được kết nối với nó khi còn nhỏ. Một cây nhị phân đơn giản có thể được mô tả như được thấy trong hình sau.

Các bộ phận của cấu trúc dữ liệu cây

Một cây bao gồm một nút gốc, các nút lá và các nút bên trong. Mỗi nút được kết nối với chile của nó thông qua một tham chiếu, được gọi là cạnh. & NBSP;

Nút gốc: Nút gốc là nút trên cùng của cây. Nó luôn luôn là nút đầu tiên được tạo trong khi tạo cây và chúng ta có thể truy cập từng phần tử của cây bắt đầu từ nút gốc. Trong ví dụ trên, nút chứa phần tử 50 là nút gốc. Root node is the topmost node of a tree. It is always the first node created while creating the tree and we can access each element of the tree starting from the root node. In the above example, the node containing element 50 is the root node.

Nút cha: Cha mẹ của bất kỳ nút nào là nút tham chiếu nút hiện tại. Trong ví dụ trên, 50 là cha mẹ của 20 và 45, 20 là cha mẹ của 11, 46 và 15. Tương tự 45 là cha mẹ của 30 và 78. The parent of any node is the node which references the current node. In the above example, 50 is the parent of 20 and 45, 20 is parent of 11, 46 and 15. Similarly 45 is the parent of 30 and 78.

Nút con: Các nút con của nút cha là các nút mà tại đó nút cha đang trỏ bằng các tham chiếu. Trong ví dụ trên, 20 và 45 là con của 50. Các nút 11, 46 và 15 là con của 20 và 30 và 78 là con 45. Child nodes of a parent node are the nodes at which the parent node is pointing using the references. In the example above, 20 and 45 are children of 50. The nodes 11, 46, and 15 are children of 20 and 30 and 78 are children of 45.

Cạnh: Tham chiếu thông qua đó nút cha được kết nối với nút con được gọi là cạnh. Trong ví dụ trên, mỗi mũi tên kết nối bất kỳ hai nút nào là một cạnh. The reference through which a parent node is connected to a child node is called an edge. In the above example, each arrow that connects any two nodes is an edge.

Nút lá: Đây là những nút trong cây không có con. & NBSP; Trong ví dụ trên, 11, 46, 15, 30 và 78 là các nút lá. These are those nodes in the tree which have no children. In the above example, 11, 46, 15, 30, and 78 are leaf nodes.

Các nút bên trong: Các nút bên trong là các nút có ít nhất một đứa trẻ. Trong ví dụ trên, 50, 20 và 45 là các nút bên trong. Internal Nodes are the nodes which have at least one child. In the above example, 50, 20 and 45 are internal nodes.

Cây nhị phân là gì?

Một cây nhị phân là cấu trúc dữ liệu cây trong đó mỗi nút có thể có tối đa 2 trẻ em. & NBSP; Nó có nghĩa là mỗi nút trong một cây nhị phân có thể có một hoặc hai hoặc không có con. Mỗi nút trong một cây nhị phân chứa dữ liệu và tham chiếu đến con cái của nó. Cả hai đứa trẻ được đặt tên là đứa trẻ trái và đứa trẻ phải theo vị trí của chúng. Cấu trúc của một nút trong một cây nhị phân được hiển thị trong hình sau.

Chúng ta có thể xác định một nút của cấu trúc được hiển thị ở trên trong Python bằng cách sử dụng các lớp như sau.

class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.leftChild = None
    self.rightChild=None

Ở đây, hàm tạo của nút lấy giá trị dữ liệu làm đầu vào, tạo một đối tượng của loại binytreenode và khởi tạo trường dữ liệu bằng với đầu vào đã cho và khởi tạo các tham chiếu đến trẻ em thành không. Trẻ em có thể được chỉ định vào các nút sau này. Một ví dụ về cây nhị phân được hiển thị trong hình dưới đây.

Chúng ta có thể thực hiện cây nhị phân ở trên trong Python như sau.

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


node1 = BinaryTreeNode(50)
node2 = BinaryTreeNode(20)
node3 = BinaryTreeNode(45)
node4 = BinaryTreeNode(11)
node5 = BinaryTreeNode(15)
node6 = BinaryTreeNode(30)
node7 = BinaryTreeNode(78)

node1.leftChild = node2
node1.rightChild = node3
node2.leftChild = node4
node2.rightChild = node5
node3.leftChild = node6
node3.rightChild = node7

print("Root Node is:")
print(node1.data)

print("left child of the node is:")
print(node1.leftChild.data)

print("right child of the node is:")
print(node1.rightChild.data)

print("Node is:")
print(node2.data)

print("left child of the node is:")
print(node2.leftChild.data)

print("right child of the node is:")
print(node2.rightChild.data)

print("Node is:")
print(node3.data)

print("left child of the node is:")
print(node3.leftChild.data)

print("right child of the node is:")
print(node3.rightChild.data)

print("Node is:")
print(node4.data)

print("left child of the node is:")
print(node4.leftChild)

print("right child of the node is:")
print(node4.rightChild)

print("Node is:")
print(node5.data)

print("left child of the node is:")
print(node5.leftChild)

print("right child of the node is:")
print(node5.rightChild)

print("Node is:")
print(node6.data)

print("left child of the node is:")
print(node6.leftChild)

print("right child of the node is:")
print(node6.rightChild)

print("Node is:")
print(node7.data)

print("left child of the node is:")
print(node7.leftChild)

print("right child of the node is:")
print(node7.rightChild)

Output:

Root Node is:
50
left child of the node is:
20
right child of the node is:
45
Node is:
20
left child of the node is:
11
right child of the node is:
15
Node is:
45
left child of the node is:
30
right child of the node is:
78
Node is:
11
left child of the node is:
None
right child of the node is:
None
Node is:
15
left child of the node is:
None
right child of the node is:
None
Node is:
30
left child of the node is:
None
right child of the node is:
None
Node is:
78
left child of the node is:
None
right child of the node is:
None

Sự kết luận

Trong bài viết này, chúng tôi đã thảo luận về cấu trúc dữ liệu cây và cấu trúc dữ liệu cây nhị phân trong Python. Để tìm hiểu thêm về các cấu trúc dữ liệu trong Python, bạn có thể đọc bài viết này trên danh sách được liên kết trong Python.

Khuyến nghị đào tạo Python

Khóa học: Python 3 cho người mới bắt đầu

Hơn 15 giờ nội dung video với hướng dẫn hướng dẫn cho người mới bắt đầu. Tìm hiểu làm thế nào để tạo các ứng dụng trong thế giới thực và làm chủ những điều cơ bản.