This is the seventh day of my participation in the August More Text Challenge. For details, see “August More Text Challenge”.
preface
“The colours of August are of gold, bright and precious; The colours of August are brewed with sunshine, fragrant and brilliant.”
In the future, I wish you to adjust yourself to the best state, slowly work hard, slowly get better
define
A binary tree is an ordered tree whose node degree is less than 2. It is one of the simplest and most important trees.
The recursion of binary tree is defined as: binary tree is an empty tree, or a non-empty tree composed of a root node and two non-intersecting left and right subtrees called roots respectively; The left subtree and the right subtree are both binary trees
Binary tree as a very basic but very important data structure, in some scenarios or more important. So the importance of binary trees is self-evident.
Here’s an example:
var binaryTree = {
value: 1,
left: {
value: 2,
left: {
value: 4
}
},
right: {
value: 3,
left: {
value: 5,
left: {
value: 7
},
right: {
value: 8
}
},
right: {
value: 6
}
}
}
Copy the code
The recursive traversal
The first sequence traversal
Access root – > traverse the left subtree – > traverse the right subtree;
var preListRec = []; Var preOrderRec = function(node) {if (node) {preListRec. Push (node.value); PreOrderRec (node.left); PreOrderRec (node.right); // preOrderRec(node.right); }} preOrderRec(tree); console.log(preListRec)Copy the code
In the sequence traversal
Traverse the left subtree – > access root – > traverse the right subtree;
var inListRec = []; Var inOrderRec = function(node) {if (node) {inOrderRec(node.left); InListRec. Push (node.value); InOrderRec (node.right); }} inOrderRec(tree); console.log(inListRec);Copy the code
After the sequence traversal
Traversing the left subtree – > traversing the right subtree – > access root;
var postListRec = []; Var postOrderRec = function(node) {if (node) {postOrderRec(node.left); // Recursively traverse the left subtree postOrderRec(node.right); PostListRec. Push (node.value); }} postOrderRec(tree); console.log(postListRec);Copy the code
Non-recursive traversal
Breadth first traversal
Breadth-first traversal starts at the first level (root) of the binary tree and starts from the top to the bottom. Nodes are accessed from left to right in the same layer
Implementation principle:
Using arrays to simulate queues, you first queue the root node. When the queue is not empty, execute the loop: take out a node of the queue, if the node has a left subtree, then the left subtree of the node is stored in the queue; If the node has a right subtree, the right subtree of the node is queued
var breadthList = []; Var breadthTraversal = function(node) {if (node) {var que = [node]; Var que = []; que.push(node); while (que.length ! == 0) {// Check whether the queue is empty. Node = que. Shift (); String breadthList.push(node.value); string breadthList.push(node.value); If (node.left) que. Push (node.left); If (node.right) que. Push (node.right); // Put the right subtree in the queue if it exists}}} breadthTraversal(tree); console.log(breadthList);Copy the code
conclusion
If this post helped you, feel free to like ๐ and follow โญ๏ธ
If there are any mistakes in this article, please correct them in the comments section ๐๐.