In the previous section, we learned about the linked list. In this section, we learn a new data structure, the binary tree. For the linked list, it has an attribute time value val, and a pointer to the next linked list node next, and the binary tree actually has one more attribute than it. Its The shape looks like this:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self. left = left
self.right = right
head=TreeNode(1,TreeNode(2),TreeNode(3))
print(head.val)#1
print(head. left. val)#2
print(head.right.val)#3
The binary tree formed in this way is shown in the figure below:
As before, we first introduce the traversal method of the binary tree
Binary tree traversal
There are three recursive traversal methods and one layer order traversal method for binary trees, all of which need to be mastered. We use the binary tree shown in the figure below to explain:
Preorder traversal
The preorder traversal method is
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self. left = left
self.right = right
@staticmethod
def pre_order(head):
if head is None: return
print(head. val)
TreeNode. pre_order(head. left)
TreeNode. pre_order(head. right)
head=TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3,TreeNode(6),None))
TreeNode. pre_order(head)
The answer is 1 2 4 5 3 6. Is there a correct answer? It doesn’t matter if the answer is not correct, because a new knowledge point recursion is involved here. Let’s analyze how the code runs according to the current binary tree:
As shown in the figure below, the rectangular thing is called a stack, and the function is the pre_order on the right. The function can only run correctly after being pushed into the stack. 
Let’s take a look at the process of pushing into the stack. After entering the stack, pre_order(1) starts to run. The first sentence is not empty. Continue to run down. The second sentence prints 1, and the third sentence is designed with a recursive function. A new one needs to be created. The function pre_order(2), and it is necessary to continue the operation of the fourth sentence after pre_order(2) is pushed into the stack and run
After continuing pre_order(2) into the stack, repeat the process just now and create pre_order(4) in the third sentence
Then pre_order(4) is pushed onto the stack, and the above process is repeated to create pre_order(None), because there is no left child node for the node 4, right?
Continuing the process just now, pre_order(None) is pushed into the stack, and the code starts to be executed. The entire code has been executed at the first sentence, and the function after execution will be popped.
After popping out of the stack, the function on the top of our stack is pre_order(4). Do you remember which line of code this function ran last time? It is the third sentence, so now we will continue to run the fourth sentence of code. If the node 4 still has no right node, then the generated function is still pre_order(None), which is exactly the same as the above process, so I won’t repeat it here. We read on
After another pre_order(None) is popped out of the stack, pre_order(4) is all executed, so pre_order(4) should also be popped out of the stack
Next, after pre_order(4) pops out of the stack, the function at the top of the stack is pre_order(2). This function was also executed to the third sentence last time, and it is time to execute the fourth round. Here, another function pre_order( 5), because the right node of 2 is 5
Then pre_order(5) is pushed into the stack and prints 5, and finally starts to print the right node of node 1. The analysis process is the same as above. You can analyze it yourself
The final print result is 1, 2, 4, 5, 3, 6
Inorder traversal
After understanding recursion and pre-order traversal, in-order traversal is very simple. Its code is as follows, but the output statement is changed to a position:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self. left = left
self.right = right
@staticmethod
def in_order(head):
if head is None: return
TreeNode.in_order(head.left)
print(head. val)
TreeNode.in_order(head.right)
head=TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3,TreeNode(6),None))
TreeNode.in_order(head)
His output result is: 4 2 5 1 6 3, because his printing method is “left, root, right” will first output the node of the left subtree
Post-order traversal
Is it possible to write post-order traversal by yourself? It’s really simple.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self. left = left
self.right = right
@staticmethod
def post_order(head):
if head is None: return
TreeNode. post_order(head. left)
TreeNode. post_order(head. right)
print(head. val)
head=TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3,TreeNode(6),None))
TreeNode. post_order(head)
His output is: 4 5 2 6 3 1
In-class testing
Can you write the preorder, inorder and subsequent traversal of the following tree without using code? You can use the code to test it later:
Layer order traversal
Do you feel that the traversal of the front, middle and back order has no rules at all, as if it is for the computer to see, as a person, I want to traverse it to be 1, 2, 3, 4, 5, 6, 7, 8, etc. This is about level order traversal.
The idea is this, we first put the head node into the container, and then add it to the container when traversing to the left node and right node of the head node, after the left node and right node of a node have been traversed, put this The node is thrown out of the container. Now there are only the left and right nodes of the head node left in the container. Let’s continue the above operation and perform the above operation on these two nodes according to the principle of first come first served until there is nothing left in the container
Think about what data structure we should use to find the first node to enter? The characteristics of the stack (as mentioned in the pre-order traversal, the stack has only one opening to enter and exit) is first-in-last-out, which is contrary to our usage, so we should use a queue (a queue is a first-in-first-out data structure, like a pipe) The add function enters from the head of the pipe, and the poll function takes out from the back of the pipe. The stack and queue in python are implemented by deque double-ended queue. Remember to import here)
import collections #Don't forget to import container tools
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self. left = left
self.right = right
@staticmethod
def post_order(head):
if head is None: return
TreeNode. post_order(head. left)
TreeNode. post_order(head. right)
print(head. val)
@staticmethod
def levelOrder(root):
if root == None: return [] # special judgment
que = collections.deque([root]) # double-ended queue, initialize and throw root into the queue
ans = []
while len(que) != 0:
size = len(que)
level = []
for _ in range(size): # traverse the current layer nodes
cur = que.popleft() # Pop the queue from the left
level.append(cur.val) # Add the current node value to the list of the current layer
if cur.left != None: que.append(cur.left)
if cur.right != None: que.append(cur.right)
ans.append(level) # Add the results of the current layer to the answer list
return ans
@staticmethod
def printList(list):
for subList in list:
print(subList)
head=TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3,TreeNode(6),None))
ans=TreeNode. levelOrder(head)
TreeNode. printList(ans)
The result is printed out as shown in the figure below:
