language: C++ 4.7.2 (gcc-4.7.2)
date: 470 days 21 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <iostream>
#include <map>
#include <vector>
 
class Tree {
public:
    explicit Tree(int value) : _root(NULL), _left(NULL), _right(NULL), _sibling(NULL), _nodeValue(value) {}
    ~Tree() { if (_left) delete _left; if (_right) delete _right; }
    Tree* root() const { return _root; }
    Tree* left_subtree() const { return _left; }
    Tree* right_subtree() const { return _right; }
    Tree* sibling() const { return _sibling; }
    int value() const { return _nodeValue; }    
    Tree* setLeft(Tree* t) { t->_root = this; return _left = t; }
    Tree* setRight(Tree* t) { t->_root = this; return _right = t; }
    void connect(Tree* s) { _sibling = s; }
private:
    Tree* _root;
    Tree* _left;
    Tree* _right;
    Tree* _sibling;
    int _nodeValue;    
};
 
typedef std::map<int, std::vector<Tree*> > nodes_by_level;
 
void join_siblings(int level, Tree* t, nodes_by_level& nodes) {
    if (!t) return;
    nodes[level].push_back(t);
    join_siblings(level + 1, t->left_subtree(), nodes);
    join_siblings(level + 1, t->right_subtree(), nodes);
}
 
nodes_by_level join_siblings(Tree& t) {
  nodes_by_level nodes;
  join_siblings(0, &t, nodes);
  return nodes;
}
 
void printSiblings(Tree* t) {
    if (!t) return;
    if (t->sibling()) std::cout << "The sibling of " << t->value() << " is " << t->sibling()->value() << std::endl;
    printSiblings(t->left_subtree());
    printSiblings(t->right_subtree());
}
 
int main() {
    Tree t(1);
    Tree* two = t.setLeft(new Tree(2));
    Tree* three = t.setRight(new Tree(3));
    Tree* four = two->setLeft(new Tree(4));
    two->setRight(new Tree(5));
    Tree* six = three->setRight(new Tree(6));
    four->setLeft(new Tree(7));
    six->setRight(new Tree(8));
 
    nodes_by_level nl = join_siblings(t);
 
    std::cout << "Connected nodes: \n";
 
    for (nodes_by_level::iterator it = nl.begin();
         it != nl.end();
         ++it) {
        std::vector<Tree*>& v = it->second;
        for (size_t i = 0; i < v.size(); ++i) {
            if (i < v.size() - 1) v[i]->connect(v[i+1]);
        }
    }
 
    printSiblings(&t);
 
    return 0;
}