#include <stdio.h> #include <stack> struct TreeNode { TreeNode *left, *right; int el; explicit TreeNode(int _el) : left(NULL), right(NULL), el(_el) {} }; typedef TreeNode* Tree; struct StackNode { TreeNode *node; bool visited; explicit StackNode(TreeNode *t) : node(t), visited(false) {} ~StackNode() { delete node; } private: StackNode(const StackNode &); StackNode operator=(const StackNode &); }; void printAncestor(Tree t, int key) { std::stack<StackNode *> stack; if (!t || t->el == key) return; stack.push(new StackNode(t)); TreeNode *tmp = t->left; while (!stack.empty()) { if (tmp) { if (tmp->el == key) { //Key found print the ancestors while (!stack.empty()) { StackNode *s = stack.top(); printf("%d ", s->node->el); stack.pop(); } } else { stack.push(new StackNode(tmp)); tmp = tmp->left; } } else { //Traverse the right subtree, if not traversed StackNode *s = stack.top(); if (!s->visited) { s->visited = true; tmp = s->node->right; } else { stack.pop(); } } } } Tree newTree() { TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->left = new TreeNode(6); root->right->right = new TreeNode(7); root->left->left->left = new TreeNode(8); root->left->right->right = new TreeNode(9); root->right->right->left = new TreeNode(10); return root; } int main(int argc, char const *argv[]) { Tree t = newTree(); for (int i = 1; i <= 11; ++i) { printf("%d: ", i); printAncestor(t, i); printf("\n"); } return 0; }
Advertisements