CMPT 125 Lecture Notes - Lecture 16: Binary Tree, The Algorithm

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 125
• Professor: Igor Shinkar

Document Summary

Write an algorithm that gets a queue and reverses it. Idea: use stack. void reverse(queue_t* q) { stack_t* s = create_stack(); while ( !queue_empty(q) ) { stack_push( s, dequeue(q) ); while ( !stack_empty(s)) { enqueue( q, stack_pop(s) ); stack_free(s); Write an algorithm that gets a binary tree and outputs all vertices in the 5th layer in time o(1). // recall: print the tree in bfs order. Bfs_traversal(btnode root): q = create_queue(, enqueue(q, root, while (!queue_empty(q)) Claim: the algorithm prints the tree level by level: Idea: create separator between layers, and add them to the queue in the end of each layer. Bfs_traversal(btnode root): q = create_queue(, separator = create_node() // special node that will separate the layers, enqueue(q, root), enqueue(q, separator) // end of level 0, while (!queue_empty(q)) 5. 2 if (current == separator) // end of layer. When separator leaves the queue: we removed all elements in level k the queue contains all elements in level k+1.