Блог

Новичок в python и пытается определить, как рекурсивно обрезать дерево решений, создав новое дерево. Если у узла есть ключ в списке «keys_to_prune», он и его потомки не включаются в новое дерево. Вот что я придумал:

 def prune_tree(tree, keys_to_prune)  new_tree = Tree()  for child in tree.children:  if child.key not in keys_to_prune:  new_tree.children.append(child)  else:  prune_tree(child, keys_to_prune)  return new_tree  

Объект tree (Дерево()) имеет атрибуты .key, .value и .children. Этот код, похоже, не работает-похоже, он проверяет пустые узлы без ключа и значения. Любая помощь была бы полезна!

Диктант-это своего рода дерево. Рассмотрим этот пример:

 {  "a": {  "a": 1,  "b": 2,  {  "c": 3,  "d": 4,  }  },  "b": {  "a": {  "a": 1,  "b": 2,  },  "z": 99,  }, }  

Если keys_to_prune только содержит a , желаемое обрезанное дерево будет выглядеть следующим образом:

 {  "b": {  "z": 99,  }, }  

Другими словами, если вы видите ключ, который следует обрезать, ничего не делайте: не добавляйте его в новое дерево и не исследуйте его поддеревья. В противном случае добавьте ребенка к новому дереву и изучите его для более глубокой обрезки.

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

 def prune_tree(tree, keys_to_prune)  new_tree = Tree()  for child in tree.children:  if child.key not in keys_to_prune:  new_child = prune_tree(child, keys_to_prune)  new_tree.children.append(new_child)  return new_tree  

Вы можете легко отфильтровать материал, используя понимание списка:

 class Tree:  def __init__(self, k, v, children=None):  self.key = k  self.value = v  if children:  self.children = children  else:  self.children = []  def __repr__(self):  return str((self.key, self.value, self.children))  def pruned(t, keys):  return Tree(t.key, t.value, [pruned(c, keys) for c in t.children if c.key not in keys])  import random  def random_tree(max_depth=5, max_children=3):  nb_children = random.randrange(max_children 1) if max_depth gt; 0 else 0  return Tree(random.randrange(100), random.choice('abcdefghijklmnopqrstuvwxyz'), [random_tree(max_depth-1, max_children) for _ in range(nb_children)])  t = random_tree() s = pruned(t, set(range(0, 100, 2))) # keep only odd keys  print(t) # (9, 'd', [(93, 'n', [(17, 'j', [(23, 'h', [(65, 'o', [(80, 'u', []), (89, 'b', [])]), (97, 'e', [(64, 'l', []), (81, 'q', []), (51, 'o', [])])]), (63, 'y', [(65, 'c', [(27, 'h', []), (25, 'z', []), (30, 'k', [])]), (78, 'r', [])]), (65, 'z', [(15, 's', [(39, 'm', []), (69, 'a', [])])])])]), (63, 'a', [(67, 'r', [(18, 'j', [(97, 'i', [(88, 'n', [])]), (6, 'a', [(72, 'l', []), (81, 'n', [])])])]), (52, 'q', [(92, 'z', [(27, 'm', [(88, 'm', []), (39, 't', [])]), (28, 'u', [(40, 'c', [])])]), (1, 'z', [])]), (99, 'r', [(49, 'x', []), (46, 'h', [(38, 'm', [(72, 'v', [])]), (98, 'h', [(75, 'z', []), (67, 'q', [])]), (78, 'w', [(67, 'v', []), (78, 'p', [])])]), (5, 'a', [(1, 'y', []), (73, 'g', [(87, 'o', []), (63, 'i', [])]), (67, 'z', [])])])])])  print(s) # (9, 'd', [(93, 'n', [(17, 'j', [(23, 'h', [(65, 'o', [(89, 'b', [])]), (97, 'e', [(81, 'q', []), (51, 'o', [])])]), (63, 'y', [(65, 'c', [(27, 'h', []), (25, 'z', [])])]), (65, 'z', [(15, 's', [(39, 'm', []), (69, 'a', [])])])])]), (63, 'a', [(67, 'r', []), (99, 'r', [(49, 'x', []), (5, 'a', [(1, 'y', []), (73, 'g', [(87, 'o', []), (63, 'i', [])]), (67, 'z', [])])])])])  

Должен сказать, что я немного озадачен использованием key и value в ваших деревьях. Возможно, мы могли Tree бы полностью удалить класс и использовать a dict напрямую?

 def pruned(t, keys):  return {k:pruned(v, keys) for k,v in t.items() if k not in keys}  import random  def random_tree(max_depth=5, max_children=3):  nb_children = random.randrange(max_children 1) if max_depth gt; 0 else 0  return {random.randrange(100): random_tree(max_depth-1, max_children) for _ in range(nb_children)}  t = random_tree() s = pruned(t, set(range(0,100,2)))  print(t) # {63: {37: {}}, 73: {4: {57: {74: {15: {}, 58: {}}, 4: {}}, 58: {4: {33: {}, 56: {}, 70: {}}, 49: {}, 38: {85: {}}}, 66: {22: {79: {}}, 1: {}, 2: {9: {}, 19: {}}}}}}  print(s) # {63: {37: {}}, 73: {}}   

Вот пример того, как я бы создал новое «обрезанное» дерево с помощью рекурсии.

Чтобы все было просто, я создам двоичное дерево. Я собираюсь использовать это изображение в качестве ссылки.

Вот код для создания дерева на основе примера изображения, так что нам есть с чем работать.

 class Tree(object):  def __init__(self, data):  self.left = None  self.right = None  self.data = data  ####All of the main Nodes#### tree_start = Tree("Has feathers") can_fly = Tree("Can fly") has_finns = Tree("Has finns") hawk = Tree("Hawk") penguin = Tree("Penguin") dolphin = Tree("Dolphin") bear = Tree("Bear")  #####Connect the nodes#### #does it have feathers? tree_start.left = can_fly tree_start.right = has_finns  #can it fly? can_fly.left = hawk can_fly.right = penguin  #does it have finns? has_finns.left = dolphin has_finns.right = bear  

Вот как мы можем создать недавно обрезанное дерево с помощью рекурсии

 #Recursive Funciton def prune_tree(treeNode, keys_to_prune):    if treeNode is None:  return    if treeNode.data in keys_to_prune:  print("pruning this branch: {}".format(treeNode.data))  return    newTreeNode = Tree(treeNode.data)    if treeNode.left is not None:  newTreeNode.left = (prune_tree(treeNode.left, keys_to_prune))   if treeNode.right is not None:  newTreeNode.right = (prune_tree(treeNode.right, keys_to_prune))   return newTreeNode   

Вызовите нашу функцию обрезки

 prunedTree = prune_tree(tree_start, ["Can fly"])   

Эта последняя часть необязательна, но мы можем использовать аналогичную логику рекурсии для распечатки ветвей нашего нового дерева

 def print_tree(tree):  if tree:  print(tree.data)  print_tree(tree.left)  print_tree(tree.right)  

вызовите функцию печати

 print_tree(prunedTree)   

конечным результатом всего этого является:

 pruning this branch: Can fly Has feathers Has finns Dolphin Bear