Binary tree knowledge

Binary trees have two main forms ： Full binary tree and full binary tree

Full binary tree

 If a binary tree has only a degree of 0 The sum is 2, And the degree is 0 A binary tree whose nodes are all on the same layer is a full binary tree 

This binary tree is full of binary trees , It can also be said that the depth is k, Yes 2^k-1 A binary tree of nodes

Perfect binary tree

 In complete binary tree ,
1. Except that the bottom layer may not be filled ,
2. Every other layer is filled with ,
3. If there is no left subtree in the bottom layer, the following nodes cannot have 

If the bottom layer is No h layer , Then the layer contains 1~ 2^(h-1) Nodes

Binary search tree

 characteristic ：
1. Binary search tree is an ordered tree 
2. If his left sub tree is not empty , The value of the left subtree is less than the root node 
3. If his right subtree is not empty , The value of the right subtree is greater than the root node 

Balanced binary search trees

 The absolute value of the height difference between an empty tree or its left and right sub trees does not exceed 1,
 And both the left and right subtrees are a balanced binary tree 

1.C++ in map、set、multimap,multiset The underlying implementation of is a balanced binary search tree
2.unordered_map、unordered_set,unordered_map、unordered_map The underlying implementation is a hash table

Storage method of binary tree

1. Chain store -----> Linked list 
2. Sequential storage ----> Array 

The traversal of binary tree

 Binary tree mainly has the following two traversal methods ：
1. Depth-first traversal ： Go deep first , Meet the leaf node and go back 
2. Breadth first traversal ： Layer by layer to traverse 

With these two kinds of traversal, we can expand the following traversal

Depth-first traversal ：

1. The first sequence traversal 
2. In the sequence traversal 
3. Subsequent traversal 

Breadth first traversal

1. Level traversal 

Here, in front, in the back , In fact, it refers to the traversal order of intermediate nodes , As long as you remember The first, middle and last order refers to the position of the intermediate node, that is, the parent node

The former sequence traversal ： Around the middle
In the sequence traversal ： Left middle right
After the sequence traversal ： Right and left

Experience ：

1. When we do binary tree, we often use recursive method to realize depth first traversal , That is to realize the pre -, middle -, and post traversal ,
2. Stack is actually an implementation structure of recursion , In other words, the logic of pre -, middle - and post order traversal can actually be implemented in a non recursive way with the help of the stack 
3. The breadth of traversal queue is generally realized by , This is determined by the first in first out characteristic node of the queue , In this way, we can traverse the binary tree layer by layer 

struct TreeNode {
    
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {
    }
};