preface
Suddenly recently rediscovered the brush algorithm in school and the fun of learning data structure, failed to play these foundation at school, so I decided at the time of learning technology framework, at the same time also learn to review previous basic skills, these are especially important in the interview, the framework can learn, program does algorithm + data structure, technology with official documentation can quickly get started, But fundamentals are a cumulative process, and it is the fundamentals that many companies value. Ok, without further ado, let’s start today’s main character reconstruction of binary tree, that is, according to the preorder traversal and middle order traversal to restore a complete binary tree.
Introduction to Basic Knowledge
First, we need to learn some basic facts about binary trees. The binary tree is shown below, which is eachMaximum number of rootsonlyTwo childrenThe tree formed from top to bottom isBinary treeOne of the things THAT I always get confused about is that the child on the left is bigger than the child on the right, but the one that satisfies this property in real time isOrdered binary treeWe’re just talking about basic binary trees. Here’s a treeBinary tree.
Preorder traversal (preorder traversal)
The rule of preemptive traversal is root left and right, so the result of preemptive traversal is 6 > 3 > 1 > 11 > 8 > 2 > 5 > 7 > 10 > 13 > 12. Because the root of the binary tree is 6, so find the first 6, according to the laws of the root around looking for the left child, find 3, note that this is not directly take 3, but with 3 as the root node in the left subtree again according to law about the root to traverse, in three sub tree, 3 for the root node, so after 6 is 3, find the root, and didn’t find, And then I go through the left subtree of 3, which is the root tree of 1, and then I follow the rule and I get to 1, and THEN I go back to 11, and 11 has no children, so I’m done on the left for 1, and I go to the right for 8, and then for 3 I’m done on the left, so the next node is right, So I’m going to find 2, and then for 6, I’m done on the left, and I’m done on the right, The result is 5 > 7 > 10 > 13 > 12, so the final result is 6 > 3 > 1 > 11 > 8 > 2 > 5 > 7 > 10 > 13 > 12
In the sequence traversal
The rule of middle order traversal is left root right, so the result of middle order traversal is 11 > 1 > 8 > 3 > 2 > 6 > 7 > 5 > > 13 > 10 > 12. Middle order traversal is similar to the preceding order, but the rule of left root right is changed
After the sequence traversal
The rule of backorder traversal is left and right roots, so the result of backorder traversal is 11 > 8 > 1 > 2 > 3 > 7 > 13 > 12 > 10 > 5 > 6. The backorder traversal is similar to the front order, but the rule is changed to left and right roots
PS: Memorization tips, observe the position of the roots, the former root in front, the middle in the middle, the latter in the last, left is always in front of right.
Topic describes
The foreorder traversal and middle order traversal are given to restore a complete binary tree. Input: 6 -> 3 > 1 > 11 > 8 > 2 > 5 > 7 > 10 > 13 > 12 Input: 6 -> 3 > 1 > 11 > 8 > 5 > 7 > 10 > 13 > 12
6 / \ 3 5 / \ / 12 7 10 / \ / \ 11 8 13 12Copy the codeReconstruction of binary tree related ideas
According to the principle that the first of the preceding traversal is the root node, go to the middle traversal to find the root node, record the current position, because the middle traversal is left root right. 1, 6 -> 3 > 1 > 11 > 8 > 2 > 5 > 7 > 10 > 13 > 12, the first one is 6, so 6 is the root node of the main tree, so we can use the root node to find the middle order traversal. 11 > 1 > 8 > 3 > 2 > 6 > 7 > 5 > 13 > 10 > 12, then the left of 6 is the middle-order traversal of the left subtree, and the right is the middle-order traversal of the right subtree. The left subtree must be traversed before the right subtree is traversed. The left subtree must be traversed before the right subtree. , which can be obtained from our rule that left comes before right, that is to say, the right subtree traversal results of the preceding sequence traversal are clustered at the end, The left subtree is traversed by 3 > 1 > 11 > 8 > 2, and the left subtree is traversed by 3 > 1 > 11 > 8 > 2. 3, so let’s clarify the idea, at this time our current sub-problem is not according to the preceding order traversal 3 > 1 > 11 > 8 > 2, middle order traversal 11 > 1 > 8 > 3 > 2, to restore the binary tree, whether the problem is the same as the main problem ^-^. 4, summing up the above results, in general is that differentiate the first order and the order of the subtree, then go to tree also atoms, subtree problem in row molecular tree before the order and the order, the Russian dolls, all in all is according to this problem, we also is the son and the main problems, you can use the home address, the key is to divide the order and the order out before.
Code implementation
Just look at the main core code, the rest is just for the output tree, for good ^-^
package com.cj;
import java.util.Arrays;
import java.util.Scanner;
/** * the reconstruction of binary tree ** from the antecedent and middle antecedent traversal to infer the binary tree * 6 * / \ * 3 5 * / \ / \ * 12 7 10 * / \ /* 11 8 13 12 ** antecedent traversal 6 -> 3 > 1 > 11 > 8 > 2 > 5 > 7 > 10 > 13 > 12 * Middle order traversal 11 > 1 > 8 > 3 > 2 > 6 > 7 > 5 > 13 > 10 > 12 * Rear order traversal 11 > 8 > 1 > 2 > 3 > 7 > 13 > 12 > 10 > 5 > 6 * * conjecture binary tree */
public class Main {
// Preorder traversal storage
private static Integer []preOrderStringArray;
// Sequence traversal storage
private static Integer []middleOrderStringArray;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Please enter the prior traversal of the binary tree (separated by commas) :");
// Process input
preOrderStringArray = Arrays.stream(sc.nextLine().split(",")).map(Integer::valueOf).toArray(Integer[]::new);
System.out.println("Please enter a middle-order traversal of the binary tree (separated by commas) :");
// Process input
middleOrderStringArray = Arrays.stream(sc.nextLine().split(",")).map(Integer::valueOf).toArray(Integer[]::new);
// Call the method to get the binary tree
Node node = getTwoBranchTree(0,preOrderStringArray.length - 1.0,middleOrderStringArray.length - 1);
// Prints the binary tree
show(node);
}
/** * core code *@param preI
* @param preJ
* @param middleI
* @param middleJ
* @return* /
private static Node getTwoBranchTree(int preI,int preJ,int middleI,int middleJ){
// The first node in the forward traversal is the root node
Node root = new Node(preOrderStringArray[preI]);
// If preI and preJ are equal, the subtree has only one node
if(preI == preJ){
return root;
}
// The order traverses the index position of the root
int index = 0;
// Start to delimit the range of subtrees in order traversal
for (int i = middleI ; i < middleJ ; i++){
if(root.value == middleOrderStringArray[i]){
index = i;
break; }}/** * to recurse to the left subtree of the current logic, the first one is the root, So the index of the current root node is preI, notice that index is the index position of the middle traversal root node, and according to the preceding traversal is (' the index position of the root node + 1 ', 'the index position of the root node + the length of the left subtree'), the left subtree length is (index) -middlei) gives the index range of the preceding order (preI + 1,preI + (index - middleI)). The traversal index range of the left subtree is the first to the position before the root (middleI,index - 1) */
root.left = getTwoBranchTree(preI + 1,preI + (index - middleI),middleI,index - 1);
/** * preI + (index-middlei + 1),preJ); /** * preJ (index - middleI + 1); /** * preJ (index - middleI + 1) So index + 1,middleJ */
root.right = getTwoBranchTree(preI + (index - middleI + 1),preJ,index + 1,middleJ);
return root;
}
// Get the number of layers of the tree
private static int getTreeDepth(Node root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
}
// Write the computed format to an array for easy output
private static void writeArray(Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// Make sure the input tree is not empty
if (currNode == null) return;
// Save the current node to a two-dimensional array
res[rowIndex][columnIndex] = String.valueOf(currNode.value);
// Calculate the current level in the tree
int currLevel = ((rowIndex + 1) / 2);
// If you reach the last layer, return
if (currLevel == treeDepth) return;
// Calculate the interval between the current row and the next row, each element (the interval between the next row's column index and the current element's column index)
int gap = treeDepth - currLevel - 1;
// Judge the left son. If there is a left son, record the corresponding "/" and the value of the left son
if(currNode.left ! =null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// Judge the right son, if there is a right son, then record the corresponding "\" and the value of the right son
if(currNode.right ! =null) {
res[rowIndex + 1][columnIndex + gap] = "\ \";
writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth); }}// Print the binary tree by traversing the array
private static void show(Node root) {
if (root == null) System.out.println("EMPTY!");
// Get the depth of the tree
int treeDepth = getTreeDepth(root);
// The width of the last line is 2 to the power of n minus 1 times 3, plus 1
// As the width of the entire two-dimensional array
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
// Use an array of strings to store the elements that should be displayed at each location
String[][] res = new String[arrayHeight][arrayWidth];
// Initializes the array with a space by default
for (int i = 0; i < arrayHeight; i ++) {
for (int j = 0; j < arrayWidth; j ++) {
res[i][j] = ""; }}// Process the entire tree recursively, starting from the root node
// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
writeArray(root, 0, arrayWidth/ 2, res, treeDepth);
// At this point, all the elements that need to be displayed are stored in a two-dimensional array, which can be spliced and printed
for (String[] line: res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i ++) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i += line[i].length() > 4 ? 2: line[i].length() - 1; } } System.out.println(sb.toString()); }}// Binary tree node definition
static class Node{
// The value of the current node
private int value;
/ / the left child
private Node left;
/ / right child
private Node right;
public Node(int value){
this.value = value;
}
@Override
public String toString(a) {
return "Node{" +
"value=" + value +
", left=" + left +
", right=" + right +
'} '; }}}Copy the codeconclusion
I haven’t written an article for a long time, and I still have to summarize what I have learned. In the future, I will send at least one article in a week, and the other two or two traversals can be derived from the binary tree. Here is only the front order + middle order, and if there are any mistakes, we welcome to correct them. The road to data structures and algorithms is slow, and I will search up and down.