palitsin
BAN USER#include <deque>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
struct Node {
int val;
vector<Node*> children;
Node(int v) : val(v) {}
};
void traverseTreeRecursive(const Node *n) {
for (auto node : n->children) {
traverseTreeRecursive(node);
}
cout << n->val << " ";
}
void traverseTreeIterative(Node *n) {
map<Node*, bool> nodeExpanded;
vector<Node*> stack;
stack.push_back(n);
while (stack.size() > 0) {
if(nodeExpanded[stack.back()]) {
cout << stack.back()->val << " ";
stack.pop_back();
} else {
nodeExpanded[stack.back()] = true;
for (auto &ch : stack.back()->children) {
stack.push_back(ch);
}
}
}
}
int main() {
Node n1(1); Node n2(2); Node n3(3); Node n4(4); Node n5(5); Node n6(6); Node n7(7);
n1.children.push_back(&n2); n1.children.push_back(&n3); n1.children.push_back(&n4);
n4.children.push_back(&n5); n4.children.push_back(&n6);
n6.children.push_back(&n7);
//1-------|-------|
//2 3 4-------|
// 5 6
// 7
traverseTreeRecursive(&n1);
cout << endl;
traverseTreeIterative(&n1);
cout << endl;
return 0;
}
#include <deque>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
struct Node {
int val;
vector<Node*> children;
Node(int v) : val(v) {}
};
void traverseTreeRecursive(const Node *n) {
for (auto node : n->children) {
traverseTreeRecursive(node);
}
cout << n->val << " ";
}
void traverseTreeIterative(Node *n) {
map<Node*, bool> nodeExpanded;
vector<Node*> stack;
stack.push_back(n);
while (stack.size() > 0) {
if(nodeExpanded[stack.back()]) {
cout << stack.back()->val << " ";
stack.pop_back();
} else {
nodeExpanded[stack.back()] = true;
for (auto &ch : stack.back()->children) {
stack.push_back(ch);
}
}
}
}
int main() {
Node n1(1); Node n2(2); Node n3(3); Node n4(4); Node n5(5); Node n6(6); Node n7(7);
n1.children.push_back(&n2); n1.children.push_back(&n3); n1.children.push_back(&n4);
n4.children.push_back(&n5); n4.children.push_back(&n6);
n6.children.push_back(&n7);
//1-------|-------|
//2 3 4-------|
// 5 6
// 7
traverseTreeRecursive(&n1);
cout << endl;
traverseTreeIterative(&n1);
cout << endl;
return 0;
}
First version double inserted.
This version 5 lines.
#include <list>
#include <iostream>
using namespace std;
//template <typename T, typename L, typename V>
void insert(std::list<int>::iterator begin, std::list<int>::iterator end, list<int> &list, const int &value)
{
std::list<int>::iterator next = begin; next++;
if (begin == end) list.insert(begin, value);
else {
if (*begin < value) insert(next, end, list, value);
else list.insert(begin, value);
}
}
int main() {
list<int> l;
for (auto i : {1,3,5,7,9})
insert(l.begin(), l.end(), l, i);
//l.push_back(i);
for (const auto &it : l)
std::cout << ' ' << it;
std::cout << '\n';
insert(l.begin(), l.end(), l, 4);
insert(l.begin(), l.end(), l, 3);
insert(l.begin(), l.end(), l, 5);
for (const auto &it : l)
std::cout << ' ' << it;
std::cout << '\n';
return 0;
}
4 lines
#include <list>
#include <iostream>
using namespace std;
//template <typename T, typename L, typename V>
void insert(std::list<int>::iterator begin, std::list<int>::iterator end, list<int> &list, const int &value)
{
std::list<int>::iterator next = begin; next++;
if (begin == end) list.insert(begin, value);
if (*begin < value) insert(next, end, list, value);
else list.insert(begin, value);
}
int main() {
list<int> l;
for (auto i : {1,3,5,7,9})
l.push_back(i);
for (const auto &it : l)
std::cout << ' ' << it;
std::cout << '\n';
insert(l.begin(), l.end(), l, 4);
insert(l.begin(), l.end(), l, 3);
insert(l.begin(), l.end(), l, 5);
for (const auto &it : l)
std::cout << ' ' << it;
std::cout << '\n';
return 0;
}
Both variants recursive and iterative for testing.
- palitsin September 23, 2015For every node keep a boolean value signing that we have pushed its children to stack already.