Tree

binaryTree.cpp

#include <iostream>

template <typename Object>
class LinkedBinaryTree {
protected:
  struct Node {
    Object element;
    Node* parent;
    Node* left;
    Node* right;

    Node() : element(Object()), parent(NULL), left(NULL), right(NULL) {}

    Node* sibling() const {
      return this == parent->left ? parent->right : parent->left;
    }
  };

private:
  Node* ROOT;
  int sz;

public:
  LinkedBinaryTree() : ROOT(NULL), size(0) {}

  Node* root() {
    return ROOT;
  }

  Node* leftChild(Node* v) const {
    return v->left;
  }

  Node* rightChild(Node* v) const {
    return v->right;
  }

  bool isExternal(Node* v) const {
    return (v->left == NULL && v->right == NULL);
  }

  bool isInternal(Node* v) const {
    return !isExternal(v);
  }

  bool isRoot(Node* v) const {
    return (v == ROOT);
  }

  void setRoot(Node* r) {
    ROOT = r;
    if (r != NULL) {
      r->parent = NULL;
    }
  }

  void replaceElement(Node* n, the Object& o) {
    n->element = o;
  }

  void swapElements(Node* n, Node* w) {
    Object tmp = n->element;
    n->element = w->element;
    w->element = tmp;
  }

  void expandExternal(Node* n, Object l, Object r) {
    n->left  = new Node; n->left->parent  = n; n->left->element = l;
    n->right = new Node; n->right->parent = n; n->right->element = r;
    sz += 2;
  }

  Node* removeAboveExternal(Node* n) {
    Node* p = n->parent;
    Node* s = n->sibling();
    if (isRoot(p)) {
      setRoot(s);
    } else {
      Node* g = p->parent; // grandparent
      if (p == g->left) g->left = s;
      else g->right = s;
      s->parent = g;
    }
    delete n;
    delete p;
    sz -= 2;
    return s;
  }
  
  LinkedBinaryTree(Object elem) {
    ROOT = new Node;
    sz = 1;
    ROOT->element = elem;
  }

  int size() const {
    return sz;
  }
  
  bool isEmpty() const {
    return (sz == 0);
  }
  
  void preorder(Node* v) {
    cout << v->element << " ";
    if (isInternal(v) {
      preorder(leftChild(v));
      preorder(rightChild(v));
    }
  }
  
  void postorder(Node* v) {
    if (isInternal(v)) {
      postorder(leftChild(v));
      postorder(rightChild(v));
    }
    cout << v->element << " ";
  }
  
  void inorder(Node* v) {
    if (isInternal(v)) 
      inorder(leftChild(v));
    
    cout << v->element << " ";
    
    if (isInternal(v)) 
      inorder(rightChild(v));
  }
  
  void eulerTour(Node* v) {
    cout << v->element << " ";
    
    if (isInternal(v)) 
      eulerTour(leftChild(v));
      
    cout << v->element << " ";
    
    if (isInternal(v))
      eulerTour(rightChild(v));
      
    cout << v->element << " ";
  }
};