如何基于一组随机字母的摩尔斯电码构建二叉树？

Question

我需要根据一组随机字母构建二叉树...也就是说，例如以下字母组合：

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

必须生成以下树

       *
     /   \
    A     C
   / \   /
  T   R !

也就是说，对于树的每个节点，必须插入左边的字母来表示点“.”。和右边代表破折号“-”

我写了下面的代码，但它不完整...我实际上不知道如何实现递归

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)

对于以下数据样本

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

但是需要注意的是，如果我们有一个没有字母的节点，我们应该包括*，如下例所示

A .-.
E ..
I ...
T -.
M --.
N -..

然后它应该生成以下树：

Answer 1

在你的递归中，你继续调用函数直到路径字符串（.s 和 _s 的集合）对于给定节点用完：

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('*')) #default character for empty node
      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())

如何基于一组随机字母的摩尔斯电码构建二叉树？

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

python

recursion

binary-tree