[Introduction] I tried to implement it by myself while explaining to understand the binary tree

To understand the binary tree

What is a binary tree?

It is a kind of non-linear data structure having a tree structure.

Tree ADT does not consider the order of elements.

Every node in a binary tree has 0 to 2 children. Therefore, the root and the left subtree that expands to the left of the root and the right subtree that expands to the right can be generally visualized.

[Explanation of the binary tree by Wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%A8%E6%A7%8B%E9%80%A0_(%E3%83%87%E3%) 83% BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0))

二分木の図解

Purpose

Contents

Data structure and node definition

Binary tree implementation

Creating a Node () object

Create a Node object and generate the following in the constructor. .Left and .right are also None because they have nothing to do with others at the time of generation

Node_class.py


class Node:
    """ Node is user data structure as binary tree  """
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

Binary tree generation

  1. Create a Node object
  2. Find the part where the child has no element and insert the Node.
  3. There are multiple methods that traversal Node, considering the order of visits.
Points at the time of implementation

binary_tree.py


class BinaryTree:
    """ user difine data structure BinaryTree """
    def __init__(self, arr):
        self.root = None #Create an empty root to serve as a basis for future processing

        for inserted_node_data in arr: #Process to insert the values of the nodes stored in the list sequentially
            print('....')
            print('try inserting ', inserted_node_data)
            self.insert(inserted_node_data)

    def insert(self, data):     #Insertion process (route generation ⇒ generate branch of each node) ・ ・ ・ The left branch has a value smaller than the current node
        if self.root == None:   #Because the root node is a special node that serves as the basis for tree analysis.Cases to be generated separately as root
            print('Root node is ....')
            self.root = Node(data) # Node()Create an instance and assign it
            print(self.root.data)

        else:
            level = 1
            flag = True
            next_queue = [self.root] #Create the first queue
            while flag:   #flag becomes False when all elements are None
                temp_queue, next_queue = next_queue, []
                level += 1

                for node in temp_queue:
                    #Left branch
                    #Add the currently node chiled node to the queue for the next operation
                    if node.left is not None:
                        next_queue.append(node.left)
                    #When None is found in child node, create a new node using data
                    else:
                        node.left = Node(data)
                        print('In level {}, {} is inseted'.format(level, data))
                        """
                        (AA)
After adding data to node, this insert ends
Here is for< while <Since it is in the insert method, use return to terminate the method in one shot
                        """
                        return 

                    #Right branch tree
                    #Add the currently node chiled node to the queue for the next operation
                    if node.right is not None:
                        next_queue.append(node.right)
                    #When None is found in child node, create a new node using data
                    else:
                        node.right = Node(data)
                        print('In level {}, {} is inseted'.format(level, data))
                        """
See (AA)
                        """
                        return

                flag = any(next_queue)

    ##########################
    #  Tree traversal
    ##########################
    def preoder_traversal(self, node, res):
        if node != None:
            print('queue', node.data)
            res.append(node.data)

            #Left subtree in preorder
            self.preoder_traversal(node.left, res)
            #Right subtree in preorder
            self.preoder_traversal(node.right, res)

        return res

    def inoder_traversal(self, node, res):
        if node != None:

            #Left subtree in order
            self.inoder_traversal(node.left, res)

            print('queue', node.data)
            res.append(node.data)

            #Right subtree in order
            self.inoder_traversal(node.right, res)
        return res

    def postorder_traversal(self, node, res):
        if node != None:
            self.postorder_traversal(node.left, res)
            self.postorder_traversal(node.right, res)
            print('queue', node.data)
            res.append(node.data)
        return res

    def level_order_traversal(self, queue, res= []):

        if queue == [] :
            # it's root
            print('root', self.root.data)
            res.append(self.root.data)
            queue.append(self.root)

        else:
            #Since the node of this level is a queue of arguments, turn it with for
            temp_list, queue = queue, []
            not_none_cnt = 0

            for item in temp_list:
                if item.left is not None:
                    res.append(item.left.data)
                    print('queue', item.left.data)
                    queue.append(item.left)
                    not_none_cnt += 1

                if item.right is not None:
                    res.append(item.right.data)
                    print('queue', item.right.data)
                    queue.append(item.right)
                    not_none_cnt += 1

            if not_none_cnt == 0:
                return #Go back to where you last called this function

        self.level_order_traversal(queue, res)

        return res

Binary tree method

