413 binary tree Foundation

1、 The species of binary trees

There are two main forms of binary tree in the process of solving problems ： Full binary tree and Perfect binary tree .

1.1、 Full binary tree

Full binary tree ： If a binary tree has only a degree of 0 The node and degree of are 2 The node of , And the degree is 0 On the same layer , Then this binary tree 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 .

1.2、 Perfect binary tree

Definition ： In a complete binary tree , Except that the lowest node may not be full , The number of nodes in each layer reaches the maximum , And the nodes of the lowest layer are concentrated in the leftmost positions of the layer .

Priority queue It's actually a Pile up , A heap is a complete binary tree , At the same time, ensure the order of the parent-child nodes .

1.3、 Binary search tree （BST）

Binary search tree has numerical value , The binary search tree is an ordered tree .

• If its left subtree is not empty , Then the value of all nodes in the left subtree is less than the value of its root node ;
• If its right subtree is not empty , Then the value of all nodes in the right subtree is greater than the value of its root node ;
• Its left 、 The right subtree is also a binary sort tree

The next two trees are search trees ：

1.4、 Balanced binary search trees （AVL）

Balanced binary search trees ： Also known as AVL（Adelson-Velsky and Landis） Trees , And has the following properties ： It's an empty tree or its The absolute value of the height difference between the left and right subtrees does not exceed 1, also The left and right subtrees are both balanced binary trees .

Pictured ：

The last one It's not an equilibrium binary tree , Because of its The absolute value of the height difference between the left and right subtrees exceeds 1.

C++ in map、set、multimap,multiset The underlying implementation of is a balanced binary search tree （ Red and black trees ）, therefore map、set The time complexity of adding and deleting operations is logn;

Be careful ：unordered_map、unordered_set,unordered_map、unordered_map The underlying implementation is Hashtable .

2、 Binary tree storage

Binary trees can be stored in chains , It can also be stored sequentially .

Chained storage uses pointers , The way of sequential storage is to use arrays .

Sequential storage Elements in Memory is continuously distributed Of , and Chain store By means of The needle connects the nodes scattered at various addresses in series .

2.1、 Chain store

2.2、 Array storage

The method of sequential storage is shown in the figure ：

How to traverse a binary tree with an array ？

• If the array subscript of the parent node is i, So its left child is i * 2 + 1, The right child is i * 2 + 2.

2.3、 The traversal of binary tree

There are two main ways to traverse a binary tree ：

• Depth-first traversal ： Go deep first , Meet the leaf node and go back .
• Breadth first traversal ： Layer by layer to traverse .

Depth-first traversal ：

• The former sequence traversal （ Recursive method , Iterative method ）
• In the sequence traversal （ Recursive method , Iterative method ）
• After the sequence traversal （ Recursive method , Iterative method ）

Breadth first traversal ：

• Level traversal （ Iterative method ）

Depth first traversal ： There are three orders , Traversal in front, middle and back order ; The former, the middle and the latter refer to The location of the intermediate node That's all right. .

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

Two fork tree Depth first and breadth-first Traverse Realization way ：

• Let's do the related topics of binary tree , Often use recursively To achieve Depth-first traversal , That is to say, before, in and after the implementation of traversal , Use recursive It's more convenient .
• Stack is actually an implementation structure of recursion , That is to say, the logic of traversal before, during and after the sequence is actually OK With the help of stack, it is implemented in a non recursive way .
• Breadth first traversal General implementation of Use queues to implement , This is also determined by the first in first out feature of the queue , Because of the need fifo Structure , To traverse the binary tree layer by layer .

3、 The definition of binary tree

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