inorder: stack
preorder: dfs
postorder: stack
nonRecursivePostorder(rootNode)
nodeStack.push(rootNode)
while (! nodeStack.empty())
currNode = nodeStack.peek()
if ((currNode.left != null) and (currNode.left.visited == false))
nodeStack.push(currNode.left)
else
if ((currNode.right != null) and (currNode.right.visited == false))
nodeStack.push(currNode.right)
else
print currNode.value
currNode.visited := true
nodeStack.pop()
stl replacement of tree:
set and map
struct ltstr { bool operator()(const char* s1, const char* s2) const { return strcmp(s1, s2) < 0; } }; int main() { const int N = 6; const char* a[N] = {"isomer", "ephemeral", "prosaic", "nugatory", "artichoke", "serif"}; const char* b[N] = {"flat", "this", "artichoke", "frigate", "prosaic", "isomer"}; set<const char*, ltstr> A(a, a + N); set<const char*, ltstr> B(b, b + N); set<const char*, ltstr> C; cout << "Set A: "; copy(A.begin(), A.end(), ostream_iterator<const char*>(cout, " ")); cout << endl; cout << "Set B: "; copy(B.begin(), B.end(), ostream_iterator<const char*>(cout, " ")); cout << endl; cout << "Union: "; set_union(A.begin(), A.end(), B.begin(), B.end(), ostream_iterator<const char*>(cout, " "), ltstr()); cout << endl; cout << "Intersection: "; set_intersection(A.begin(), A.end(), B.begin(), B.end(), ostream_iterator<const char*>(cout, " "), ltstr()); cout << endl; set_difference(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()), ltstr()); cout << "Set C (difference of A and B): "; copy(C.begin(), C.end(), ostream_iterator<const char*>(cout, " ")); cout << endl; }
ets are based on the abstract data structure of a binary search tree
ReplyDelete