Implemented methods to search for the maximum value, search for the presence or absence of a value, check the size, and check the height. See the comments in the code for points.

bt_method.py


#Binary tree method
class BT_method(BinaryTree):
    def __init__(self, arr):
        super().__init__(arr)

    def max_in_binary_tree(self, node, temp_max):
        """Implementation shows maximum value in parent-child relationship
It is the same even if you LIFO while travers and leave a large value.
Same thing as remembering the maximum value while traversing in a forward search"""
        if node is not None:
            temp_root_val = node.data
            left_val = self.max_in_binary_tree(node.left, temp_max)
            right_val = self.max_in_binary_tree(node.right, temp_max)

            temp_max = max(temp_root_val, left_val, right_val, temp_max)

        return temp_max

    def find_val(self, node, val, flag=False):
        if node != None:
            if node.data == val:
                return True

            else:
                flag_left = self.find_val(node.left, val) #Since the result of recursion is returned by return, it is received as a variable
                flag_right = self.find_val(node.right, val)

                if flag_left or flag_right:
                    return True

        return False


    def size(self, node):
        if node is None: #End counting when node is None
            return 0 #If you return 0, it will not be counted
        else:
            left_cnt = self.size(node.left)
            right_cnt = self.size(node.right)

            return 1 + left_cnt + right_cnt #I (not None) is 1 and the number in the left and right trees (virtual search is realized by a recursive function)


    def hight(self, level=0):
        flag = True
        queue = [self.root]

        while flag:
            level += 1
            temp_list, queue = queue, []
            for node in temp_list:
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)


            flag = any(queue)

        return level

Run

I ran the code as below.

main.py



ins = BinaryTree(range(1,16))

print('--------------------------')
print('start preoder traversal')
print(ins.preoder_traversal(ins.root, []))

print('--------------------------')
print('start inoder traversal')
print(ins.inoder_traversal(ins.root, []))

print('--------------------------')
print('start postoder traversal')
print(ins.postorder_traversal(ins.root, []))

print('--------------------------')
print('start level order traversal')
print(ins.level_order_traversal([]))

#
print('=====================================')

ins2 = BT_method(range(1,16))
print('--------------------------')
print('find max')
print(ins2.max_in_binary_tree(ins2.root, 0))
print('--------------------------')
print('find value')
print('looking for 7', ins2.find_val(ins2.root, 7))
print('looking for 17', ins2.find_val(ins2.root, 17))


#  search size
print('--------------------------')
print('detect node size')
print(ins2.size(ins2.root))

Execution result

The print part tells us the behavior sequentially

....
try inserting  1
Root node is ....
1
....
try inserting  2
In level 2, 2 is inseted
....
try inserting  3
In level 2, 3 is inseted
....
try inserting  4
In level 3, 4 is inseted
....
try inserting  5
In level 3, 5 is inseted
....
try inserting  6
In level 3, 6 is inseted
....
try inserting  7
In level 3, 7 is inseted
....
try inserting  8
In level 4, 8 is inseted
....
try inserting  9
In level 4, 9 is inseted
....
try inserting  10
In level 4, 10 is inseted
....
try inserting  11
In level 4, 11 is inseted
....
try inserting  12
In level 4, 12 is inseted
....
try inserting  13
In level 4, 13 is inseted
....
try inserting  14
In level 4, 14 is inseted
....
try inserting  15
In level 4, 15 is inseted
--------------------------
start preoder traversal
queue 1
queue 2
queue 4
queue 8
queue 9
queue 5
queue 10
queue 11
queue 3
queue 6
queue 12
queue 13
queue 7
queue 14
queue 15
[1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15]
--------------------------
start inoder traversal
queue 8
queue 4
queue 9
queue 2
queue 10
queue 5
queue 11
queue 1
queue 12
queue 6
queue 13
queue 3
queue 14
queue 7
queue 15
[8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15]
--------------------------
start postoder traversal
queue 8
queue 9
queue 4
queue 10
queue 11
queue 5
queue 2
queue 12
queue 13
queue 6
queue 14
queue 15
queue 7
queue 3
queue 1
[8, 9, 4, 10, 11, 5, 2, 12, 13, 6, 14, 15, 7, 3, 1]
--------------------------
start level order traversal
root 1
queue 2
queue 3
queue 4
queue 5
queue 6
queue 7
queue 8
queue 9
queue 10
queue 11
queue 12
queue 13
queue 14
queue 15
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
=====================================
....
try inserting  1
Root node is ....
1
....
try inserting  2
In level 2, 2 is inseted
....
try inserting  3
In level 2, 3 is inseted
....
try inserting  4
In level 3, 4 is inseted
....
try inserting  5
In level 3, 5 is inseted
....
try inserting  6
In level 3, 6 is inseted
....
try inserting  7
In level 3, 7 is inseted
....
try inserting  8
In level 4, 8 is inseted
....
try inserting  9
In level 4, 9 is inseted
....
try inserting  10
In level 4, 10 is inseted
....
try inserting  11
In level 4, 11 is inseted
....
try inserting  12
In level 4, 12 is inseted
....
try inserting  13
In level 4, 13 is inseted
....
try inserting  14
In level 4, 14 is inseted
....
try inserting  15
In level 4, 15 is inseted
--------------------------
find max
15
--------------------------
find value
looking for 7 True
looking for 17 False
--------------------------
detect node size
15

