The recursion of binary tree realizes pre -, middle – and post-order traversal

Reserve knowledge

What is a binary tree

To quote Wikipedia:

A Binary tree is a tree with at most two branches per node (i.e., no node with a branching degree greater than 2). Branches are usually referred to as “left subtrees” or “right subtrees”. The branches of a binary tree have left and right order and cannot be reversed at will.

What are pre-middle and post-order traversals

In popular terms, for each tree, the top position of the tree is traversed in front of the two children, in the middle, and in the back (the order of children must be the left child before the right child). In the binary tree above, for the small tree ABC, ABC is pre-ordered traversal, BAC is middle-ordered traversal, and BCA is post-ordered traversal.

The implementation of binary tree

• Chain store

Through linked list structure to achieve. Based on the linked list structure, children can be found from each point. Most binary trees are implemented through linked lists.

• Sequential storage

This is done in an array. It only works with complete binary trees. The index relationship between parent node and child node is:

JavaScript recursive implementation

The former sequence traversal

function pre(tree, fatherIndex) { if (! tree[fatherIndex]) { return; } console.log(tree[fatherIndex]); let leftChildrenIndex = 2 * fatherIndex + 1; let rightChildrenIndex = 2 * fatherIndex + 2; pre(tree, leftChildrenIndex); pre(tree, rightChildrenIndex); }Copy the code

In the sequence traversal

function middle(tree, fatherIndex) { if (! tree[fatherIndex]) { return; } let leftChildrenIndex = 2 * fatherIndex + 1; let rightChildrenIndex = 2 * fatherIndex + 2; middle(tree, leftChildrenIndex); console.log(tree[fatherIndex]); middle(tree, rightChildrenIndex); }Copy the code

After the sequence traversal

function next(tree, fatherIndex) { if (! tree[fatherIndex]) { return; } let leftChildrenIndex = 2 * fatherIndex + 1; let rightChildrenIndex = 2 * fatherIndex + 2; next(tree, leftChildrenIndex); next(tree, rightChildrenIndex); console.log(tree[fatherIndex]); }Copy the code

Recursion sequence

As you can see from the front, middle, and back traversal functions above, the recursive pattern is written exactly the same, except that console.log is in a different position, thus achieving three sequential printing. Why is that? The answer is recursive order. Recursive order, as the name suggests, is the order of recursions.

So how do we use recursive order to solve the front, middle, and back traversal? As an example, check out the following image:

According to the code, each node goes through three times, and of these three times, which print determines what traversal is; The route through is as follows:

The reason each node goes through three times is because the function, inside the function itself, calls itself twice.