如何测试节点的子项、孙子、曾孙等的成员资格？

Question

我不确定我在这里使用的语言是否正确，但是给定树中的特定节点，我如何测试子代、孙子代等的成员关系?

1
/   
2     3 
/    / 
4   5 6   7  

基本上，我有一个标记为树的csv文件中的家谱记录。给定一个特定的人，我希望看到这个人的祖先的记录。在这种情况下，给定"2"，我将得到一个包含2、4、5的列表。给定"1"，我将得到一个包含1、2、3、4、5、6、7的列表。TY。

编辑:我认为这个问题措辞不当，我道歉。通过"language"我指的是像"节点"这样的术语;和";tree"我可能用错了我说的是"测试会员资格"。因为我不确定这是一个递归问题，也许通过数学可以得到同样的结果。我也搞混了祖先和后代。我所寻找的是关于如何从某个节点开始获得树的分支的指导。在这种情况下，结果的顺序并不重要。我会查找不同的遍历选项，谢谢!

Answer 1

您通常会递归地执行此操作。

如果您的树结构由Person对象实例组成，定义如下:

class Person:
def __init__(self,name,mother=None,father=None):
self.name   = name
self.mother = mother
self.father = father

祖先属性可以递归定义:

@property
def ancestors(self):
result = [self.name]
if self.mother: result += self.mother.ancestors
if self.father: result += self.father.ancestors
return result

输出:

person7 = Person("7")
person6 = Person("6")
person5 = Person("5")
person4 = Person("4")
person3 = Person("3",person6,person7)
person2 = Person("2",person4,person5)
person1 = Person("1",person2,person3)
print(person2.ancestors) # ['2', '4', '5']
print(person1.ancestors) # ['1', '2', '4', '5', '3', '6', '7']

请注意，将人包含在"祖先"列表中有点奇怪，但该方法符合您的预期结果

Answer 2

不知道你为什么要问语言。这个问题与语言无关。

如果树的一个节点被实现为:

class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None

那么你所需要做的就是给出一个node:

def family(node: Node):
children = [node.left, node.right]
grandchildren = [(n.left, n.right) for n in children]
return children, grandchildren