References

Recommended Posts

[Introduction] I tried to implement it by myself while explaining to understand the binary tree
[Introduction] I tried to implement it by myself while explaining the binary search tree.
A super introduction to Django by Python beginners! Part 6 I tried to implement the login function
Try to implement and understand the segment tree step by step (python)
I tried to understand the decision tree (CART) that makes the classification carefully
I tried to analyze the New Year's card by myself using python
I tried to implement the traveling salesman problem
I tried to rescue the data of the laptop by booting it on Ubuntu
I didn't understand the Resize of TensorFlow so I tried to summarize it visually.
I tried to implement PCANet
I tried to implement StarGAN (1)
I tried to implement anomaly detection by sparse structure learning
[Introduction to simulation] I tried playing by simulating corona infection ♬
[Django] I tried to implement access control by class inheritance.
[Introduction to Pandas] I tried to increase exchange data by data interpolation ♬
I wrote it in Go to understand the SOLID principle
I tried to implement the mail sending function in Python
I tried to understand it carefully while implementing the algorithm Adaboost in machine learning (+ I deepened my understanding of array calculation)
I tried to implement Deep VQE
I tried to make it possible to automatically send an email just by double-clicking the [Python] icon
[Introduction to simulation] I tried playing by simulating corona infection ♬ Part 2
I tried to implement adversarial validation
I tried to implement sentence classification by Self Attention with PyTorch
I tried to summarize the commands used by beginner engineers today
I tried to predict by letting RNN learn the sine wave
I tried to implement hierarchical clustering
I tried to solve the shift scheduling problem by various methods
I tried to implement Realness GAN
I tried to move the ball
I tried to estimate the interval.
A super introduction to Django by Python beginners! Part 2 I tried using the convenient functions of the template
I tried to make it possible to automatically send an email just by double-clicking the [GAS / Python] icon
I tried moving the image to the specified folder by right-clicking and left-clicking
When I tried to run Python, it was skipped to the Microsoft Store
I tried to summarize the general flow up to service creation by self-education.
765 I tried to identify the three professional families by CNN (with Chainer 2.0.0)
I tried to implement Bayesian linear regression by Gibbs sampling in python
Matching karaoke keys ~ I tried to put it on Laravel ~ <on the way>
I tried to find the optimal path of the dreamland by (quantum) annealing
I tried to verify and analyze the acceleration of Python by Cython
I tried to summarize the Linux commands used by beginner engineers today-Part 1-
I tried to solve the inverted pendulum problem (Cart Pole) by Q-learning.
I tried to verify the result of A / B test by chi-square test
I tried to implement PLSA in Python
I tried to implement Autoencoder with TensorFlow
I tried to summarize the umask command
I tried to implement permutation in Python
I tried to recognize the wake word
Binary tree traverse is difficult to understand
I tried to summarize the graphical modeling.
I tried to implement ADALINE in Python
I tried to estimate the pi stochastically
I tried to touch the COTOHA API
I tried to implement PPO in Python
I tried to implement CVAE with PyTorch
When I tried to change the root password with ansible, I couldn't access it.
I tried to verify the Big Bang theorem [Is it about to come back?]
I tried to predict the presence or absence of snow by machine learning.
I tried to predict the change in snowfall for 2 years by machine learning
[I'm an IT beginner] I tried my best to implement Linux on Windows
[Introduction to AWS] I tried porting the conversation app and playing with text2speech @ AWS ♪