1. Creating Binary Trees from Input: Sequential and Linked Storage
a. Problem Analysis:
This task requires creating a binary tree from an input character sequence, implementing two storage methods: sequential storage and linked storage. The character ‘@’ in the input sequence represents an empty node.
b. Algorithm Design:
Sequential Storage Method:
- Initialize an array to represent the sequentially stored binary tree.
- Traverse the input character sequence and store characters in the array sequentially.
- Use array indices to represent node positions: for a parent node at index
i, its left child is at2*i + 1and right child at2*i + 2. - Skip ‘@’ characters (empty nodes), storing only actual data.
Linked Storage Method:
- Create a
TreeNodestruct to represent binary tree nodes, containing data, left subtree pointer, and right subtree pointer. - Use a queue data structure to assist in building the tree. Initialize with a root node and enqueue it.
- Traverse the input sequence, dequeuing nodes to create left and right children, then enqueue them.
c. Data Structure Design:
Sequential Storage:
struct TreeNoderepresents binary tree nodes.- Array stores nodes sequentially.
Linked Storage:
struct TreeNoderepresents nodes with data and subtree pointers.- Queue assists in tree construction.
d. Debugging Process:
- Run the program with sample input to build the tree.
- Ensure correct input sequence with ‘@’ for empty nodes.
- Use ‘#’ to mark input completion in linked storage.
- Verify correct sequential and linked storage implementations.
e. Output Results:
- Output includes sequentially stored node data and traversal results for linked storage.
2. Depth-First Traversal Implementation
a. Problem Analysis:
Implement depth-first traversals: pre-order, in-order, and post-order for sequentially stored trees.
b. Algorithm Design:
Pre-order:
- Visit root, then recursively traverse left and right subtrees.
In-order:
- Recursively traverse left subtree, visit root, then right subtree.
Post-order:
- Recursively traverse left and right subtrees, then visit root.
c. Data Structure Design:
- Recursive algorithms.
3. Breadth-First Traversal Implementation
a. Problem Analysis:
Implement level-order traversal for linked storage trees.
b. Algorithm Design:
- Use a queue, starting from root, enqueuing nodes level by level while visiting them.
c. Data Structure Design:
- Queue data structure.
Sample Cases
Inputs: abc@@@d@ef@ and abc@@@d@ef@#
Debugging Process:
- Sequential Storage:
- Input characters: ‘a’, ‘b’, ‘c’, ‘@’, ‘@’, ‘@’, ’d’, ‘@’, ’e’, ‘f’.
- Sequential array:
['a', 'b', 'c', '@', '@', '@', 'd', '@', 'e', 'f'].
- Linked Storage:
- Create root ‘a’, enqueue.
- ‘b’ becomes left child of ‘a’, enqueue.
- ‘c’ becomes right child of ‘a’, enqueue.
- ‘@’ indicates empty left child.
- ‘@’ indicates empty right child.
- ’d’ becomes left child of ‘b’, enqueue.
- ‘@’ indicates empty right child.
- ’e’ becomes left child of ‘c’, enqueue.
- ‘f’ becomes right child of ‘c’, enqueue.
Output Results:
- Sequential Storage:
- Pre-order:
a b d c e f - In-order:
d b a e c f - Post-order:
d b e f c a
- Pre-order:
- Linked Storage:
- Pre-order:
a b d c e f - In-order:
b d a e c f - Post-order:
d b e f c a - Level-order:
a b c d e f
- Pre-order:
Source Code
Sequential Storage
#include<bits/stdc++.h>
using namespace std;
#define MAX_NODES 1000 // Maximum node count
// Binary tree node structure
struct TreeNode {
char data;
};
// Create new tree node
TreeNode* createNode(char data) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->data = data;
return newNode;
}
// Sequential storage tree structure
struct SequentialTree {
TreeNode* nodes[MAX_NODES];
int size; // Node count
};
// Initialize sequential tree
void initSequentialTree(SequentialTree* tree) {
tree->size = 0;
for (int i = 0; i < MAX_NODES; i++) {
tree->nodes[i] = nullptr;
}
}
// Insert node into sequential tree
void insertNode(SequentialTree* tree, char data) {
if (tree->size < MAX_NODES) {
TreeNode* newNode = createNode(data);
tree->nodes[tree->size] = newNode;
tree->size++;
} else {
printf("Tree is full, cannot insert\n");
}
}
// Get root node
TreeNode* getRoot(SequentialTree* tree) {
return tree->nodes[0];
}
// Get left child
TreeNode* getLeftChild(SequentialTree* tree, int parentIndex) {
int leftChildIndex = 2 * parentIndex + 1;
if (leftChildIndex < tree->size) {//Check existence
return tree->nodes[leftChildIndex];
}
return nullptr;
}
// Get right child
TreeNode* getRightChild(SequentialTree* tree, int parentIndex) {
int rightChildIndex = 2 * parentIndex + 2;
if (rightChildIndex < tree->size) {
return tree->nodes[rightChildIndex];
}
return nullptr;
}
// Pre-order traversal
void preorderTraversal(struct SequentialTree* tree, int index) {
if (index >= tree->size || tree->nodes[index]->data == '@') {
return;
}
printf("%c ", tree->nodes[index]->data); // Visit root
preorderTraversal(tree, 2 * index + 1); // Traverse left
preorderTraversal(tree, 2 * index + 2); // Traverse right
}
// In-order traversal
void inorderTraversal(struct SequentialTree* tree, int index) {
if (index >= tree->size || tree->nodes[index]->data == '@') {
return;
}
inorderTraversal(tree, 2 * index + 1); // Traverse left
printf("%c ", tree->nodes[index]->data); // Visit root
inorderTraversal(tree, 2 * index + 2); // Traverse right
}
// Post-order traversal
void postorderTraversal(struct SequentialTree* tree, int index) {
if (index >= tree->size || tree->nodes[index]->data == '@') {
return;
}
postorderTraversal(tree, 2 * index + 1); // Traverse left
postorderTraversal(tree, 2 * index + 2); // Traverse right
printf("%c ", tree->nodes[index]->data); // Visit root
}
int main() {
SequentialTree* tree=(SequentialTree*)malloc(sizeof(SequentialTree));
initSequentialTree(tree);
char data='a';
while (1){
cin>>data;
if(data=='#'){
break;
}
insertNode(tree,data);
}
cout<<"Pre-order traversal:"<<endl;
preorderTraversal(tree,0);
cout<<endl;
cout<<"In-order traversal:"<<endl;
inorderTraversal(tree,0);
cout<<endl;
cout<<"Post-order traversal:"<<endl;
postorderTraversal(tree,0);
cout<<endl;
cout<<"Level-order traversal:"<<endl;
for(int i=0;i<tree->size;i++){
if(tree->nodes[i]->data!='@')
cout<<tree->nodes[i]->data<<' ';
}
cout<<endl;
return 0;
}
Linked Storage
#include<bits/stdc++.h>
using namespace std;
// Binary tree node structure
struct TreeNode {
char data;
TreeNode* left;
TreeNode* right;
TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};
// Create linked binary tree
TreeNode* createBinaryTree(const string& input) {
if (input.empty()) {
return nullptr;
}
queue<TreeNode*> nodeQueue;
TreeNode* root = new TreeNode(input[0]);
nodeQueue.push(root);
for (int i = 1; i < input.length(); i += 2) {
TreeNode* current = nodeQueue.front();
nodeQueue.pop();
if (input[i] != '@') {
current->left = new TreeNode(input[i]);
nodeQueue.push(current->left);
}
if (i + 1 < input.length() && input[i + 1] != '@') {
current->right = new TreeNode(input[i + 1]);
nodeQueue.push(current->right);
}
}
return root;
}
// Pre-order traversal
void preorderTraversal(TreeNode* root) {
if (root) {
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
// In-order traversal
void inorderTraversal(TreeNode* root) {
if (root) {
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}
}
// Post-order traversal
void postorderTraversal(TreeNode* root) {
if (root) {
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->data << " ";
}
}
// Level-order traversal
void breadthFirstTraversal(TreeNode* root) {
if (!root) {
return;
}
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
while (!nodeQueue.empty()) {
TreeNode* current = nodeQueue.front();
nodeQueue.pop();
cout << current->data << " ";
if (current->left) {
nodeQueue.push(current->left);
}
if (current->right) {
nodeQueue.push(current->right);
}
}
}
int main() {
string input;
cin>>input;
TreeNode* root = createBinaryTree(input);
cout << "Pre-order traversal: ";
preorderTraversal(root);
cout << endl;
cout << "In-order traversal: ";
inorderTraversal(root);
cout << endl;
cout << "Post-order traversal: ";
postorderTraversal(root);
cout << endl;
cout << "Level-order traversal: ";
breadthFirstTraversal(root);
cout << endl;
return 0;
}
When will I have a drink and discuss the details again?