Tree Traversal
Tree traversal refers to the process of visiting and exploring all nodes in a tree data structure. Traversing a tree allows us to access the data stored in each node.
There are three common methods of tree traversal:
- Inorder: Traverses the left subtree, visits the root node, and then traverses the right subtree.
- Preorder: Visits the root node, traverses the left subtree, and then traverses the right subtree.
- Postorder: Traverses the left subtree, traverses the right subtree, and then visits the root node.
Let's take a look at an example of performing an inorder traversal in C++:
TEXT/X-C++SRC
1#include <iostream>
2using namespace std;
3
4// Definition of a Binary Tree node
5struct Node {
6 int data;
7 Node* left;
8 Node* right;
9};
10
11// Function to perform an inorder traversal
12void inorderTraversal(Node* root) {
13 if (root == NULL) {
14 return;
15 }
16
17 inorderTraversal(root->left);
18 cout << root->data << " ";
19 inorderTraversal(root->right);
20}
21
22int main() {
23 // Create a binary tree
24 Node* root = new Node;
25 root->data = 1;
26 root->left = new Node;
27 root->left->data = 2;
28 root->left->left = NULL;
29 root->left->right = NULL;
30 root->right = new Node;
31 root->right->data = 3;
32 root->right->left = NULL;
33 root->right->right = NULL;
34
35 // Perform an inorder traversal
36 inorderTraversal(root);
37
38 return 0;
39}xxxxxxxxxx39
}using namespace std;// Definition of a Binary Tree nodestruct Node { int data; Node* left; Node* right;};// Function to perform an inorder traversalvoid inorderTraversal(Node* root) { if (root == NULL) { return; } inorderTraversal(root->left); cout << root->data << " "; inorderTraversal(root->right);}int main() { // Create a binary tree Node* root = new Node; root->data = 1; root->left = new Node; root->left->data = 2; root->left->left = NULL; root->left->right = NULL;OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment