Today, let’s write about the mutual search methods of pre-order traversal, in-order traversal and post-order traversal.
First of all, we need to know the order of pre-order traversal, in-order traversal and post-order traversal:
1. Preorder traversal (order around the root): ①Visit the root node
②Traverse the left subtree in order
③Traverse the right subtree in order
2. In-order traversal (left root and right order): ① In-order traversal of the left subtree
②Access the root node
③In-order traversal of the right subtree
3. In-order traversal (order of left and right roots): ① Post-order traversal of the left subtree
②Post-order traversal of the right subtree
③Access the root node
We need to know that a binary tree cannot be uniquely determined based on pre-order traversal and post-order traversal, so it is impossible to output an in-order traversal based on pre-order traversal and post-order traversal. This is because pre-order and post-order traversal cannot determine the specific location of the root node. For example, consider two trees of different shapes but with the same preorder and postorder traversal:
A A / \ B B
The pre-order traversal of these two trees is AB, and the post-order traversal is both BA, but their in-order traversal is BA and AB respectively, so we cannot determine the in-order traversal based only on pre-order and post-order traversal.
However, if we know that the leaf nodes or all internal nodes of the tree have two children (i.e. a full binary tree), then we can reconstruct the tree using pre-order and post-order traversal. But in general, we need in-order traversal and pre-order or post-order traversal to uniquely determine a binary tree. So here we only discuss the use of in-order traversal and post-order traversal to obtain pre-order traversal, and the use of pre-order traversal and in-order traversal to obtain post-order traversal.
1. Given the in-order traversal and post-order traversal, find the pre-order traversal
example:
In-order traversal: 4, 2, 5, 1, 3
Postorder traversal: 4, 5, 2, 3, 1
The first thing to know is that in postorder traversal, the last element is always the root node. So in this example, 1 is the root node.
Then, find 1 in the in-order traversal result, which divides the in-order traversal result into two parts: the in-order traversal result 4, 2, 5 of the left subtree and the in-order traversal result 3 of the right subtree.
Next, we need to determine the post-order traversal results of the left subtree and right subtree. In post-order traversal, the elements of the left subtree are always before the elements of the right subtree. So in this example, the result of post-order traversal of the left subtree is 4, 5, 2, and the result of post-order traversal of the right subtree is 3.
Now, the same operation can be done recursively on the left and right subtrees. For the left subtree, you can see that 2 is the root node, 4 is the left child node, and 5 is the right child node. For the right subtree, 3 is a leaf node.
Therefore, the results of the pre-order traversal of this binary tree are: 1 (root node), 2 (root node of the left subtree), 4 (left child node of the left subtree), 5 (right child node of the left subtree), 3 (right child node).
This binary tree can be drawn:
Therefore, according to the rules of pre-order traversal, the order of pre-order traversal can be obtained as: 1, 2, 4, 5, 3
code show as below
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Define the binary tree node structure
typedef struct Node {
int data; // data field
struct Node *left; // left pointer field
struct Node *right; // right pointer field
} Node;
// Construct a binary tree based on post-order traversal and in-order traversal, and return the root node pointer
Node *buildTree(int *postOrder, int *inOrder, int len) {
// If the input is empty or has zero length, return a null pointer
if (postOrder == NULL || inOrder == NULL || len <= 0) {
return NULL;
}
//Create a new node and assign the last element of the post-order traversal to its data field
Node *root = (Node *)malloc(sizeof(Node));
root->data = postOrder[len - 1];
// Find the location of the root node in inorder traversal
int pos = 0;
while (inOrder[pos] != root->data) {
pos + + ;
}
// Call the function recursively, passing in the left subtree part and the right subtree part of post-order traversal and in-order traversal respectively.
root->left = buildTree(postOrder, inOrder, pos);
root->right = buildTree(postOrder + pos, inOrder + pos + 1, len - pos - 1);
//Return the root node pointer
return root;
}
// Pre-order traversal prints the binary tree
void preOrder(Node *root) {
//If the node is empty, return
if (root == NULL) {
return;
}
//Print the data field of the current node
printf("%d ", root->data);
//Traverse the left subtree in order
preOrder(root->left);
//Traverse the right subtree in order
preOrder(root->right);
}
// test code
int main() {
// Define integer arrays for post-order traversal and in-order traversal
int postOrder[] = {4, 5, 2, 3, 1};
int inOrder[] = {4, 2, 5, 1, 3};
// Construct a binary tree and get the root node pointer
Node *root = buildTree(postOrder, inOrder, sizeof(postOrder) / sizeof(int));
// Pre-order traversal prints the binary tree
printf("The result of preorder traversal is:\
");
preOrder(root);
printf("\
");
// release memory
free(root);
return 0;
}
The running results are as follows
The result of preorder traversal is:
1 2 4 5 3
2. Given pre-order traversal and in-order traversal, find post-order traversal
example:
Preorder traversal: 1, 2, 4, 5, 3
In-order traversal: 4, 2, 5, 1, 3
The first thing to know is that in preorder traversal, the first element is always the root node. So in this example, 1 is the root node.
Then, finding 1 in the inorder traversal result, it divides the inorder traversal result into two parts: the inorder traversal result 4, 2, 5 of the left subtree and the inorder traversal result 3 of the right subtree.
Next, we need to determine the pre-order traversal results of the left subtree and right subtree. In preorder traversal, the elements of the left subtree are always in front of the elements of the right subtree. So in this example, the result of preorder traversal of the left subtree is 2, 4, 5, and the result of preorder traversal of the right subtree is 3.
Now, the same operation can be done recursively on the left and right subtrees. For the left subtree, you can see that 2 is the root node, 4 is the left child node, and 5 is the right child node. For the right subtree, 3 is a leaf node.
Therefore, the result of the post-order traversal of this binary tree is: 4 (left child node of the left subtree), 5 (right child node of the left subtree), 2 (root node of the left subtree), 3 (right child node), 1 (root node).
This binary tree can be drawn:
Therefore, according to the rules of post-order traversal, the order of post-order traversal can be obtained as: 4, 5, 2, 3, 1
code show as below
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Define the binary tree node structure
typedef struct Node {
int data; // data field
struct Node *left; // left pointer field
struct Node *right; // right pointer field
} Node;
// Construct a binary tree based on pre-order traversal and in-order traversal, and return the root node pointer
Node *buildTree(int *preOrder, int *inOrder, int len) {
// If the input is empty or has zero length, return a null pointer
if (preOrder == NULL || inOrder == NULL || len <= 0) {
return NULL;
}
//Create a new node and assign the first element of the preorder traversal to its data field
Node *root = (Node *)malloc(sizeof(Node));
root->data = preOrder[0];
// Find the location of the root node in inorder traversal
int pos = 0;
while (inOrder[pos] != root->data) {
pos + + ;
}
// Call the function recursively, passing in the left subtree part and right subtree part of pre-order traversal and in-order traversal respectively.
root->left = buildTree(preOrder + 1, inOrder, pos);
root->right = buildTree(preOrder + pos + 1, inOrder + pos + 1, len - pos - 1);
//Return the root node pointer
return root;
}
// Post-order traversal prints binary tree
void postOrder(Node *root) {
//If the node is empty, return
if (root == NULL) {
return;
}
// Post-order traversal of the left subtree
postOrder(root->left);
// Post-order traversal of the right subtree
postOrder(root->right);
//Print the data field of the current node
printf("%d ", root->data);
}
// test code
int main() {
// Define integer arrays for pre-order traversal and in-order traversal
int preOrder[] = {1, 2, 4, 5, 3};
int inOrder[] = {4, 2, 5, 1, 3};
// Construct a binary tree and get the root node pointer
Node *root = buildTree(preOrder, inOrder, sizeof(preOrder) / sizeof(int));
// Post-order traversal prints binary tree
printf("The result of post-order traversal is:\
");
postOrder(root);
printf("\
");
// release memory
free(root);
return 0;
}
The running results are as follows
The result of post-order traversal is:
4 5 2 3 1
This is my understanding of the known in-order traversal and post-order traversal and the pre-order traversal and the known pre-order traversal and in-order traversal and post-order traversal. You are welcome to point out my mistakes so that I can correct them later.