#include <iostream>
#include <vector>
class Node{
private:
int data;
Node *left, *right;
public:
Node(int d, Node *l = 0, Node *r = 0) {data = d; left = l; right = r; }
void vomit(int rank) {
if (this == 0) return;
this->left->vomit(rank + 3);
for (int i = 0; i < rank; i++)
std::cout << ' ';
std::cout << this->data << std::endl;
this->right->vomit(rank + 3);
}
int Saiki() {
if (this == 0)
return 0;
return this->data + this->left->Saiki() + this->right->Saiki();
}
enum _dir { LEFT, RIGHT };
int NSaiki() {
std::vector<Node *> stack;
std::vector<_dir> direction;
_dir dir;
int sum = 0;
Node *p = this;
label_start:
sum += p->data;
if (p->left != 0) {
stack.push_back(p);
direction.push_back(LEFT);
p = p->left;
goto label_start;
}
label_right:
if (p->right != 0) {
stack.push_back(p);
direction.push_back(RIGHT);
p = p->right;
goto label_start;
}
label_back:
if (stack.empty())
return sum;
p = stack.back();
stack.pop_back();
dir = direction.back();
direction.pop_back();
if (dir == LEFT)
goto label_right;
else
goto label_back;
}
bool isFound(int n) {
if (this == 0)
return false;
if (this->data == n)
return true;
if (this->data > n)
return this->left->isFound(n);
else
return this->right->isFound(n);
}
};
int main() {
Node n1 = Node(5);
Node n2 = Node(2);
Node n3 = Node(4, &n1);
Node n4 = Node(7);
Node n5 = Node(9);
Node n6 = Node(3, &n2, &n3);
Node n7 = Node(8, &n4, &n5);
Node r = Node(6, &n6, &n7);
r.vomit(0);
std::cout << "sum(recursive): " << r.Saiki() << std::endl;
std::cout << "sum(non-recursive): " << r.NSaiki() << std::endl;
std::cout << 1 << ": " << ((r.isFound(1)) ? "found." : "not found." ) << std::endl;
std::cout << 4 << ": " << ((r.isFound(4)) ? "found." : "not found." ) << std::endl;
std::cout << 7 << ": " << ((r.isFound(7)) ? "found." : "not found." ) << std::endl;
std::cout << 12<< ": " << ((r.isFound(12))? "found." : "not found." ) << std::endl;
return 0;
}