因为Python是动态类型的，所以定义你需要的任何类都没有问题。

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

即使你对输入这些定义感兴趣，你也可以像在任何其他基于类的面向对象语言中一样这样做：

from typing import Union

class Tree:
    left: Union['Tree', int]
    right: Union['Tree', int]
    def __init__(self, left: Union['Tree', int], right: Union['Tree', int]) -> None:
        self.left = left
        self.right = right

注意类型名称使用字符串（在最近的Python版本中可以避免）。
请参阅mypy中的open issue，了解直接递归代数类型，例如

Tree = Union[Tuple['Tree', 'Tree'], int]

定义WordTree的最常见（尽管不一定推荐）方法是使用超类和浅层次结构：

from typing import List, final

class WordTree: pass

@final
class Word(WordTree):
    word: str

@final
class Subword(WordTree):
    subword: str
    children: List[WordTree]

@final
class Root(WordTree):
    children: List[WordTree]

使用这样的实现可能需要使用isinstance检查（尽管Python3.10为这些检查提供了nice sugar）。为了避免混乱，本例中省略了构造函数;您可能希望使用dataclass轻松获取它们和其他类型的行为。
到目前为止，Python没有提供任何方法来禁止不相关的类从WordTree继承，从而破坏了对此类程序进行静态推理的能力。
其他一些OOP语言，比如Scala和Kotlin，以及（即将推出的）Java，可以采用这样的定义（使用sealed classes），并给予与Haskell等函数式语言类似的类型检查和语法构造。
据我所知，这种设计通常只推荐用于纯数据类，比如AST。它不太适合定义面向用户的容器，如trie，因为它公开了数据结构的内部工作原理。因此，即使采用这种设计，您也可能希望将其用作实现细节，并使用另一个类Trie，由客户机代码通过定义良好的API使用。这个类可以有一个WordTree字段，或者任何其他实现相同逻辑的方式。
这对于面向对象设计与功能设计的区别至关重要。后者侧重于数据流和静态推理，而前者侧重于API，可扩展性和解耦。我认为这是有帮助的，当在语言和环境之间移植时-尽管如上所述，一些语言试图启用两种设计方法。

下面是Python 3.10中Haskell二叉树的等价实现。静态类型检查可以用mypy来完成。

from __future__ import annotations
from dataclasses import dataclass
from typing import Generic, TypeVar

T = TypeVar("T")

@dataclass
class Branch(Generic[T]):
    value: T
    left: Tree[T]
    right: Tree[T]

@dataclass
class Leaf(Generic[T]):
    value: T

Tree = Branch[T] | Leaf [T]

你可以这样使用它（注意contains函数中的模式匹配-Python 3.10的新特性）：

def contains(tree: Tree[T], value: T):
    match tree:
        case Leaf(x):
            return x == value
        case Branch(x, left, right):
            return x == value or contains(left, value) or contains(right, value)

tree = Branch(
    1,
    Branch(2, Leaf(3), Leaf(4)),
    Branch(5, Leaf(6), Branch(4, Leaf(7), Leaf(8)))
)

assert contains(tree, 1)
assert contains(tree, 5)
assert contains(tree, 8)

要实现WordTree，您需要执行以下操作：

from __future__ import annotations
from dataclasses import dataclass

@dataclass
class Word:
    value: str

@dataclass
class Subword:
    value: str
    trees: list[WordTree]

@dataclass
class Root:
    trees: list[WordTree]

WordTree = Word | Subword | Root

关于进口的说明：

• from __future__ import annotations允许使用尚未定义的类型的名称进行注解。
• @dataclass会自动为您定义一个构造函数。

我偶然发现这篇文章，希望实现以下内容：
整数nestedList的嵌套列表每个元素是一个整数或一个列表，其元素也可以是整数或其他列表。
我的实现如下。

class NestedInteger(ABC):
    @staticmethod
    # "List" is invariant. https://mypy.readthedocs.io/en/stable/common_issues.html#variance
    def create(data: Sequence[int | list[int]]) -> list[NestedInteger]:
        root: list[NestedInteger] = []
        for x in data:
            match x:
                case int():
                    root.append(NestedInt(x))
                case _:
                    root.append(NestedList(NestedInteger.create(x)))
        return root

    @abc.abstractmethod
    def is_integer(self) -> bool:
        pass

    @abc.abstractmethod
    def get_integer(self) -> int | None:
        pass

    @abc.abstractmethod
    def get_list(self) -> list[NestedInteger] | None:
        pass

@final
@dataclasses.dataclass
class NestedInt(NestedInteger):
    val: int

    def is_integer(self) -> bool:
        return True

    def get_integer(self) -> int | None:
        return self.val

    def get_list(self) -> list[NestedInteger] | None:
        return None

@final
@dataclasses.dataclass
class NestedList(NestedInteger):
    values: list[NestedInteger]

    def is_integer(self) -> bool:
        return False

    def get_integer(self) -> int | None:
        return None

    def get_list(self) -> list[NestedInteger] | None:
        return self.values

给定[1, [4, [6]]]，上面的代码创建：

{list: 2}
├── NestedInt(val=1)
└── NestedList
    ├── NestedInt(val=4)
    └── NestedList
        └── NestedInt(val=6)