Как создать функцию для преобразования двоичного дерева в кортеж?

#python #recursion #data-structures #binary-tree

Вопрос:

я столкнулся с этим вопросом, когда мне было поручено преобразовать кортеж в двоичное дерево, а затем преобразовать двоичное дерево обратно в кортеж и вернуть как дерево, так и кортеж. мне удалось преобразовать кортеж в дерево, но мне не удалось создать функцию для обратного. я всего лишь начинающий, пытающийся изучить структуры данных.

функция parse_tuple здесь используется для анализа кортежа для создания двоичного дерева, которое отлично работает.

пожалуйста, помогите мне исправить мою функцию tree_to_tuple. любые идеи или советы по исправлению логики были бы великолепны.

Спасибо

 #used for creating binary tree class TreeNode:    def __init__(self, key):  self.key = key  self.left = None  self.right = None

 #used to parse over the tuple to create a bianry tree def parse_tuple(data):    if isinstance(data, tuple) and len(data) == 3:    node = TreeNode(data[1])  node.left = parse_tuple(data[0])  node.right = parse_tuple(data[2])    elif data is None:  node = None    else:  node = TreeNode(data)    return node

 #doesnt work def tree_to_tuple(node):  if isinstance(node, TreeNode) and node.left is not None and node.right is not None:  node_mid = node.key  node_left = tree_to_tuple(node.left)  node_right = tree_to_tuple(node.right)    elif node.left is None:  node_left = None    else:  node_right = None    return (node_left, node_mid, node_right)

 tree_tuple = ((1, 3, None), 2, ((None, 3, 4), 5, (6, 7, 8)))  tree2 = parse_tuple(tree_tuple)  tree_tuple2 = (1, 2, 3) tree = parse_tuple(tree_tuple2) print(tree_to_tuple(tree2))

и это ошибка, которую я получаю, если пытаюсь использовать tree_to_tuple

Файл «main.py», строка 45, в возврате tree_to_tuple (node_left, node_mid, node_right) UnboundLocalError: локальная переменная ‘node_left’, на которую ссылаются перед назначением.

1. Ну, вы всегда возвращаетесь (node_left, node_mid, node_right) , но если вы прошли через ветви elif или else ветви, то они не будут определены. В elif ветке вы только определяете node_left и забываете о node_mid и node_right, а в else ветке вы определяете только node_right и забываете о node_mid и node_left.

Ответ №1:

Вы были близки, но ваши тесты немного запутаны.

Вот патч:

 def tree_to_tuple(node):  if isinstance(node, TreeNode):   # special case if the tree has no left and no right sub-tree  if node.left is None and node.right is None:  return node.key   return (  tree_to_tuple(node.left),  node.key,  tree_to_tuple(node.right)  )  raise ValueError('this is not a tree')  tree_tuple = ((1, 3, None), 2, ((None, 3, 4), 5, (6, 7, 8)))  tree2 = parse_tuple(tree_tuple)  tree_tuple2 = (1, 2, 3) tree = parse_tuple(tree_tuple2) print(tree_to_tuple(tree2))

Выход:

 ((1, 3, None), 2, ((None, 3, 4), 5, (6, 7, 8)))

Ответ №2:

Вот фрагмент кода, который я написал, который работает для меня.

 def tree_to_tuple(node):  if isinstance(node, TreeNode):   if node.left is not None and node.right is not None:  node_mid = node.key  node_left = tree_to_tuple(node.left)  node_right = tree_to_tuple(node.right)   return (node_left, node_mid, node_right)   elif node.left is None and node.right is None:  return node.key   elif node.left is None and node.right is not None:  node_mid = node.key  node_right = tree_to_tuple(node.right)  node_left = None   return (node_left, node_mid, node_right)   elif node.left is not None and node.right is None:  node_mid = node.key  node_right = None  node_left = tree_to_tuple(node.left)   return (node_left, node_mid, node_right)   else:  print("It's not a tree")