[ create a new paste ] login | about

Link: http://codepad.org/Grt3NsIV    [ raw code | output | fork ]

C++, pasted on Feb 22:
#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;
}


Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
      2
   3
         5
      4
6
      7
   8
      9
sum(recursive):     44
sum(non-recursive): 44
1: not found.
4: found.
7: found.
12: not found.


Create a new paste based on this one


Comments: