什么是普通树

Question

我将用 python 构建一个非二叉树 输入格式。第一行包含顶点数 𝑛。第二行包含从 -1 到 𝑛 − 1（顶点的父节点）的 𝑛 整数。如果它们的第 i 个顶点 (0 ≤ 𝑖 ≤ 𝑛 - 1) 为 -1，则顶点 𝑖 为根，否则为第 1 个顶点的父顶点的从 0 开始的索引。确保只有一个根。确保输入代表一棵树。 输出格式。输出树的高度 输入：

5

4 -1 4 1 1

输出：

3 输入表示有 5 个节点，编号从 0 到 4，节点 0 是节点 4 的子节点，节点 1 是根节点，节点 2 是节点 4 的子节点，节点 3 是节点 1 的子节点，节点 4 是节点节点 1 的子节点。要查看这一点，我们将节点编号从 0 到 4 写在一行上，并将输入中给出的数字写在下面的第二行上：

0 1 2 3 4

4 -1 4 1 1

现在我们可以看到，节点 1 是根节点，因为 -1 对应于第二行中的节点 1。我们还知道节点 3 和 4 是根节点 1 的子节点。我们还知道节点 0 和 2 是节点 4 的子节点。

1 3 4 0 2 这棵树的高度是 3，因为从根 1 到叶子 2 的路径上的顶点数是 3。

Answer 1

正如评论中提到的：实际问题正文中没有问题。该问题可能会被删除，如果没有，值得从标题中回答实际问题。

树有非常严格的数学定义： 树是没有循环的连通图

需要指出的一件重要的事情是，大多数计算机科学家不使用该定义，而是依赖于 “一棵树（实际上是一个节点）是某些数据加上多个 self 实例。”这个定义很令人困惑，因为事物不能有不同的数据，而且它本身在所有方面都像它的孩子，因为孩子有以前的父母没有的孩子。 因此很难证明它们是相同的，即节点是树的替代定义。事实并非如此，并且需要对每个节点的连接进行额外冗长的检查，以验证是否存在诸如 Floyd-Warshall 算法之类的循环。所以 Tree 和 TreeNode 是根本不同的东西。但是，您只使用节点，因为它们拥有其下的整个树的所有权。

这是 Python 中树的一个很好的定义：

    T = TypeVar('T')
class Node(Generic[T]):
    def __init__(self, value_type : Type[T], parent=None):
        self.parent = parent
        self.children = set()
        self.value = value_type()
    def add_child(self, child)->None:
        child.set_parent = self
        self.children.add(child)
    def add_child_x(self, child)->bool:
        if child not in self.children:
            self.add_child(child)
            return True
        return False
    def add_children(self, children : list)->None:
        for child in children:
            self.add_child(child)
    def remove_child(self, child)->bool:
        if child in self.children:
            child.set_parent(None)
            self.children.remove(child)
            return True
        return False
    def set_parent(self, parent):
        self.parent = parent
    def sever(self):
        self.set_parent(None)
    def set_value(self, value):
        self.value = value
    def outstr(self, indent = 0):
        outstr = ''
        if indent:
            outstr += '\n' +(' '*indent) + '↑___'
        elif not self.parent:
            outstr += '*'
        outstr += str(self.value)
        for child in self.children:
            outstr += child.outstr(indent+len(str(self.value)))
        return outstr
    def print(self):
        print(self.outstr())

    def get_root(self):
        back = self
        while back.parent is not None:
            back = back.parent
        return back
        
    def get_leafs(self):
        stack = [self]
        leafs = list()
        while stack:
            node = stack.pop()
            if node.children:
                stack.extend(node.children)
            else:
                leafs.append(node)
        return leafs