Skip to content

Instantly share code, notes, and snippets.

@eopXD
Last active Sep 21, 2020
Embed
What would you like to do?
Morris Traversal / Deletion
// see https://eopxd.com/2020/08/30/morris-traversal/ for explaination
#include <iostream>
#include <cassert>
#include <vector>
#include <memory>
using namespace std;
template<class T>
struct Tree {
struct Node {
T data;
Node *left, *right;
Node ( const T &value ) : data(value), left(nullptr), right(nullptr) {
cout << "create node with value: " << value << "\n";
}
~Node () {
cout << "delete node with value: " << data << "\n";
}
};
Node *root;
size_t size;
Tree () : root(nullptr), size(0) {}
void in_order () { // morris traversal
Node *now = root, *tmp = nullptr;
while ( now ) {
if ( !now->left ) {
cout << now->data << ", ";
now = now->right;
} else {
tmp = now->left;
while ( tmp->right and tmp->right != now ) {
tmp = tmp->right;
}
if ( !tmp->right ) {
tmp->right = now;
now = now->left;
} else {
tmp->right = nullptr;
cout << now->data << ", ";
now = now->right;
}
}
}
cout << "\n";
}
~Tree () { // morris traversal deletion
Node *now = root, *tmp = nullptr;
while ( now ) {
if ( !now->left ) {
tmp = now;
now = now->right;
delete tmp;
} else {
tmp = now->left;
while ( tmp->right and tmp->right != now ) {
tmp = tmp->right;
}
if ( !tmp->right ) { // left-subtree visit
tmp->right = now;
tmp = now;
now = now->left;
tmp->left = nullptr;
} else { // no repeating left visit
assert(0);
}
}
}
}
void insert ( T val ) {
++size;
if ( !root ) {
root = new Node(val);
return;
}
Node *now = root;
while ( 1 ) {
if ( val < now->data ) {
if ( !now->left ) {
//cout << "insert left\n";
now->left = new Node(val);
break;
} else {
now = now->left;
}
} else {
if ( !now->right ) {
//cout << "insert right\n";
now->right = new Node(val);
break;
} else {
now = now->right;
}
}
}
}
};
int main ()
{
Tree<int> t;
vector<int> seq = {6, 2, 7, 1, 3, 9, 5, 8, 4};
for ( auto x : seq )
t.insert(x);
t.in_order();
return (0);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment