当前位置: 首页 > 知识库问答 >
问题:

Python在二叉树中检查到叶的路径Python在叶中提供数据

宇文灿
2023-03-14

假设我有一棵树:

                                     cough
                      Yes /                            \ No
                   sneezing                        sneezing
               Yes /       \ No                Yes /       \ No
             fever         fever               fever         fever
       Yes /    \ No    Yes/     \No       Yes /    \ No    Yes/     \No
       dead   cold   influenza   cold      dead   influenza cold   healthy

我想要疾病的路径“流感”输出应该是这样的:

[[True,False,True],[False,True,False]]

如果您转到根的右侧,它将返回True(是),如果您转到左侧,它将返回False(否)

这是我一直在尝试为此函数执行的代码,但我做错了什么,它返回的不是我想要的...

def paths_to_illness(self, illness):

    head=self.__root
    new_list=[]
    new_list=diagnoser.get_path(head,illness)
    return new_list

def get_path(self,head,illness):

    if head is None:
        return []
    if (head.positive_child == None and head.negative_child==None):
        return [head.data]

    left_tree=diagnoser.get_path(head.negative_child,illness)
    right_tree=diagnoser.get_path(head.positive_child,illness)
    all_tree=left_tree+right_tree

    list1=[]

    for leaf in  all_tree:

        if illness == leaf:

            list1.append(["True"])
        else:
            list1.append(["False"])

    return list1

有什么办法帮我修复代码吗?谢谢

Diagnoser只是一个不重要的类,我的node类的右边是“positive\u child”,左边是“negative\u child”

如果还有什么不清楚的请告诉我

谢谢

根据要求,我的树制作代码:

class Diagnoser:
def __init__(self, root):
    self.__root = root


class Node:
 def __init__(self, data="", pos=None, neg=None):
    self.data = data
    self.positive_child = pos
    self.negative_child = neg


leaf1 = Node("dead", None, None)
leaf2 = Node("cold", None, None)
fever1 = Node("fever", leaf1, leaf2)

leaf3 = Node("influenza", None, None)
leaf4 = Node("cold", None, None)
fever2 = Node("fever", leaf3, leaf4)

sneezing1 = Node("sneezing", fever1, fever2)

leaf5 = Node("dead", None, None)
leaf6 = Node("influenza", None, None)
fever3 = Node("fever", leaf5, leaf6)

leaf7 = Node("cold", None, None)
leaf8 = Node("healthy", None, None)
fever4 = Node("fever", leaf7, leaf8)

sneezing2 = Node("sneezing", fever3, fever4)

root = Node("cough", sneezing1, sneezing2)
diagnoser = Diagnoser(root)

共有1个答案

公冶才
2023-03-14

这是我想到的

class Tree:
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left = left
    self.right = right

  @property
  def is_leaf(self):
    return not (self.left or self.right)

  def __repr__(self):
    return 'Tree({}, {}, {})'.format(self.data, self.left, self.right)

  def find(self, target, path_to=()):
    if self.is_leaf:
      if self.data == target:
        yield path_to
    else:
      if self.left:
        yield from self.left.find(target, (*path_to, True))
      if self.right:
        yield from self.right.find(target, (*path_to, False))

t = Tree('Cough', Tree('Sneezing', Tree('Fever', Tree('Dead'), Tree('Cold')), Tree('Fever', Tree('Influenza'), Tree('Cold'))), Tree('Sneezing', Tree('Fever', Tree('Dead'), Tree('Influenza')), Tree('Fever', Tree('Cold'), Tree('Healthy'))))

print(list(t.find('Influenza')))

通过让我们的find方法成为生成器,我们可以很容易地使用yield from调用堆栈中的积极结果。如果您使用的Python版本不支持参数解包(*path\u to,True),那么path\u to(True,)是等效的

编辑:这是一个不使用的版本

def find(self, target, path_to=()):
  if self.is_leaf:
    if self.data == target:
      return [path_to]
    else:
      return []
  else:
    if self.left:
      l = self.left.find(target, (*path_to, True))
    if self.right:
      r = self.right.find(target, (*path_to, False))
    return l + r
 类似资料:
  • 问题内容: 我试图使用Java在二叉树中打印所有根到叶的路径。 在主要方法中: 但是它给出了错误的输出。 给定的树: 预期产量: [5,1,3] [5、8、6] [5、8、9] 但是输出产生了: [5,1,3] [5、1、3、8、6] [5、1、3、8、6、9] 可以找出一个… 问题答案: 用以下方法调用递归方法: 传递时会发生什么(而不是在所有方法调用中使用单个对象,这意味着,当您返回原始调用者

  • 我试图搜索给定红黑树中所有根到叶的路径。特别是,我想编写一个测试,在给定rbt的情况下,该测试将断言每个路径具有相同数量的黑色节点。 我用两个全局变量尝试这样的东西: 然而,当左分支中的黑色节点右侧有红色节点时,我遇到了麻烦,因为这意味着计数比应该减少的更多。 有没有更好的方法来搜索根到叶的路径,计算特定值的频率,然后以某种方式比较计数?或者,如果给定rbt余额,是否有一种完全不同的方法来测试rb

  • 上面的函数将包含二叉树每个叶的路径的数组附加到全局数组。 代码工作正常,但我想删除全局变量,并使函数返回数组。我怎么能那样做?

  • 问题查找具有n个节点的完整二叉树中的叶节点数。 我为上述问题编写了一个递归程序,每当我到达一个没有子节点的节点时,遍历树并增加叶节点的数量。但由于这棵树是一棵完整的二叉树,我认为这会使问题变得更容易,但我不知道如何解决。它是否可以简化为紧凑形式(类似于公式)。

  • 我试图找到从根到叶的最小路径和,还需要计算最小路径。如果解决方案在左子树中,我的解决方案有效,但是如果结果在右子树中,根节点在结果路径中添加了两次,是否有人可以查看我的解决方案并帮助我修复此错误,如果有,还可以建议更好的运行时解决方案 我正在使用回溯访问所有节点,我认为我的解决方案的时间复杂度将是O(N)(因为所有节点都应该被访问,如果我错了,请纠正我)

  • 给定一棵二叉树,问题是找到所有根到叶的路径。我们通过以列表的形式传递路径,并在到达叶子时将其添加到结果中来了解算法。 我的问题是存储所有路径需要多少空间。我的直觉是,每条路径将消耗树高度(O(h))的内存顺序,如果我们的完整二叉树中有2*n-1个节点,那么每个节点对应于一条路径,因此假设树高度平衡,空间复杂度将为O(n*log(n))。我的分析正确吗?