Skip to content

Instantly share code, notes, and snippets.

@dslaw
Created May 29, 2016 21:17
Show Gist options
  • Save dslaw/af783710e687558b76cd618409acc834 to your computer and use it in GitHub Desktop.
Save dslaw/af783710e687558b76cd618409acc834 to your computer and use it in GitHub Desktop.
Invert binary tree
#include "btree.h"
template <typename T>
void Btree<T>::insert(const T &x) {
if (root == nullptr) {
node_ptr node = std::make_unique<Node>(x);
root = std::move(node);
return;
}
insert_node(x, root);
}
template <typename T>
void Btree<T>::insert_node(const T &x, node_ptr &p) {
if (p == nullptr) {
node_ptr node = std::make_unique<Node>(x);
p = std::move(node);
return;
}
// No duplicate entries
if (x < p->value) {
insert_node(x, p->left);
} else if (x > p->value ) {
insert_node(x, p->right);
}
}
template <typename T>
void Btree<T>::invert() {
if (root == nullptr) {
return;
}
invert_node(root);
}
template <typename T>
void Btree<T>::invert_node(node_ptr &p) {
if (p == nullptr) {
return;
}
node_ptr holding = std::move(p->left);
p->left = std::move(p->right);
p->right = std::move(holding);
invert_node(p->left);
invert_node(p->right);
}
template <typename T>
std::vector<T> Btree<T>::traverse(bool inorder) const {
typename std::vector<T> xs;
if (root == nullptr) {
return xs;
}
inorder ? traverse_inorder(root, xs) : traverse_preorder(root, xs);
return xs;
}
template <typename T>
void Btree<T>::traverse_inorder(const node_ptr &p, std::vector<T> &x) const {
if (p == nullptr) {
return;
}
traverse_inorder(p->left, x);
x.push_back(p->value);
traverse_inorder(p->right, x);
}
template <typename T>
void Btree<T>::traverse_preorder(const node_ptr &p, std::vector<T> &x) const {
if (p == nullptr) {
return;
}
x.push_back(p->value);
traverse_preorder(p->left, x);
traverse_preorder(p->right, x);
}
// Compile a couple data types
template class Btree<int>;
template class Btree<float>;
#ifndef __B_TREE_H
#define __B_TREE_H
#include <memory>
#include <vector>
template <typename T>
class Btree {
public:
Btree() {};
void insert(const T &x);
void invert();
std::vector<T> traverse(bool inorder) const;
private:
struct Node {
std::unique_ptr<Node> left, right;
T value;
Node(const T &x) : value(x) {}
};
typedef std::unique_ptr<Node> node_ptr;
node_ptr root;
void insert_node(const T &x, node_ptr &p);
void invert_node(node_ptr &p);
void traverse_inorder(const node_ptr &p, std::vector<T> &x) const;
void traverse_preorder(const node_ptr &p, std::vector<T> &x) const;
};
#endif
#include "btree.h"
#include <iostream>
#include <vector>
int main () {
std::vector<int> xs = {10, 2, 15, 1, 5, 11, 20};
Btree<int> tree;
for (auto &x: xs) {
tree.insert(x);
}
tree.invert();
// Inorder traversal
auto v = tree.traverse(true);
for (auto &x: v) {
std::cout << x << std::endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment