Python在二叉树中检查叶的路径python在叶中提供数据 [英] Python Checking paths to leaf in binary tree python giving data in the leaf
问题描述
让我说我有这棵树:
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
我想找到通往疾病的道路"influenza"
输出应该是这样的:
And i want the paths to the illness "influenza"
What the output should be is like this:
[[True,False,True],[False,True,False]]
如果转到根的右侧,则返回True(是),如果转到根的左侧,则返回False(否)
If you go to right of the root it return True ( Yes ) , if you go to Left its False( No)
这是我一直在尝试为该功能执行的代码,但是我做错了它返回的不是我想要的..
This is the code I have been trying to do for this function but im doing something wrong it returns not as i want..
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
有什么想法可以帮助我修复代码吗?谢谢
any ideas to help me fix my code? thanks
对角线器只是一个不重要的类,我的节点类的右边为"positive_child"
,左边为"negative_child"
the diagonser is just a class not important, my node class have the right as "positive_child"
and left "negative_child"
如果还有其他不清楚的地方,请告诉我
if anything else is unclear please let me know
谢谢!.
根据我的要求来制作树的代码:
Upon request my code for making the tree:
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)
推荐答案
这就是我想出的
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_to, True)
,那么path_to + (True,)
是等效的
By having our find
method be a generator, we can easily bubble positive results up the call stack using yield from
. If you're using a version of Python that doesn't support argument unpacking (*path_to, True)
, then path_to + (True,)
is equivalent
这是一个不使用yield
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
这篇关于Python在二叉树中检查叶的路径python在叶中提供数据的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!