#include <stdio.h>
#include <stdlib.h>
#include <stack>
struct TreeNode {
int data;
TreeNode *left, *right;
};
typedef TreeNode* Tree;
class InorderTraversal {
public:
InorderTraversal(TreeNode *t):t_(t), cursor_(t) {}
/**
* Returns NULL at the end of the traversal
*
**/
TreeNode* next() {
while (cursor_) {
s_.push(cursor_);
cursor_ = cursor_->left;
}
if (!s_.empty()) {
TreeNode* ret = s_.top();
s_.pop();
cursor_ = ret->right;
return ret;
}
return NULL;
}
void reset() {
cursor_ = t_;
s_ = std::stack<TreeNode*>();
}
private:
Tree t_;
TreeNode* cursor_;
std::stack<TreeNode*> s_;
};
Tree insert(Tree t, int el) {
if (t == NULL) {
t = (TreeNode *)calloc(sizeof(TreeNode), 1);
t->data = el;
} else {
if(el <= t->data) {
if(t->left) {
insert(t->left, el);
} else {
t->left = (TreeNode *)calloc(sizeof(TreeNode), 1);
t->left->data = el;
}
} else {
if(t->right) {
insert(t->right, el);
} else {
t->right = (TreeNode *)calloc(sizeof(TreeNode), 1);
t->right->data = el;
}
}
}
return t;
}
int main() {
int i;
Tree t1 = NULL;
Tree t2 = NULL;
for (i = 10; i >= 6; i--) {
t1 = insert(t1, i);
}
for (i = 12; i >= 6; i--) {
t2 = insert(t2, i);
}
InorderTraversal s1(t1);
InorderTraversal s2(t2);
TreeNode *n1 = s1.next(), *n2 = s2.next();
while (n1 && n2) {
if (n1->data < n2->data) {
printf("%d ", n1->data);
n1 = s1.next();
} else {
printf("%d ", n2->data);
n2 = s2.next();
}
}
while (n1) {
printf("%d ", n1->data);
n1 = s1.next();
}
while (n2) {
printf("%d ", n2->data);
n2 = s2.next();
}
printf("\n");
}
Neat code using power of C++. I recapped STL implementation of next function after this code. Thanks.
Wouldn't the following be even more simpler? Only the insert function,Tree insert(Tree &t, int el) { if (t == NULL) { t = (TreeNode *)calloc(sizeof(TreeNode), 1); t->data = el; } else { if(el <= t->data) { insert(t->left, el); } else { insert(t->right, el); } } return t;}