Binary tree and figure 1

Binary tree

The binary tree is divided into Full binary tree , Perfect binary tree , Ordinary binary tree

Full binary tree

A full binary tree has two leaf nodes for each node , The nodes of the whole tree are full , This is the full binary tree

Perfect binary tree

A complete binary tree consists of all but the last layer of leaf nodes , All parent nodes are full binary trees , And the leaf nodes of the last layer are distributed from left to right , A full binary tree must be a complete binary tree , A complete binary tree is not necessarily a full binary tree

Ordinary binary tree

Besides completing binary tree and full binary tree , The others are ordinary binary trees

Binary tree storage

Complete binary tree storage is suitable for storing in an array , Because a complete binary tree is continuous , It is more suitable to store in an array
Incomplete binary trees are not suitable for storing in arrays , You can use a linked list to store

Binary tree linked list storage python Code implementation

class Node:
    def __init__(self, item=None):
        self.data = item
        self.left_next = None
        self.right_next = None


class HashList:
    def __init__(self):
        self.item = None

    def add(self, item):
        node = Node(item)
        if self.item is None:
            self.item = node
            return
        head = self.item
        head_item = head
        while head:
            head_item = head
            head = head.left_next if item < head.data else head.right_next
        if item < head_item.data:
            head_item.left_next = node
        else:
            head_item.right_next = node

    def preorder(self, item):
        if item is not None:
            print(item.data, end=" ")
            self.preorder(item.left_next)
            self.preorder(item.right_next)

    def search(self, item):
        head = self.item
        if not head:
            print(item, " non-existent ")
            return False
        while head:
            if head.data == item:
                print(item, " There is ")
                return True
            head = head.left_next if item < head.data else head.right_next

        print(item, " non-existent ")
        return False

    def rm(self, item):
        head = self.item
        head_itme = None
        while head:
            if head.data == item:
                #  If the data to be deleted is a leaf node ,
                if not head.right_next and not head.left_next:
                    #  here  head_itme  It is the root node of this leaf node , Determine whether the data to be deleted is on the left or right of the root node 
                    if item < head_itme.data:
                        head_itme.left_next = None
                    else:
                        head_itme.right_next = None
                    return
                elif head.left_next and not head.right_next:
                    #  If it's not a leaf node , And only the left leaf node , Then the root node's left_next  Set as... Of the data to be deleted left_next
                    head_itme.left_next = head.left_next
                    return
                elif head.right_next and not head.left_next:
                    #  If it's not a leaf node , And only the right leaf node , Then the root node's right_next  Set as... Of the data to be deleted right_next
                    head_itme.right_next = head.right_next
                    return
                else:
                    #  If you find the node to delete , When a node has left and right branches , Replace the minimum value of the right branch of the node 
                    #  Get the right node of this node 
                    head1 = head.right_next
                    head2 = None
                    #  Determine whether the right node has left and right next node 
                    if head1.right_next and head1.left_next:
                        #  Loop to get the minimum leaf node of the right node 
                        while head1.left_next:
                            head2 = head1
                            head1 = head1.left_next
                        #  At present head1  It is the smallest leaf node down the right side of the data to be deleted 
                        head.data = head1.data
                        # head2  It is the root node of this leaf node , Put this left_next  That is, the leaf node to be replaced is deleted 
                        head2.left_next = None
                        return
                    else:
                        #  This indicates that the right leaf node of the node to be deleted has no left or right leaf nodes , It is equivalent to a single chain ,
                        #  Then, the whole single chain will be used to replace the nodes to be deleted 
                        head.data = head1.data
                        #  Determine whether the right leaf node of the node to be deleted has a left leaf node or a right leaf node ,
                        #  If there is a right , Then directly replace the replaced right node , If there is a left , Then replace the replaced node 
                        #  The right node of is connected to the left node 
                        if head1.right_next:
                            head.right_next = head1.right_next
                        else:
                            head.right_next = head1.left_next
                        return

            head_itme = head
            head = head.right_next if head.data < item else head.left_next

    def find_max(self):
        head = self.item
        if not head:
            return
        while head.right_next:
            head = head.right_next
        print(" The maximum is ：", head.data)

    def find_min(self):
        head = self.item
        if not head:
            return
        while head.left_next:
            head = head.left_next
        print(" The minimum is ：", head.data)


if __name__ == '__main__':
    lists = [10, 8, 50, 6, 9, 40, 55, 2, 3, 77, 54, 1, 2.5, 0]
    map_hash = HashList()
    for i in lists:
    	#  Loop to insert data into the binary tree 
        map_hash.add(i)
    #  Output the data stored in the binary tree 
    map_hash.preorder(map_hash.item)
    print()
    #  Find out if the data exists 
    map_hash.search(1000)
    #  Delete data 
    map_hash.rm(10)
    #  Output deleted data 
    map_hash.preorder(map_hash.item)
    print()
    #  Find the maximum and minimum values 
    map_hash.find_max()
    map_hash.find_min()

The traversal of binary tree has Before the order Middle preface In the following order Traverse , What is in the current code is only the preorder traversal

The former sequence traversal Refer to , For any node in the tree , Print this node first , Then print its left subtree , Finally print its right subtree .
In the sequence traversal Refer to , For any node in the tree , First print its left subtree , And then print it itself , Finally print its right subtree
After the sequence traversal Refer to , For any node in the tree , First print its left subtree , Then print its right subtree , Finally, print the node itself .

Binary search tree

The binary tree is queried through the root node and Compare the data you want to find , If the data to be found is smaller than the root node , Then look down from the left side of the root node , Because data smaller than the root node is stored on the left , Data larger than the root node is stored on the right ,, It's a bit like dichotomy