How to build a binary tree based on morse code for a random set of letters?-CodePudding

I need to build a binary tree based on a random set of letters... That is, for example for the following combination of letters:

A .
C -
R .-
T ..
! -.

Must produce the following tree

       *
     /   \
    A     C
   / \   /
  T   R !

That is, for each node of the tree the letter on the left must be inserted to represent the point "." and right to represent a dash "−"

I wrote the following code but it's incomplete... I don't actually know how to implement the recursion

class BinaryTree:
  def __init__(self, key):
    self.dado = key
    self.esq = None
    self.dir = None

def parse_tree(root, letter):
  if alphabet[letter] == '.':
    root.esq = BinaryTree(letter)
  elif alphabet[letter] == '-':
    root.dir = BinaryTree(letter)


N = int(input())
alphabet = {}

tree = BinaryTree('*')
for n in range(N):
  letter, morse_code = input().split()
  alphabet[letter] = morse_code
  parse_tree(tree, letter)

For the following data sample

5
A .
C -
R .-
T ..
! -.

CodePudding user response：

In your recursion, you continue to call the function until the path string (the set of .s and _s) is exhausted for a given node:

class BinaryTree:
   def __init__(self, key = None):
      self.head = key
      self.left = None
      self.right = None

def add_node(tree, node, path):
   if not path:
      tree.head = node
   else:
      if getattr(tree, (p:='left' if path[0] == '.' else 'right')) is None:
          setattr(tree, p, BinaryTree())
      add_node(getattr(tree, p), node, path[1:])

s = """
A .
C -
R .-
T ..
! -.
"""
t = BinaryTree('*') #root node of tree
for i in filter(None, s.split('\n')):
   add_node(t, *i.split())