树排序

"""
树排序算法。

构建二叉搜索树，然后遍历它以获取排序后的列表。
"""
from __future__ import annotations

from collections.abc import Iterator
from dataclasses import dataclass


@dataclass
class Node:
    val: int
    left: Node | None = None
    right: Node | None = None

    def __iter__(self) -> Iterator[int]:
        if self.left:
            yield from self.left
        yield self.val
        if self.right:
            yield from self.right

    def __len__(self) -> int:
        return sum(1 for _ in self)

    def insert(self, val: int) -> None:
        if val < self.val:
            if self.left is None:
                self.left = Node(val)
            else:
                self.left.insert(val)
        elif val > self.val:
            if self.right is None:
                self.right = Node(val)
            else:
                self.right.insert(val)


def tree_sort(arr: list[int]) -> tuple[int, ...]:
    """
    >>> tree_sort([])
    ()
    >>> tree_sort((1,))
    (1,)
    >>> tree_sort((1, 2))
    (1, 2)
    >>> tree_sort([5, 2, 7])
    (2, 5, 7)
    >>> tree_sort((5, -4, 9, 2, 7))
    (-4, 2, 5, 7, 9)
    >>> tree_sort([5, 6, 1, -1, 4, 37, 2, 7])
    (-1, 1, 2, 4, 5, 6, 7, 37)

    # >>> tree_sort(range(10, -10, -1)) == tuple(sorted(range(10, -10, -1)))
    # True
    """
    if len(arr) == 0:
        return tuple(arr)
    
    # 创建根节点
    root = Node(arr[0])
    
    # 将其他元素插入到树中
    for item in arr[1:]:
        root.insert(item)
    
    # 返回排序后的元组
    return tuple(root)


if __name__ == "__main__":
    import doctest

    # 运行文档测试
    doctest.testmod()
    
    # 打印额外的测试结果
    print(f"{tree_sort([5, 6, 1, -1, 4, 37, -3, 7]) = }")