tree.mojo

from memory import UnsafePointer


@value
struct Node:
    alias _Ptr = UnsafePointer[Self]

    var value: Int
    var left: Self._Ptr
    var right: Self._Ptr

    fn __init__(out self, value: Int):
        self.value = value
        self.left = Self._Ptr()
        self.right = Self._Ptr()


# 前序遍历 (根 -> 左 -> 右)
fn preorder_traversal(node: UnsafePointer[Node]):
    if not node:
        return

    print(node[].value, end=" ")
    preorder_traversal(node[].left)
    preorder_traversal(node[].right)


# 中序遍历 (左 -> 根 -> 右)
fn inorder_traversal(node: UnsafePointer[Node]):
    if not node:
        return

    inorder_traversal(node[].left)
    print(node[].value, end=" ")
    inorder_traversal(node[].right)


# 后序遍历 (左 -> 右 -> 根)
fn postorder_traversal(node: UnsafePointer[Node]):
    if not node:
        return

    postorder_traversal(node[].left)
    postorder_traversal(node[].right)
    print(node[].value, end=" ")


fn main():
    # 创建更多节点构建完整的二叉树
    # 树的结构:
    #       1
    #      / \
    #     2   3
    #    / \ / \
    #   4  5 6  7

    var root = Node(1)
    var node2 = Node(2)
    var node3 = Node(3)
    var node4 = Node(4)
    var node5 = Node(5)
    var node6 = Node(6)
    var node7 = Node(7)

    # 构建二叉树连接
    root.left = UnsafePointer(to=node2)
    root.right = UnsafePointer(to=node3)

    node2.left = UnsafePointer(to=node4)
    node2.right = UnsafePointer(to=node5)

    node3.left = UnsafePointer(to=node6)
    node3.right = UnsafePointer(to=node7)

    print("二叉树结构:")
    print("       1")
    print("      / \\")
    print("     2   3")
    print("    / \\ / \\")
    print("   4  5 6  7")
    print()

    print("前序遍历 (根->左->右): ", end="")
    preorder_traversal(UnsafePointer(to=root))
    print()

    print("中序遍历 (左->根->右): ", end="")
    inorder_traversal(UnsafePointer(to=root))
    print()

    print("后序遍历 (左->右->根): ", end="")
    postorder_traversal(UnsafePointer(to=root))
    print()