This C++ program demonstrates how to perform a **Preorder Traversal** of a binary tree using recursion. Below is a detailed explanation of the code:
Class Definition: `node`
{
public:
int data;
node *left;
node *right;
node(int x)
{
data = x;
left = right = NULL;
}
};
```
- **Purpose**: Defines the structure of a node in the binary tree.
- **Members**:
- `data`: Stores the value of the node.
- `left`: Pointer to the left child of the node.
- `right`: Pointer to the right child of the node.
- **Constructor**:
- `node(int x)`: Initializes the node with the value `x` and sets both `left` and `right` pointers to `NULL`.
---
#### **2. Function: `create()`**
```cpp
node *create()
{
node *root;
int x;
cout << "\nEnter data: ";
cin >> x;
if (x == -1)
return NULL;
root = new node(x);
cout << "\nEnter left of " << x;
root->left = create();
cout << "\nEnter right of " << x;
root->right = create();
return root;
}
```
- **Purpose**: Recursively creates a binary tree.
- **Steps**:
1. Prompts the user to enter data for the current node.
2. If the user enters `-1`, it returns `NULL`, indicating no node should be created (base case for recursion).
3. Otherwise, it creates a new node with the entered data.
4. Recursively calls `create()` to construct the left subtree.
5. Recursively calls `create()` to construct the right subtree.
6. Returns the root of the constructed tree.
---
#### **3. Function: `pre()`**
```cpp
void pre(node *root)
{
if (root != NULL)
{
cout << "\t" << root->data; // Print the current node's data
pre(root->left); // Traverse the left subtree
pre(root->right); // Traverse the right subtree
}
}
```
- **Purpose**: Performs a **Preorder Traversal** of the binary tree.
- **Preorder Traversal Order**:
1. Visit the root node.
2. Traverse the left subtree.
3. Traverse the right subtree.
- **Steps**:
1. Checks if the current node (`root`) is not `NULL`.
2. Prints the data of the current node.
3. Recursively calls `pre()` for the left child.
4. Recursively calls `pre()` for the right child.
4. `main()` Function**
int main()
{
node *root = create(); // Create the binary tree
pre(root); // Perform preorder traversal
return 0;
}
Purpose: Drives the program.
Steps
1. Calls the `create()` function to construct the binary tree and stores the root of the tree in `root`.
2. Calls the `pre()` function to perform a preorder traversal of the tree starting from the root.
3. Returns `0` to indicate successful execution.
How the Program Works
1. The program starts by calling the `create()` function in `main()`.
2. The user is prompted to enter data for each node. If `-1` is entered, it signifies the absence of a node.
3. The binary tree is constructed recursively based on user input.
4. Once the tree is constructed, the `pre()` function is called to perform a preorder traversal.
5. The traversal visits nodes in the order: **Root → Left Subtree → Right Subtree**, and prints the data of each node.
Example Input and Output
Input
Enter data: 1
Enter left of 1
Enter data: 2
Enter left of 2
Enter data: -1
Enter right of 2
Enter data: -1
Enter right of 1
Enter data: 3
Enter left of 3
Enter data: -1
Enter right of 3
Enter data: -1
Tree Structure
1
/ \
2 3
Output
1 2 3
Key Points
- The program uses **recursion** extensively for both tree creation and traversal.
- The `create()` function builds the tree dynamically based on user input.
- The `pre()` function implements the preorder traversal algorithm.
- The program assumes `-1` as a sentinel value to indicate the absence of a node.