In the journey of learning data structures, binary tree traversal is an extremely critical knowledge point, serving as a key to unlock the mysteries of tree data structures. Whether in the field of algorithm design, database optimization scenarios, or the operation of complex file systems, binary tree traversal plays a crucial role. Therefore, to assist learners in better mastering the knowledge related to binary tree traversal in C++, this article will provide a detailed analysis of the preorder, inorder, postorder, and level-order traversals. It will not only explore the usage of both recursive and non-recursive implementations but also present a wealth of application examples and exam question samples, hoping to help everyone thoroughly understand and skillfully apply this important knowledge.
1.Basic Concepts of Binary Tree Traversal
(1)Definition and Characteristics of Binary Trees
A binary tree is a tree data structure in which each node can have at most two children, referred to as the left child and the right child. The nodes of a binary tree consist of a data field and pointers to the left and right children, where the data field is used to store the node’s data, and the left and right child pointers point to the left and right subtrees of that node, respectively.
Binary trees have several common characteristics. The number of nodes is closely related to the height of the tree. A binary tree with height h can have at most 2^(h+1) – 1 nodes. A full binary tree is a special type of binary tree where every level is fully populated, meaning a full binary tree of height h has 2^(h+1) – 1 nodes. A complete binary tree is characterized by having all levels fully populated except possibly for the last level, which is filled from left to right. A balanced binary tree is a special type of binary search tree where the absolute difference in height between the left and right subtrees does not exceed 1, and both subtrees are also balanced binary trees. These characteristics are significant in practical applications, helping to improve algorithm efficiency and data processing capabilities.
(2)The Concept and Significance of Traversal
Binary tree traversal refers to the process of visiting each node in the tree according to a specific search path, with each node being visited only once. This process aims to systematically access all nodes of the binary tree to process node data or retrieve relevant information about the tree.
Traversal is of great significance in binary tree operations. In algorithm design, traversal can be used to find specific nodes, calculate the depth of the tree, count the number of nodes, etc. Through traversal, various operations can be efficiently performed on the binary tree, achieving complex algorithm functionalities. In database optimization, binary tree traversal helps optimize query operations. For example, in database index structures, using binary tree traversal can quickly locate the required data, reducing query time and improving database performance. Additionally, in managing file system directory structures and evaluating expression trees, binary tree traversal plays an indispensable role, providing strong support for solving practical problems.
2.C++ Implementation of Binary Tree Traversal
(1)Preorder Traversal
1.Recursive Implementation
The code example for the recursive version of preorder traversal is as follows:
void preorder(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << ” “;
preorder(root->left);
preorder(root->right);
}
The logic of this code is as follows: first, check if the root node is null; if it is, return immediately without performing any operations. If the root node is not null, visit the root node, output its value, then recursively perform preorder traversal on the left subtree, and finally recursively perform preorder traversal on the right subtree.
For a simple binary tree example, let the root node be A, the left child be B, and the right child be C. Node B has a left child D and a right child E. The recursive call process is as follows: first visit the root node A, output A; then recursively visit A‘s left subtree, which is node B, output B; then recursively visit B‘s left subtree, which is node D, output D; since D has no left or right children, return from the recursion, then visit B‘s right subtree, which is node E, output E; after visiting both left and right subtrees of B, return to A, then visit A‘s right subtree, which is node C, output C. The final result of the preorder traversal is A B D E C.
2.Non-Recursive Implementation
The code example for the non-recursive version of preorder traversal is as follows:
vector preorderTraversal(TreeNode* root) {
if (root == nullptr) return {};
TreeNode* cur = root;
vector v;
stack<TreeNode*> st;
while (cur || !st.empty()) {
while (cur) {
v.push_back(cur->val);
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();
st.pop();
cur = top->right;
}
return v;
}
The idea of using a stack to implement preorder traversal is as follows: first, push the root node onto the stack, then repeatedly process the nodes in the stack. In each iteration, pop the top node from the stack, visit that node (i.e., output its value or save its value), and then push the right child and left child of that node onto the stack (pushing the right child first ensures that the left subtree is processed first when popping from the stack). When both the stack is empty and the current node is null, the traversal ends.
The specific execution flow is as follows: assuming the binary tree is the same as the previous example. First, push the root node A onto the stack, visit A and save its value, then push A‘s right child C and left child B onto the stack; then pop the top node B, visit B and save its value, push B‘s right child E and left child D onto the stack; pop the top node D, visit D and save its value; since D has no children, continue popping; pop the top node E, visit E and save its value; E has no children, continue popping; pop the top node C, visit C and save its value; C has no children, at this point the stack is empty, and the traversal ends. The final result of the preorder traversal is consistent with the recursive version, which is A B D E C.
(2)Inorder Traversal
1.Recursive Implementation
The code example for the recursive version of inorder traversal is as follows:
void inorder(TreeNode* root) {
if (root == nullptr) return;
inorder(root->left);
cout << root->val << ” “;
inorder(root->right);
}
The algorithm logic is as follows: first recursively visit the left subtree, then visit the root node, and finally recursively visit the right subtree.
Using the same binary tree as an example, the order of node visits during recursion is as follows: first recursively visit A‘s left subtree, which is node B; then recursively visit B‘s left subtree, which is node D; since D has no left child, output D; then return to B, output B; then recursively visit B‘s right subtree, which is node E, output E; after visiting both left and right subtrees of B, return to A, output A; finally recursively visit A‘s right subtree, which is node C, output C. The final result of the inorder traversal is D B E A C.
2.Non-Recursive Implementation
The code example for the non-recursive version of inorder traversal is as follows:
vector inorderTraversal(TreeNode* root) {
if (root == nullptr) return {};
TreeNode* cur = root;
vector v;
stack<TreeNode*> st;
while (cur || !st.empty()) {
while (cur) {
st.push(cur);
cur = cur->left;
}
TreeNode* top = st.top();
st.pop();
v.push_back(top->val);
cur = top->right;
}
return v;
}
The method of using a stack to implement inorder traversal is as follows: start from the root node, continuously move down the left subtree, pushing each node onto the stack until the leftmost node is found. Then, pop a node from the stack, visit that node, and set its right subtree as the current node, repeating the above process until both the stack is empty and the current node is null.
Using the same binary tree as an example, the execution process is as follows: first push the root node A onto the stack, then push A‘s left child B onto the stack, and then push B‘s left child D onto the stack; since D has no left child, pop D and save its value; then pop B and save its value, push B‘s right child E onto the stack, pop E and save its value; then pop A and save its value, push A‘s right child C onto the stack, pop C and save its value. The final result of the inorder traversal is D B E A C.
(3)Postorder Traversal
1.Recursive Implementation
The code example for the recursive version of postorder traversal is as follows:
void postorder(TreeNode* root) {
if (root == nullptr) return;
postorder(root->left);
postorder(root->right);
cout << root->val << ” “;
}
The algorithm logic is as follows: first recursively visit the left subtree, then recursively visit the right subtree, and finally visit the root node.
Using the same binary tree as an example, the order of recursive calls is as follows: first recursively visit A‘s left subtree, which is node B; then recursively visit B‘s left subtree, which is node D; since D has no left child, return; then recursively visit B‘s right subtree, which is node E, return; output B; then return to A, recursively visit A‘s right subtree, which is node C; since C has no left or right children, output C; finally output A. The final result of the postorder traversal is D E B C A.
2.Non-Recursive Implementation
The code example for the non-recursive version of postorder traversal is as follows:
vector postorderTraversal(TreeNode* root) {
if (root == nullptr) return {};
stack<TreeNode*> st1, st2;
st1.push(root);
while (!st1.empty()) {
TreeNode* top = st1.top();
st1.pop();
st2.push(top);
if (top->left) st1.push(top->left);
if (top->right) st1.push(top->right);
}
vector v;
while (!st2.empty()) {
v.push_back(st2.top()->val);
st2.pop();
}
return v;
}
This algorithm uses two stacks to implement postorder traversal. First, push the root node onto st1, then loop through st1, popping nodes and pushing them onto st2, and pushing the left and right children (if they exist) onto st1. When st1 is empty, it indicates that all nodes have been processed, and at this point, pop nodes from st2 in order, which gives the postorder traversal order.
Using the same binary tree as an example, the execution process is as follows: first push the root node A onto st1, then push A‘s right child C and left child B onto st1; then pop B, push B‘s right child E and left child D onto st1; pop D, since D has no children, continue popping; pop E, since E has no children, continue popping; pop C, since C has no children, continue popping; at this point st1 is empty, and popping from st2 gives the final postorder traversal result of D E B C A.
(4)Level Order Traversal
1.Implementation Method
The code implementation for level order traversal is as follows:
vector<vector> levelOrder(TreeNode* root) {
vector<vector> result;
if (root == nullptr) return result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
vector level;
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(level);
}
return result;
}
The principle of using a queue to implement level order traversal is to enqueue and dequeue nodes in order of their levels. First, enqueue the root node, then in a loop, each time dequeue a node from the queue, visit that node and save its value to the current level’s array, then enqueue the left and right children of that node (if they exist). When the queue is not empty, repeat the above process until the queue is empty, at which point the result is the level order traversal result.
Using the same binary tree as an example, the execution process is as follows: first enqueue the root node A, then dequeue A, save A‘s value to the current level array, and enqueue A‘s left child B and right child C; then dequeue B, save B‘s value to the current level array, and enqueue B‘s left child D and right child E; dequeue C, save C‘s value to the current level array; dequeue D, save D‘s value to the current level array; dequeue E, save E‘s value to the current level array. The final result of the level order traversal is [[A], [B, C], [D, E]].
3.Usage and Application Examples of Binary Tree Traversal
(1)Usage Examples
The following code demonstrates how to use the above traversal functions to perform binary tree traversal operations. First, create a binary tree using a simple manual creation method:
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
Next, call the traversal functions and output the results. Using preorder traversal as an example:
“`cpp
vector<int> preorderResult = preorderTraversal(root);
for (int val : preorderResult) {
cout << val << ” “;
}
cout << endl;
Inorder Traversal:
vector<int> inorderResult = inorderTraversal(root);
for (int val : inorderResult) {
cout << val << ” “;
}
cout << endl;
Postorder Traversal:
vector<int> postorderResult = postorderTraversal(root);
for (int val : postorderResult) {
cout << val << ” “;
}
cout << endl;
Level Order Traversal:
vector<vector<int>> levelOrderResult = levelOrder(root);
for (const auto& level : levelOrderResult) {
for (int val : level) {
cout << val << ” “;
}
cout << endl;
}
Through the above code, the complete process of creating a binary tree, calling traversal functions, and outputting traversal results is accomplished, allowing for a clear view of the results of different traversal methods.
(2)Examples of Application Scenarios
In traversing the directory structure of a file system, binary tree traversal plays an important role. The file system can be abstracted as a binary tree, with directories as nodes and subdirectories and files as child nodes. Using preorder traversal, one can first visit the root directory, then recursively visit the left subdirectory (if it exists) and the right subdirectory (if it exists), allowing for a specific order of access to directories and files at various levels, facilitating file searches, counting files, and other operations. For example, to find a specific file, starting from the root directory and using preorder traversal to delve into subdirectories allows for a systematic and comprehensive search of the entire file system.
Evaluating expression trees is also a common application scenario for binary tree traversal. The nodes of an expression tree can be operands or operators, with leaf nodes being operands and non-leaf nodes being operators. By performing postorder traversal on the expression tree, calculations can be carried out in the order of “first operands, then operators.” First, recursively calculate the values of the left and right subtrees, and finally compute the operation corresponding to the root node operator, thus effectively solving the computation of complex mathematical expressions.
4.Examples of Exam Questions on Binary Tree Traversal
(1)Analysis of Common Question Types
In exams on binary tree traversal, reconstructing a binary tree based on given traversal sequences is a common question type. For example, given the preorder traversal sequence [1, 2, 4, 5, 3, 6, 7] and the inorder traversal sequence [4, 2, 5, 1, 6, 3, 7], reconstruct the binary tree. The solution approach is to utilize the property that the first element of the preorder traversal is the root node, determining that the root node is 1. Then, find the root node 1 in the inorder traversal, where the left side [4, 2, 5] is the inorder sequence of the left subtree, and the right side [6, 3, 7] is the inorder sequence of the right subtree. Based on the length of the left subtree’s inorder sequence, the corresponding preorder sequences can be derived from the preorder traversal: the left subtree’s preorder sequence is [2, 4, 5], and the right subtree’s preorder sequence is [3, 6, 7]. Then recursively reconstruct the left and right subtrees.
TreeNode* buildTree(vector& preorder, vector& inorder) {
if (preorder.empty() || inorder.empty()) return nullptr;
int rootVal = preorder[0];
TreeNode* root = new TreeNode(rootVal);
int inorderRootIndex = 0;
for (int i = 0; i < inorder.size(); ++i) {
if (inorder[i] == rootVal) {
inorderRootIndex = i;
break;
}
}
vector leftPreorder(preorder.begin() + 1, preorder.begin() + inorderRootIndex + 1);
vector leftInorder(inorder.begin(), inorder.begin() + inorderRootIndex);
vector rightPreorder(preorder.begin() + inorderRootIndex + 1, preorder.end());
vector rightInorder(inorder.begin() + inorderRootIndex + 1, inorder.end());
root->left = buildTree(leftPreorder, leftInorder);
root->right = buildTree(rightPreorder, rightInorder);
return root;
}
Determining whether the traversal sequences of two binary trees are the same is also a common exam question type. The solution approach is to perform the same type of traversal (e.g., preorder traversal) on both trees, storing the results in arrays, and then comparing the two arrays for equality.
bool areTraversalsEqual(TreeNode* root1, TreeNode* root2) {
vector traversal1, traversal2;
//Assuming a preorder traversal function existspreorderTraversal
traversal1 = preorderTraversal(root1);
traversal2 = preorderTraversal(root2);
return traversal1 == traversal2;
}
###Summary of Problem-Solving Techniques
To solve exam questions related to binary tree traversal, it is essential to understand the characteristics of traversal sequences to analyze the structure of the binary tree. The first element of the preorder traversal is the root node, and the last element of the postorder traversal is the root node. Utilizing these properties in conjunction with inorder traversal can help determine the sequences of the left and right subtrees, thereby reconstructing the binary tree.
Both recursive and non-recursive methods have their applicable scenarios. Recursive code is concise but may encounter stack overflow issues; non-recursive methods use stacks or queues to simulate the recursive process, making them more intuitive and suitable for handling complex situations.
In preparation for exams, it is crucial to be proficient in the recursive and non-recursive implementation codes for various traversals, practice different types of questions, and understand the problem-solving approaches for different question types. During exams, carefully read the questions, clarify the requirements, and pay attention to edge cases, such as handling empty trees.
Knowledge of binary tree traversal is widely applied in practical programming and algorithm design. I hope this learning share can help everyone gain a deeper understanding of binary tree traversal, achieve good results in learning and exams, and apply knowledge to practical projects to enhance programming skills.
Feel free to share, since you are here, please follow before you go.
COCO in Beijing 2025.11
【Disclaimer】Videos and images are sourced from the internet, Weibo, WeChat public accounts, and other public channels, and sharing is for learning and communication purposes only. Copyright belongs to the original authors and institutions. If your rights are infringed, please contact us promptly, and we will delete the content.