Python辅导树的遍历 CSCA48 Tree Traversal辅导Python

Tree Traversal

Draw the Binary Search Tree (BST) we would get if we were to insert the letters C O M P U T E R S in the order listed (i.e., C is the first letter added to the tree).

Wait… didn’t we do this last week??? Yes… but now we’re working in the opposite direction.

Now consider the following function:

1
2
3
4
5
6
7
8
9
10

def traverse(container, root):
  result = ""
  container.put(root)
  while(not container.is_empty()):
    next_node = container.get()
    if(next_node is not None):
      result += next_node.data
      container.put(next_node.left)
      container.put(next_node.right)
    return result

Containers

What is the result of calling print(traverse(my container, my root)) when my root is the root node of the tree you made, and my container is:

1. A stack
2. A queue
3. An alternating queue
4. A neck queue
5. A steue

If you are unsure how any of the containers above work, you can ask a TA during practicals, or ask on
Piazza. Make sure you understand the ADT before you start working.
You can trace the code by hand, but we recommend actually implementing each container and running it, then you can just copy/paste the output.

What to hand in

You must submit a file called ex4.txt with what would be printed for each of the containers listed above, in order, one container per line. For example, your file might look something like (once again, the format is correct, the answers are not):

COMPUTERS
SRETUPMOC
COMPSRETU
RETUSPCUP
PROCTORUS