Article directory
-
-
- 1. Introduction
-
- 1. Full binary tree
- 2. Complete binary tree
- 3. Binary search tree
- 4. Balanced Binary Search Tree
- Two. Binary tree front, middle and back order traversal
- 3. Binary tree definition
-
- 1. Chain storage
- 2. Sequential storage
- 4. Binary tree recursive traversal
-
- 1. Preorder traversal implementation
- 2. Inorder traversal implementation
- 3. Post-order traversal implementation
- 5. Binary tree iterative traversal
-
1. Introduction
1. Full binary tree
Full binary tree: If a binary tree has only nodes with degree 0 and nodes with degree 2, and the nodes with degree 0 are on the same level, then this binary tree is a full binary tree, which can also be said to have a depth of k. A binary tree with 2^k-1 nodes.
2. Complete binary tree
The definition of a complete binary tree is as follows: In a complete binary tree, except for the bottom node that may not be filled, the number of nodes in each layer reaches the maximum value, and the nodes in the bottom layer are all concentrated in the leftmost positions of the layer. If the bottom layer is the hth layer, then this layer contains 1~ 2^(h-1) nodes, as shown in the figure below:
The heap is a complete binary tree, while ensuring the order relationship of parent and child nodes.
3. Binary search tree
A binary search tree is an ordered tree:
- If its left subtree is not empty, the values of all nodes on the left subtree are less than the value of its root node;
- If its right subtree is not empty, the values of all nodes on the right subtree are greater than the value of its root node;
- Its left and right subtrees are also binary sorted trees
The following two trees are binary search trees:
4. Balanced binary search tree
Balanced binary search tree: also known as AVL (Adelson-Velsky and Landis) tree, and has the following properties:It is an empty tree or the absolute value of the height difference between its left and right subtrees does not exceed 1 , and both left and right subtrees are a balanced binary tree.
As shown in the picture:
The last one is not a balanced binary tree because the absolute value of the height difference between its left and right subtrees exceeds 1.
2. Binary tree front, middle and back order traversal
Looking at the order of the intermediate nodes below, you can find that the order of the intermediate nodes is the so-called traversal method:
- Preorder traversal: middle left
- Inorder traversal: left center right
- Post-order traversal: left, right, middle
For example, as shown in the figure below:
3. Binary tree definition
Binary tree is a basic data structure. Binary tree has two storage methods, sequential storage and chain storage. Sequential storage uses an array to store, and linked storage uses a linked list to store. Compared with the linked list binary tree node, there is one more pointer, and there are two pointers, pointing to the left and right children.
1. Chain storage
Linked storage uses pointers to connect nodes distributed at various addresses in series. Linked storage is shown in the figure:
Define the root node code as follows:
class TreeNode:
def __init__(self, value):
self. value = value
self. left = None
self.right = None
2. Sequential storage
Use arrays to store binary trees, and the sequential storage method is shown in the figure:
How to use array to store binary tree traversal?
If the array subscript of the parent node is i, then its left child is i * 2 + 1, and its right child is i * 2 + 2.
4. Binary tree recursive traversal
Introduce the three elements of a recursive algorithm. Every time you write recursion, write according to these three elements, which can ensure that you can write the correct recursive algorithm:
-
Determine the parameters and return values of the recursive function: Determine which parameters need to be processed during the recursion process, then add this parameter to the recursive function, and also specify what the return value of each recursion is to determine the recursive function The return type of .
-
Determine the termination condition: After writing the recursive algorithm, when it is running, it often encounters a stack overflow error, that is, the termination condition is not written or the termination condition is written incorrectly. The operating system also uses a stack structure to save each layer Recursive information, if the recursion is not terminated, the memory stack of the operating system will inevitably overflow.
-
Determine the logic of single-level recursion: Determine the information that needs to be processed for each level of recursion. Here, the process of calling itself repeatedly to achieve recursion will also be repeated.
1. Preorder traversal implementation
from typing import List
###Tree node data structure definition
class TreeNode:
def __init__(self, val):
self.val = val
self. left = None
self.right = None
# Preorder traversal - recursion - preorder traversal of LC144_ binary tree
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
# save the result
result = []
def traversal(root: TreeNode):
if root == None:
return
result.append(root.val) # Preamble
traversal(root.left) # left
traversal(root.right) # right
traversal (root)
return result
2. Inorder traversal implementation
from typing import List
###Tree node data structure definition
class TreeNode:
def __init__(self, val):
self.val = val
self. left = None
self.right = None
# Inorder traversal - recursion - inorder traversal of LC94_ binary tree
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
result = []
def traversal(root: TreeNode):
if root == None:
return
traversal(root.left) # left
result.append(root.val) # in order
traversal(root.right) # right
traversal (root)
return result
3. Post-order traversal implementation
from typing import List
###Tree node data structure definition
class TreeNode:
def __init__(self, val):
self.val = val
self. left = None
self.right = None
# Post-order traversal - recursion - post-order traversal of LC145_ binary tree
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
result = []
def traversal(root: TreeNode):
if root == None:
return
traversal(root.left) # left
traversal(root.right) # right
result.append(root.val) # Postorder
traversal (root)
return result
5. Binary tree iterative traversal
- Next section: Python implements binary tree iterative traversal