binTree.h

#include <iostream>
#include <vector>
using namespace std;

#ifndef BIN_TREE_H
#define BIN_TREE_H
#endif

class Node {
    public:
    int index;
    int key;
    Node *p;
    Node *left;
    Node *right;
    Node();
    Node(int i, int k, Node *parent, Node *leftChild, Node *rightChild);
};

Node::Node() {
    index = key = 0;
    p = left = right = NULL;
}

Node::Node(int i, int k, Node *parent, Node *leftChild, Node *rightChild) {
    index = i;
    key = k;
    p = parent;
    left = leftChild;
    right = rightChild;
}

class RootedTree {
    private:
    vector<Node> T;
    int n;
    void print(Node *N);

    public:
    RootedTree();
    RootedTree(int key);
    bool insert(int index, int key);
    void print();
};

RootedTree::RootedTree() {
    n = 0;
}

RootedTree::RootedTree(int key) {
    Node N(T.size(), key, NULL, NULL, NULL);
    T.push_back(N);
    n = 1;
}

bool RootedTree::insert(int index, int key) {
    if (index > n-1) return false;
    if (T[index].left == NULL) {
        Node N(n, key, &T[index], NULL, NULL);
        T.push_back(N);
        n++;
        T[index].left = &T[n-1];
        return true;
    } else if (T[index].right == NULL) {
        Node N(n, key, &T[index], NULL, NULL);
        T.push_back(N);
        n++;
        T[index].right = &T[n-1];
        return true;
    }
    return false;
}

void RootedTree::print() {
    print(&T[0]);
    cout << endl;
}

void RootedTree::print(Node *N) {
    cout << N->key << " ";
    if (N->left != NULL) print(N->left);
    if (N->right != NULL) print(N->right);
}