Skriv ut boktitlar i alfabetisk ordning

I videon lärde du dig tre sätt att implementera djupet-först-sökning (depth first search) i binära träd: in-order, pre-order och post-order.

I följande binära sökträd har du lagrat titlarna på några böcker.

Graphical representation of a binary search tree.

Trädet är förladdat i variabeln bst (rad 15):

bst = CreateTree()

Kan du tillämpa in-order-traversering så att boktitlarna visas i alfabetisk ordning?

Den här övningen är en del av kursen

Datastrukturer och algoritmer i Python

Visa kurs

Övningsinstruktioner

Kontrollera om current_node finns.
Anropa funktionen in_order() rekursivt på rätt halva av trädet.
Skriv ut värdet för current_node.
Anropa funktionen in_order() rekursivt på den andra halvan av trädet.

Interaktiv övning med praktiskt arbete

Testa den här övningen genom att slutföra den här exempelkoden.

class BinarySearchTree:
  def __init__(self):
    self.root = None

  def in_order(self, current_node):
    # Check if current_node exists
    if ____:
      # Call recursively with the appropriate half of the tree
      self.in_order(current_node.____)
      # Print the value of the current_node
      print(____)
      # Call recursively with the appropriate half of the tree
      self.in_order(current_node.____)
  
bst = CreateTree()
bst.in_order(bst.root)

Redigera och kör kod