preface

The front-end algorithm series is a record of my algorithm learning, which mainly analyzes the learning algorithm knowledge from common algorithms, data structure, algorithm thinking and common skills. It realizes deliberate practice through LeetCode platform, and practices Feynman learning method through digging gold and the output of STATION B. I will update the quality content and synchronously update it to Nuggets, B station and Github in the future, so as to record the complete process of learning algorithm. Welcome to communicate, like and collect more, let us make progress together, daydayUp 👊

Directory address: directory section

Code address: Github

Related video address: Bilibili

A concept,

(1) Trees

Trees are very common in our daily lives, but in the algorithmic world, they are also a data structure that we often need to use. And that’s where we started moving from linear table structures to more complex data structures.

The difference between a tree in a computer and a tree in real life is that it is more like a buried root, starting at a root node and spreading down, like a forked linked list in terms of data structure.

(2) degree

Degree: The number of edges per node

Entry: The number of edges ending at this node

Output: The number of edges starting with this node

(3) traversal

Traverse the way
The former sequence traversal	The root	On the left	right
In the sequence traversal	On the left	The root	right
After the sequence traversal	On the left	right	The root

For example, in order traversal, when traversing a binary tree

Outputs the root node first, then the left node, then the right node

⚠️ Note that if the left node has children, the children need to be traversed in the order of the left and right root

The traversal process follows the depth-first principle

In the above picture, the output should be as follows:

// A, B, C, D, E, F
// Output the root node A in order, then since the left node of A has children, depth first,
B, C, D, E, F
Copy the code

In addition to the above three traversal methods, there is another breadth-first traversal method for trees: sequence traversal

Similarly in the above figure, the output should be:

// A B E C D F
// Output each layer in left-to-right order
Copy the code

In fact, several traversal methods of binary tree represent different ways of dealing with problems:

Sequence traversal means: breadth first, the other three are depth first

The preceding traversal mode represents: from the top down

Back-order traversal means: bottom-up

(iv) Binary tree

1, define,

1. The degree of each node is 2 at most

2. There is 1 more node with degree 0 than node with degree 2

2, legend

Some of the more common binary trees are shown below

Full binary tree

Except for the last layer, the degree of each node is 0, and the degree of each node is 2, that is, there are left and right subtrees

Complete binary tree

Only the right part of the last level is missing nodes. Note that the last level of the binary tree requires continuous nodes on the left. In addition, if the height of a binary tree is h, then the h-1 layer of a complete binary tree should be a full binary tree

3, features,

1. At the NTH level of a binary tree, there are at most 2 n-1 nodes

2. If the height of the binary tree is k, then the binary tree has at most 2 to the k minus 1 nodes

In a complete binary tree, if n nodes exist, then the height of the binary tree is log2n + 1 (rounded down).

Second, the implementation

Above we have a general understanding of the basic knowledge of binary tree, next we will specific implementation, in fact, the implementation of binary tree is very simple, we only need to achieve one of the nodes can be

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}
Copy the code

Ha ha slightly perfunctory, in the next article we come to specific realization of the binary tree several traversal way! See you next time!

TODO deep search DFS and wide search BFS binary tree classical problem big top heap and small top heap tore AVL tree