#include <iostream>
using namespace std;
// basic structure of a binary tree node
class binary_tree_node
{
private:
int data;
binary_tree_node *leftChild;
binary_tree_node *rightChild;
public:
binary_tree_node(int item)
{
data = item;
leftChild = rightChild = NULL;
}
// getters
int getData();
binary_tree_node *getLeftChild();
binary_tree_node *getRightChild();
// setters
void setLeftChild(binary_tree_node *newLeftChild);
void setRightChild(binary_tree_node *newRightChild);
};
typedef binary_tree_node node;
int node::getData()
{
return data;
}
node *node::getLeftChild()
{
return leftChild;
}
node *node::getRightChild()
{
return rightChild;
}
void node::setLeftChild(node *newLeftChild)
{
leftChild = newLeftChild;
}
void node::setRightChild(node *newRightChild)
{
rightChild = newRightChild;
}
// basic functionalities of a binary tree
class binary_tree
{
private:
node *root;
node *insertRecursive(node *root, int item);
void preorderRecursive(node *root);
void inorderRecursive(node *root);
void postorderRecursive(node *root);
public:
binary_tree()
{
root = NULL;
}
void insert(int item);
bool isEmpty();
void preorder();
void inorder();
void postorder();
};
typedef binary_tree tree;
// inserts the given item into the binary tree.
void tree::insert(int item)
{
root = insertRecursive(root, item);
}
// recursive method to insert the given item into the binary tree
node *tree::insertRecursive(node *root, int item)
{
if (root == NULL)
{
return new node(item);
}
if (root->getLeftChild() == NULL)
{
root->setLeftChild(insertRecursive(root->getLeftChild(), item));
}
else if (root->getRightChild() == NULL)
{
root->setRightChild(insertRecursive(root->getRightChild(), item));
}
else
{
// insert in the right-sub-tree
insertRecursive(root->getRightChild(), item);
}
return root;
}
// utility method to check if the tree is empty
bool tree::isEmpty()
{
return root == NULL;
}
// runs a preorder traversal over the binary tree
void tree::preorder()
{
preorderRecursive(root);
}
// recursive preorder traversal over the binary tree
void tree::preorderRecursive(node *root)
{
if (root == NULL)
return;
cout << root->getData() << " ";
preorderRecursive(root->getLeftChild());
preorderRecursive(root->getRightChild());
}
// runs an inorder traversal over the binary tree
void tree::inorder()
{
inorderRecursive(root);
}
// recursive inorder traversal over the binary tree
void tree::inorderRecursive(node *root)
{
if (root == NULL)
{
return;
}
inorderRecursive(root->getLeftChild());
cout << root->getData() << " ";
inorderRecursive(root->getRightChild());
}
// runs a postorder traversal over the binary tree
void tree::postorder()
{
postorderRecursive(root);
}
// recursive postorder traversal over the binary tree
void tree::postorderRecursive(node *root)
{
if (root == NULL)
return;
postorderRecursive(root->getLeftChild());
postorderRecursive(root->getRightChild());
cout << root->getData() << " ";
}
int main(int argc, char **argv)
{
if (argc < 2)
{
cout << "Must pass the items as argument.\n";
return 1;
}
tree tree;
for (int i = 1; i < argc; i++)
{
const char *str = argv[i];
int num;
sscanf(str, "%d", &num);
tree.insert(num);
}
cout << "Preorder Traversal: ";
tree.preorder();
cout << endl;
cout << "Inorder Traversal: ";
tree.inorder();
cout << endl;
cout << "Postorder Traversal: ";
tree.postorder();
cout << endl;
return 0;
}
REROOT
#include <iostream>
#include <vector>
using namespace std;
class Node
{
public:
int data;
Node *left;
Node *right;
Node *par;
Node(int val) : data(val), left(NULL), right(NULL), par(NULL) {}
};
class BinaryTree
{
public:
// Creates a binary tree from a level order vector representation (with -1 for NULLs)
Node *createTree(const vector<int> &v, Node *par, Node *root, int i)
{
if (i >= v.size() || v[i] == -1)
return NULL;
root = new Node(v[i]);
root->par = par;
root->left = createTree(v, root, root->left, 2 * i + 1);
root->right = createTree(v, root, root->right, 2 * i + 2);
return root;
}
// Inorder traversal
void inorder(Node *root)
{
if (root == NULL)
return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
// Postorder traversal
void postorder(Node *root)
{
if (root == NULL)
return;
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
// Get reference to a node containing the given value
Node *getReferenceOf(Node *root, int val)
{
if (root == NULL)
return NULL;
if (root->data == val)
return root;
Node *leftRes = getReferenceOf(root->left, val);
if (leftRes != NULL)
return leftRes;
return getReferenceOf(root->right, val);
}
Node *getReferenceOf(int val)
{
return getReferenceOf(this->root, val);
}
Node *root;
BinaryTree() : root(NULL) {}
};
// Appends the [root]ed subtree as rightmost child of [newRoot]ed subtree
void append(Node *root, Node *newRoot)
{
Node *rightMostChild = newRoot;
while (rightMostChild->right != NULL)
rightMostChild = rightMostChild->right;
rightMostChild->right = root;
if (root)
root->par = rightMostChild;
}
// Extracts the subtree rooted at [newRoot] from tree rooted at [root]
void fix(Node *root, Node *newRoot)
{
if (root == NULL)
return;
if (root->left == newRoot)
{
root->left = NULL;
newRoot->par = NULL;
return;
}
if (root->right == newRoot)
{
root->right = NULL;
newRoot->par = NULL;
return;
}
fix(root->left, newRoot);
fix(root->right, newRoot);
}
void reRoot(Node *root, Node *newRoot)
{
if (root == newRoot)
return;
fix(root, newRoot);
append(root, newRoot);
}
int main()
{
BinaryTree tree;
vector<int> v = {5, 7, 9, 3, -1, 11, 15, -1, -1, -1, -1, 12, 14};
Node *root = tree.createTree(v, NULL, NULL, 0);
tree.root = root;
cout << "Initial Tree:-" << endl;
cout << "Inorder: ";
tree.inorder(root);
cout << '\n';
cout << "Postorder: ";
tree.postorder(root);
cout << '\n';
Node *newRoot = NULL;
int n;
while (true)
{
cout << "\nEnter the new root of the tree: ";
cin >> n;
newRoot = tree.getReferenceOf(n);
if (newRoot != NULL)
break;
cout << "Enter valid input.\n";
}
reRoot(root, newRoot);
cout << "\nAfter Re-Root operation:-" << endl;
cout << "Inorder: ";
tree.inorder(newRoot);
cout << '\n';
cout << "Postorder: ";
tree.postorder(newRoot);
cout << '\n';
return 0;
}
