🌲 🌲 🌲preface:
In binary tree correlation algorithm, for binary tree search and traversal is unavoidable topic “bypass when I did not say 😬”. If you search the binary tree, traversal has not mastered the very clear, so we come together kangkang. The content includes”Recursion and iteration of pre-order, middle-order and post-order traversal of binary tree, as well as depth-first search and breadth-first search“, if these several kinds of master, also hope to see what is wrong, this algorithm rookie is very grateful. 💐
Binary tree traversal
Binary tree traversal includes but is not limited to pre-order, middle-order, back-order, hierarchical order, vertical order traversal, etc. All traversal methods visit all nodes of the binary tree once, and then output the values of nodes in different order. Here only to say the order before and after the sequence and the idea of the sequence traversal, to other ways interested can search oh! 🤡
📋 Concept Summary
- Fore-order traversal: Starting from the root node of the binary tree, the node data is output when the node is reached for the first time, in the direction of first left and then right.
- Middle-order traversal: Starting from the root node of the binary tree, the node data is output when the node is reached for the second time, in the direction of first left and then right.
- Back-order traversal: starting from the root node of the binary tree, the node data is output when the node is reached for the third time, in the direction of first left then right access.
- Hierarchical traversal: Traverses a binary tree from the root node down to the tree level.
Tipes: All traversal modes start at the “root node” of the binary tree. Different traversal modes output the contents of the node at different points in time.
I explode from the first time to learn to traverse when this concept is optimistic about many times just do not understand 😂.
First, each node will be accessed regardless of the traversal method. If the traversal position is compared to a pointer, then the pointer resides at each node three different times:
- Before traversing his left subtree;
- After he recurses his left subtree, before he recurses his right subtree;
- After recursing his right subtree;
So we compare the above concept, exactly every dwell corresponds to what we call pre-order, mid-order, post-order traversal.
- Fore-order traversal –> Root first, from left to right, the root of a tree is always in front of the left subtree, and the left subtree is in front of the right subtree “root, left, right”;
- Middle order traversal –> The root is in the middle, from left to right, the left subtree of a tree is always in front of the root, the root is always in front of the right subtree “left, root, right”;
- Backorder traversal –> root after, from left to back, a number of left subtrees are always in front of the right subtree, right subtree in front of the root “left, right, root”;
🔖 recursive template
The above concept looks very dry, so let’s write a little bit of code to polish it up, starting with the simplest recursion. 🐋
🔵 preorder traversal recursive template
Pre-order traversal means that the root node is in front of the left subtree and the left subtree is in front of the right subtree. Therefore, when traversing, we need to save the root node first, then the left subtree, and finally the right subtree.
// "root, left, right"
arr = []
recursive (root) {
if(! root)return;
arr.push(root.val); // The root node is first
recursive(root.left); // Then the left subtree
recursive(root.right); // Finally, the right subtree
}
Copy the codeOrder traversal recursive template in 🔴
Middle-order traversal means that the left subtree is in front of the root node, and the root node is in front of the right subtree, so all the left subtrees are traversed first, then the root node, and then the right subtree.
// "left, root, right"
arr = []
recursive (root) {
if(! root)return;
recursive(root.left); // Iterate through all the left subtrees
arr.push(root.val); // There is no left subtree at the end. The current node is the root node
recursive(root.right); // Go through all right subtrees for the last time
}
Copy the code🟡 post-order traversal recursive template
Backward traversal means that the left subtree is in front of the left subtree, and the right subtree is in front of the root node, so all the left subtrees are traversed, the right subtree is traversed, and the root node is traversed.
// "left, right, root"
arr = []
recursive (root) {
if(! root)return;
recursive(root.left); // Iterate through all the left subtrees
recursive(root.right); // Go through all the right subtrees.
arr.push(root.val); // There are no left and right subtrees at the end, and the current node is the root node
}
Copy the code🔘 To sum up
Analysis of a wave, but in the code level, it is just to adjust the order of saving node values, but the analysis process is very helpful for the next iteration idea, so I suggest to see more! In addition, the three traversal methods all follow a branch to the deepest part of the tree, and then change the direction to the deepest part of the tree. This is the depth-first search DFS. Preorder, middle order, and post order traversal are all DFS based, and DFS will be discussed later.
💽 Iterative thinking
In fact, binary tree traversal is the most basic problems, mainly in the complex difficulty of the binary tree problem also need more operations. Below we use the idea of iteration to achieve the binary tree before order, order, order after traversal. It’s easy to do it iteratively, just replace the recursive function. But the idea of iterating involves stack data structures, so let’s see. 😊
Iteration: continuously pushing new value stack from old value: in and out
⚾️ sequential traversal iterative method
In this case, the element at the top of the stack will be the left node of the root node, which will be used as the root node of the next level. In this way, the root node will be the first to be removed from the stack.
It’s too dry to look at, let’s add some code to it:
function(root) {
let arr = [];
if(! root)return arr;
let zhan = [];
let newNode = ' ';
zhan.push(root); // The root node is pushed first
while (zhan.length) {
newNode = zhan.pop(); // The top element goes off the stack
arr.push(newNode.val); // Save the contents of the stack element
if (newNode.right) { // The right node is pushed
zhan.push(newNode.right)
}
if (newNode.left) { // The left node is pushed
zhan.push(newNode.left)
}
}
return arr;
};
Copy the codeThe idea of sequential traversal: the root node is pushed before iteration, and immediately after iteration, the right subtree of the pushed element is pushed, then the left subtree is pushed, and then the above process is executed again. “Although the right subtree is first, but because of the stack structure, all left subtrees must be in front of the right subtree”. Tipes: The root node is pushed on the stack before iteration, and then “root, left, right”.
🥎 sequential traversal iterative method
First of all, we should clarify the order of the output nodes in the middle order traversal: “left, root, right”, so we should follow the previous order traversal in reverse order to push the stack? Obviously not. A pre-order traversal is the root node first, so we start at the top of the binary tree and work our way down. So the middle order traversal, the left node is first, and we definitely have to go to the deepest part of the left subtree to find the first node. Then output the content in the order of left node -> root node -> right node, “⚠️ every node we have been talking about can be the root node of the local binary tree”, the above code:
function(root) {
let arr = [];
let zhan = [];
while(root || zhan.length){
while (root) { // push all left subtrees onto the stack
zhan.push(root);
root = root.left;
};
root = zhan.pop(); // The left subtree is empty and the top element of the stack is the root node
arr.push(root.val); // The element that is already out of the stack is the root node of the local binary tree
root = root.right; If there are no nodes after the sequence, the sequence is guaranteed
};
return arr;
};
Copy the codeMiddle order traversal idea: First, all left subtrees are pushed “including the root node”, and when the lowest left subtree is empty, the element is pushed out of the stack as the root node. Since the left node is empty, the root node is directly saved, that is, the element content is popped, and then the right subtree is determined in order to determine whether there is a right subtree. If there is, the right subtree is pushed into the right subtree. Then, the pressed right node is used as the root node of the local binary tree to determine whether there is a left subtree. If there is a left subtree, all the left subtrees are continued to be pushed. Tipes: gives priority to the left subtree to be pushed onto the stack. After all the left subtrees on this branch are pushed onto the stack, the operation of removing the popup element is performed. When removing the popup element, the popup element is saved first, and then the right subtree of the popup element is determined whether there is a left subtree. “Left, root, right.”
🎾 post order traversal iterative method
First of all, let’s make clear the order of the output nodes of the post-order traversal: “left, right, root”, the root node of the post-order traversal is the last, so it is almost the same as the pre-order traversal, just modify the order. When we add an element, we add it from the head of the array, so we make sure that the root node comes last, and then we push it to the left node, and then we push it to the right node, so that the right node goes off the stack first, but since we’re adding the array from the head, the left node comes before the right node.
function(root) {
let arr = [];
if(! root)return arr;
let zhan = [];
let newNode = ' ';
zhan.push(root); // The root node is pushed first
while (zhan.length) {
newNode = zhan.pop(); // The top element goes off the stack
arr.unshift(newNode.val); // Save the contents of the stack element
if (newNode.left) { // The left node is pushed
zhan.push(newNode.left)
}
if (newNode.right) { // The right node is pushed
zhan.push(newNode.right)
}
}
return arr;
};
Copy the codeHere’s another way to write it:
function(root) {
let arr = [];
let zhan = [];
while (root || zhan.length) {
while (root) {
arr.push(root.val);
zhan.push(root);
root = root.right;
};
root = zhan.pop();
root = root.left;
};
return arr.reverse();
};
Copy the codeAll right subtrees are pushed first, and the element content is saved as the element is pushed, and then the left subtree of the unpushed element is pushed. If the left subtree has a right subtree element, the right subtree is pushed and the element content is saved. “Save pushed elements while pushing” finally outputs an array of elements in reverse order. Tipes: Push all right subtrees onto the stack, save the element contents as the stack is pushed, and finally form “root, right, left”, and output in reverse order. After the sequence traversal thought too much, do not sum up the big guys themselves experience “leave a homework ha ha”.
🧩 binary tree search
See this big guy, probably have a problem why binary tree traversal I omitted the sequence traversal 😂. Not really, because binary tree traversal is accompanied by depth-first search, breadth-first search every time. So I want to put the sequential traversal inside the binary tree search.
📋 Concept Summary
- Depth-first traversal (DFS) : Traversal along the depth of the tree. When all edges are explored, it returns to the starting node. It is a blind search, and the shortest path cannot be guaranteed.
- Breadth-first traversal (BFS) : A blind search that starts at the root and traverses a node along its width.
🧠 Thought understanding
To be more specific, let’s start with the sequential traversal of a binary tree:
🌜 DFS
function (root) {
const res = [];
function traversal(root, index) {
if(root ! = =null) {
if(! res[index]) res[index] = [];// If the index layer does not have the corresponding index, a new layer is added
res[index].push(root.val);// Add to the array element of the corresponding layer
traversal(root.left, index + 1); // Continue down
traversal(root.right, index + 1);
}
}
traversal(root, 0); // Use the layer height to locate the position of each layer of the two-dimensional array
return res;
}
Copy the code🌛 BFS
// First in, first out (FIFO)
function(root) {
const all = [];
if(! root)return all;
const one = [];
one.push(root);
while(one.length ! = =0) {
let lengthA = one.length; // Save the number of nodes in a layer
all.push([]); // Save the node content of this layer
for (let i = 0; i < lengthA; i++) { // Iterate through each node of this layer
let getOne = one.shift(); // fetch from the header
all[all.length - 1].push(getOne.val);
// Add the next layer in order from the end of the array
if (getOne.left) {
one.push(getOne.left);
};
if (getOne.right) {
one.push(getOne.right);
};
};
};
return all;
};
Copy the code💐 💐 💐conclusion:
Finally finished, as an algorithm dish chicken, this thing to write my full head sweat 😢. But it’s a little summary, a little consolidation. The next encounter will not directly give up, at least can struggle a ha ha. After all, it is algorithm-based dish chicken, if the content of the article is wrong, I hope you pointed out, about DFS and BFS written in a variety of ways, I hope you teach me, thank you very much. Finally, I wish you study and progress, a successful career! 🎆 🎆 🎆