Recursive Traversal Methods (Depth-First and Breadth-First)
Pre-order Traversal (Recursive)
This method visits the root node first, then recursively traverses the left subtree, followed by the right subtree.
void preorderRecursive(BiTree node) {
if (node != nullptr) {
visit(node); // Visit the root
preorderRecursive(node->lChild); // Traverse left subtree
preorderRecursive(node->rChild); // Traverse right subtree
}
}In-order Traversal (Recursive)
This method recursively traverses the left subtree, visits the root node, and then recursively traverses the right subtree.
void inorderRecursive(BiTree node) {
if (node != nullptr) {
inorderRecursive(node->lChild); // Traverse left subtree
visit(node); // Visit the root
inorderRecursive(node->rChild); // Traverse right subtree
}
}Post-order Traversal (Recursive)
This method recursively traverses the left subtree, then the right subtree, and finally visits the root node.
void postorderRecursive(BiTree node) {
if (node != nullptr) {
postorderRecursive(node->lChild); // Traverse left subtree
postorderRecursive(node->rChild); // Traverse right subtree
visit(node); // Visit the root
}
}Level-order Traversal (Recursive Approach)
This approach involves calculating the height of the tree and then performing a modified traversal for each level.
void printLevel(BiTree node, int level) {
if (node == nullptr || level < 1) {
return;
}
if (level == 1) {
visit(node);
}
printLevel(node->lChild, level - 1);
printLevel(node->rChild, level - 1);
}
int treeHeight(BiTree node) {
int leftHeight = 0;
int rightHeight = 0;
if (node == nullptr) {
return 0;
} else {
leftHeight = treeHeight(node->lChild);
rightHeight = treeHeight(node->rChild);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
}
void levelOrderRecursive(BiTree root) {
if (root == nullptr) {
return;
}
int height = treeHeight(root);
for (int i = 1; i <= height; ++i) {
printLevel(root, i);
}
}Iterative Traversal Methods
Pre-order Traversal (Iterative with One Stack)
This method uses a single stack to simulate the recursion. It pushes the current node onto the stack, visits it, and then proceeds to its left child. If the left child is null, it pops from the stack and moves to the right child.
void preorderIterative(BiTree root) {
if (root == nullptr) return;
std::stack<BiTree> nodeStack;
nodeStack.push(root);
while (!nodeStack.empty()) {
BiTree currentNode = nodeStack.top();
nodeStack.pop();
visit(currentNode);
if (currentNode->rChild != nullptr) {
nodeStack.push(currentNode->rChild);
}
if (currentNode->lChild != nullptr) {
nodeStack.push(currentNode->lChild);
}
}
}In-order Traversal (Iterative with One Stack)
This iterative approach pushes nodes onto the stack while traversing left as much as possible. When it can't go left anymore, it pops a node, visits it, and then tries to go right.
void inorderIterative(BiTree root) {
std::stack<BiTree> nodeStack;
BiTree currentNode = root;
while (currentNode != nullptr || !nodeStack.empty()) {
while (currentNode != nullptr) {
nodeStack.push(currentNode);
currentNode = currentNode->lChild;
}
currentNode = nodeStack.top();
nodeStack.pop();
visit(currentNode);
currentNode = currentNode->rChild;
}
}Post-order Traversal (Iterative with Two Stacks)
This method uses two stacks. The first stack is used to push nodes in a root-right-left order. The second stack then pops these nodes to achieve the left-right-root order for post-order traversal.
void postorderIterativeTwoStacks(BiTree root) {
if (root == nullptr) return;
std::stack<BiTree> stack1, stack2;
stack1.push(root);
while (!stack1.empty()) {
BiTree node = stack1.top();
stack1.pop();
stack2.push(node);
if (node->lChild != nullptr) {
stack1.push(node->lChild);
}
if (node->rChild != nullptr) {
stack1.push(node->rChild);
}
}
while (!stack2.empty()) {
visit(stack2.top());
stack2.pop();
}
}Post-order Traversal (Iterative with One Stack)
A more complex one-stack approach for post-order traversal. It keeps track of the previously visited node to determine when to visit the current node.
void postorderIterativeOneStack(BiTree root) {
std::stack<BiTree> nodeStack;
BiTree lastVisited = nullptr;
BiTree current = root;
while (current != nullptr || !nodeStack.empty()) {
if (current != nullptr) {
nodeStack.push(current);
current = current->lChild;
} else {
BiTree peekNode = nodeStack.top();
if (peekNode->rChild != nullptr && lastVisited != peekNode->rChild) {
current = peekNode->rChild;
} else {
visit(peekNode);
lastVisited = peekNode;
nodeStack.pop();
}
}
}
}Level-order Traversal (Iterative with Queue)
This is the standard iterative approach for level-order traversal, utilizing a queue to process nodes level by level.
void levelOrderIterative(BiTree root) {
if (root == nullptr) return;
std::queue<BiTree> nodeQueue;
nodeQueue.push(root);
while (!nodeQueue.empty()) {
BiTree currentNode = nodeQueue.front();
nodeQueue.pop();
visit(currentNode);
if (currentNode->lChild != nullptr) {
nodeQueue.push(currentNode->lChild);
}
if (currentNode->rChild != nullptr) {
nodeQueue.push(currentNode->rChild);
}
}
}Source Code and Test Implementation
The following C++ code provides the necessary data structures and functions for creating and traversing binary trees, along with a test case to demonstrate the different traversal methods.
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cstdlib>
#include <ctime>
// Define the data type for tree nodes
typedef double elementType;
// Structure for a binary tree node
struct BiTNode {
elementType data;
struct BiTNode *lChild, *rChild;
};
typedef struct BiTNode* BiTree;
// Global variables for stacks and queues used in iterative traversals
std::stack<BiTree> traversalStack;
std::stack<BiTree> postorderStackTemp;
std::queue<BiTree> levelOrderQueue;
// Function to initialize a new tree node
BiTree createNode(elementType value) {
BiTree newNode = new BiTNode();
newNode->data = value;
newNode->lChild = newNode->rChild = nullptr;
return newNode;
}
// Function to insert a left child
BiTree insertLeftChild(BiTree parent, elementType value) {
if (parent != nullptr) {
parent->lChild = createNode(value);
return parent->lChild;
}
return nullptr;
}
// Function to insert a right child
BiTree insertRightChild(BiTree parent, elementType value) {
if (parent != nullptr) {
parent->rChild = createNode(value);
return parent->rChild;
}
return nullptr;
}
// Function to visit a node (e.g., print its data)
void visit(BiTree node) {
if (node != nullptr) {
std::cout << node->data << "\t";
} else {
std::cout << "null\t";
}
}
// --- Recursive Traversal Functions ---
void preorderRecursive(BiTree node) {
if (node != nullptr) {
visit(node);
preorderRecursive(node->lChild);
preorderRecursive(node->rChild);
}
}
void inorderRecursive(BiTree node) {
if (node != nullptr) {
inorderRecursive(node->lChild);
visit(node);
inorderRecursive(node->rChild);
}
}
void postorderRecursive(BiTree node) {
if (node != nullptr) {
postorderRecursive(node->lChild);
postorderRecursive(node->rChild);
visit(node);
}
}
void printLevel(BiTree node, int level) {
if (node == nullptr || level < 1) {
return;
}
if (level == 1) {
visit(node);
}
printLevel(node->lChild, level - 1);
printLevel(node->rChild, level - 1);
}
int treeHeight(BiTree node) {
if (node == nullptr) {
return 0;
}
int leftHeight = treeHeight(node->lChild);
int rightHeight = treeHeight(node->rChild);
return std::max(leftHeight, rightHeight) + 1;
}
void levelOrderRecursive(BiTree root) {
if (root == nullptr) {
return;
}
int height = treeHeight(root);
for (int i = 1; i <= height; ++i) {
printLevel(root, i);
}
}
// --- Iterative Traversal Functions ---
bool clearStack(std::stack<BiTree>* s) {
if (s != nullptr) {
while (!s->empty()) {
s->pop();
}
return true;
}
return false;
}
bool clearQueue(std::queue<BiTree>* q) {
if (q != nullptr) {
while (!q->empty()) {
q->pop();
}
return true;
}
return false;
}
void preorderIterative(BiTree root) {
if (root == nullptr) return;
clearStack(&traversalStack);
traversalStack.push(root);
while (!traversalStack.empty()) {
BiTree current = traversalStack.top();
traversalStack.pop();
visit(current);
if (current->rChild != nullptr) {
traversalStack.push(current->rChild);
}
if (current->lChild != nullptr) {
traversalStack.push(current->lChild);
}
}
}
void inorderIterative(BiTree root) {
clearStack(&traversalStack);
BiTree current = root;
while (current != nullptr || !traversalStack.empty()) {
while (current != nullptr) {
traversalStack.push(current);
current = current->lChild;
}
current = traversalStack.top();
traversalStack.pop();
visit(current);
current = current->rChild;
}
}
void postorderIterativeTwoStacks(BiTree root) {
if (root == nullptr) return;
clearStack(&traversalStack);
clearStack(&postorderStackTemp);
traversalStack.push(root);
while (!traversalStack.empty()) {
BiTree node = traversalStack.top();
traversalStack.pop();
postorderStackTemp.push(node);
if (node->lChild != nullptr) {
traversalStack.push(node->lChild);
}
if (node->rChild != nullptr) {
traversalStack.push(node->rChild);
}
}
while (!postorderStackTemp.empty()) {
visit(postorderStackTemp.top());
postorderStackTemp.pop();
}
}
void postorderIterativeOneStack(BiTree root) {
clearStack(&traversalStack);
BiTree lastVisited = nullptr;
BiTree current = root;
while (current != nullptr || !traversalStack.empty()) {
if (current != nullptr) {
traversalStack.push(current);
current = current->lChild;
} else {
BiTree peekNode = traversalStack.top();
if (peekNode->rChild != nullptr && lastVisited != peekNode->rChild) {
current = peekNode->rChild;
} else {
visit(peekNode);
lastVisited = peekNode;
traversalStack.pop();
}
}
}
}
void levelOrderIterative(BiTree root) {
clearQueue(&levelOrderQueue);
if (root != nullptr) {
levelOrderQueue.push(root);
}
while (!levelOrderQueue.empty()) {
BiTree current = levelOrderQueue.front();
levelOrderQueue.pop();
if (current->lChild != nullptr) {
levelOrderQueue.push(current->lChild);
}
if (current->rChild != nullptr) {
levelOrderQueue.push(current->rChild);
}
visit(current);
}
}
// --- Test Function ---
void runTests() {
BiTree root = createNode(5779 * 5607 % 100); // Example root value
// Build a sample tree
BiTree temp = root;
srand(time(nullptr));
temp = insertLeftChild(temp, rand() % 100);
insertRightChild(temp, rand() % 100);
temp = root;
insertRightChild(temp, rand() % 100);
temp = temp->rChild;
insertLeftChild(temp, rand() % 100);
// Add more nodes to create a more complex tree structure if needed
// Example:
// temp = root->lChild; // Go to left child of root
// insertLeftChild(temp, rand() % 100);
// insertRightChild(temp, rand() % 100);
std::cout << "Pre-order Recursive: ";
preorderRecursive(root);
std::cout << std::endl;
std::cout << "In-order Recursive: ";
inorderRecursive(root);
std::cout << std::endl;
std::cout << "Post-order Recursive: ";
postorderRecursive(root);
std::cout << std::endl;
std::cout << "Level-order Recursive: ";
levelOrderRecursive(root);
std::cout << std::endl;
std::cout << "Pre-order Iterative: ";
preorderIterative(root);
std::cout << std::endl;
std::cout << "In-order Iterative: ";
inorderIterative(root);
std::cout << std::endl;
std::cout << "Post-order Iterative (2 Stacks): ";
postorderIterativeTwoStacks(root);
std::cout << std::endl;
std::cout << "Post-order Iterative (1 Stack): ";
postorderIterativeOneStack(root);
std::cout << std::endl;
std::cout << "Level-order Iterative: ";
levelOrderIterative(root);
std::cout << std::endl;
}
int main() {
runTests();
return 0;
}