Hướng dẫn how do you make a binary tree in python? - làm thế nào để bạn tạo một cây nhị phân trong python?

Cây là một cấu trúc dữ liệu phi tuyến tính. Nó là một cấu trúc dữ liệu phân cấp có các nút được kết nối thông qua các liên kết. Nút cao nhất của cây không có cha mẹ được gọi là nút gốc. is a non-linear data structure. It is a hierarchical data structure that has nodes connected through links. The topmost node of the tree which has no parent is known as the root node.

Cây

Cây nhị phân

Cây nhị phân là một dạng cây có nút không thể có nhiều hơn hai đứa con. Mỗi nút của cây nhị phân có hai con trỏ liên kết với nó, một điểm vào đứa trẻ bên trái và các điểm khác vào đứa con phải của nút. Nó là một cây không có thứ tự không có cấu trúc có tổ chức cố định để sắp xếp các nút. is a form of a tree whose nodes cannot have more than two children. Each node of the binary tree has two pointers associated with it, one points to the left child, and the other points to the right child of the node. It is an unordered tree having no fixed organized structure for the arrangement of nodes.

Lưu ý: Cây nhị phân chậm cho việc tìm kiếm, chèn hoặc xóa dữ liệu vì cấu trúc không có thứ tự của nó. Độ phức tạp của thời gian của các hoạt động này là O (n) O (N). Binary Tree is slow for the searching, insertion, or deletion of the data because of its unordered structure. The time complexity of these operations is O(N)O(N).

%0 node_110 node_270 node_1->node_2 node_390 node_1->node_3 node_159309474347820 node_2->node_1593094743478 node_159309474258460 node_2->node_1593094742584 node_159309477358450 node_3->node_1593094773584

Cây nhị phân

Cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân (BST) là một loại cây nhị phân được đặt hàng ở dạng. Nó có một cấu trúc có tổ chức cố định để sắp xếp các nút. Cấu trúc tuân theo các quy tắc sau: is a type of binary tree which is in ordered form. It has a fixed organized structure for the arrangement of nodes. The structure follows the following rules:

• Con trái của nút phải có giá trị thấp hơn giá trị cha mẹ của nó
• Đứa trẻ bên phải của nút phải có giá trị lớn hơn giá trị cha mẹ của nó

Lưu ý: BST nhanh hơn một cây nhị phân trong việc tìm kiếm, chèn hoặc xóa dữ liệu vì cấu trúc được đặt hàng của nó. Độ phức tạp của thời gian của các hoạt động này là O (logn) O (log n). BST is faster than a binary tree in the searching, insertion, or deletion of the data because of its ordered structure. The time complexity of these operations is O(logN)O(log N).

%0 node_127 node_214 node_1->node_2 node_335 node_1->node_3 node_159309474347810 node_2->node_1593094743478 node_15930947425849 node_2->node_1593094742584 node_159309480342531 node_3->node_1593094803425 node_159309477358442 node_3->node_1593094773584

BST

Thực hiện

Chúng tôi đã tạo một lớp node và khởi tạo nút root với 2727.2727.

# Creating node class
class Node:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None
    # print function
    def PrintTree(self):
        print(self.data)
# Creating a root node
root = Node(27)
root.PrintTree()

Lớp nút

Chèn

Phương pháp insert so sánh giá trị với giá trị của nút root và quyết định có nên chèn nó vào bên trái hay bên phải của BST.

Hãy nhớ rằng: nếu giá trị thấp hơn giá trị của nút cha, nó được chèn vào bên trái; Nếu không, nó đã chèn vào phía bên phải của BST. If the value is lesser than the value of the parent node, it is inserted on the left side; otherwise,​ it’s inserted on the right side of the BST.

Cuối cùng, phương pháp PrintTree được sử dụng để in BST.

# Creating node class
class Node:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None
# Function to insert in BST
    def insert(self, data):
        # if value is lesser than the value of the parent node
        if data < self.data:
            if self.leftChild:
                # if we still need to move towards the left subtree
                self.leftChild.insert(data)
            else:
                self.leftChild = Node(data)
                return
        # if value is greater than the value of the parent node        
        else:
            if self.rightChild:
                # if we still need to move towards the right subtree
                self.rightChild.insert(data)
            else:
                self.rightChild = Node(data)
                return
    # function to print a BST
    def PrintTree(self):
        if self.leftChild:
            self.leftChild.PrintTree()
        print( self.data),
        if self.rightChild:
            self.rightChild.PrintTree()
# Creating root node
root = Node(27)
# Inserting values in BST
root.insert(14)
root.insert(35)
root.insert(31)
root.insert(10)
root.insert(19)
# printing BST
root.PrintTree()

Chèn vào BST

Đang tìm kiếm

Phương pháp search so sánh giá trị với giá trị của nút root và nếu không khớp, nó sẽ quyết định tìm kiếm ở bên trái hay bên phải của BST.

Hãy nhớ rằng: nếu giá trị thấp hơn giá trị của nút cha, nó sẽ được tìm kiếm ở phía bên trái; Nếu không, nó đã tìm kiếm ở phía bên phải của BST. If the value is lesser than the value of the parent node, it is searched on the left side; otherwise,​ it’s searched on the right side of the BST.

# Creating node class
class Node:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None
# Function to insert in BST
    def insert(self, data):
        # if value is lesser than the value of the parent node
        if data < self.data:
            if self.leftChild:
                # if we still need to move towards the left subtree
                self.leftChild.insert(data)
            else:
                self.leftChild = Node(data)
                return
        # if value is greater than the value of the parent node        
        else:
            if self.rightChild:
                # if we still need to move towards the right subtree
                self.rightChild.insert(data)
            else:
                self.rightChild = Node(data)
                return
# Function to search in BST
    def search(self, val):
        # if value to be searched is found
        if val==self.data:
            return str(val)+" is found in the BST"
        # if value is lesser than the value of the parent node
        elif val < self.data:
            # if we still need to move towards the left subtree
            if self.leftChild:
                return self.leftChild.search(val)
            else:



 return str(val)+" is not found in the BST"
 # if value is greater than the value of the parent node
 else:
 # if we still need to move towards the right subtree
 if self.rightChild:
 return self.rightChild.search(val)
 else:
 return str(val)+" is not found in the BST" 
 # function to print a BST
 def PrintTree(self):
 if self.leftChild:
 self.leftChild.PrintTree()
 print( self.data),
 if self.rightChild:
 self.rightChild.PrintTree()
# Creating root node
root = Node(27)
# Inserting values in BST
root.insert(14)
root.insert(35)
root.insert(31)
root.insert(10)
root.insert(19)
# searching the values
print(root.search(7))
print(root.search(14))

Tìm kiếm trong BST

THẺ LIÊN QUAN

Cây nhị phân

Tạo nút

Chèn một nút

Tìm kiếm một nút

cộng đồng