二叉树遍历 - 动态演示

# ========================================
# 二叉树遍历 - Python 实现
# ========================================

from typing import Optional, List


class TreeNode:
    """二叉树节点"""
    def __init__(self, val: int = 0):
        self.val = val
        self.left: Optional[TreeNode] = None
        self.right: Optional[TreeNode] = None


class BinaryTree:

    # ── 前序遍历：根 → 左 → 右 ──────────────────
    def preorder(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        return [root.val] + self.preorder(root.left) + self.preorder(root.right)

    # ── 前序遍历（迭代版）───────────────────────
    def preorder_iter(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        result, stack = [], [root]
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return result

    # ── 中序遍历：左 → 根 → 右 ──────────────────
    def inorder(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        return self.inorder(root.left) + [root.val] + self.inorder(root.right)

    # ── 中序遍历（迭代版）───────────────────────
    def inorder_iter(self, root: Optional[TreeNode]) -> List[int]:
        result, stack, curr = [], [], root
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            result.append(curr.val)
            curr = curr.right
        return result

    # ── 后序遍历：左 → 右 → 根 ──────────────────
    def postorder(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        return self.postorder(root.left) + self.postorder(root.right) + [root.val]

    # ── 后序遍历（迭代版）───────────────────────
    def postorder_iter(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        result, stack = [], [root]
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return result[::-1]


# ── 构建测试树并运行 ─────────────────────────
def build_tree() -> TreeNode:
    #        1
    #      /   \
    #     2     3
    #    / \   / \
    #   4   5 6   7
    root = TreeNode(1)
    root.left  = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left   = TreeNode(4)
    root.left.right  = TreeNode(5)
    root.right.left  = TreeNode(6)
    root.right.right = TreeNode(7)
    return root


if __name__ == "__main__":
    tree = BinaryTree()
    root = build_tree()
    print(f"前序遍历: {tree.preorder(root)}")   # [1, 2, 4, 5, 3, 6, 7]
    print(f"中序遍历: {tree.inorder(root)}")    # [4, 2, 5, 1, 6, 3, 7]
    print(f"后序遍历: {tree.postorder(root)}")  # [4, 5, 2, 6, 7, 3, 1]

// ========================================
// 二叉树遍历 - Go 实现
// ========================================

package main

import "fmt"

// TreeNode 二叉树节点
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// NewNode 创建新节点
func NewNode(val int) *TreeNode {
    return &TreeNode{Val: val}
}

// ── 前序遍历：根 → 左 → 右 ──────────────────
func Preorder(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    result := []int{root.Val}
    result = append(result, Preorder(root.Left)...)
    result = append(result, Preorder(root.Right)...)
    return result
}

// PreorderIter 前序遍历（迭代版）
func PreorderIter(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    result := []int{}
    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, node.Val)
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }
    return result
}

// ── 中序遍历：左 → 根 → 右 ──────────────────
func Inorder(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    result := Inorder(root.Left)
    result = append(result, root.Val)
    result = append(result, Inorder(root.Right)...)
    return result
}

// InorderIter 中序遍历（迭代版）
func InorderIter(root *TreeNode) []int {
    result := []int{}
    stack := []*TreeNode{}
    curr := root
    for curr != nil || len(stack) > 0 {
        for curr != nil {
            stack = append(stack, curr)
            curr = curr.Left
        }
        curr = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, curr.Val)
        curr = curr.Right
    }
    return result
}

// ── 后序遍历：左 → 右 → 根 ──────────────────
func Postorder(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    result := Postorder(root.Left)
    result = append(result, Postorder(root.Right)...)
    result = append(result, root.Val)
    return result
}

// PostorderIter 后序遍历（迭代版）
func PostorderIter(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    result := []int{}
    stack := []*TreeNode{root}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append([]int{node.Val}, result...)
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
    }
    return result
}

// ── main 函数 ────────────────────────────────
func main() {
    //      1
    //    /   \
    //   2     3
    //  / \   / \
    // 4   5 6   7
    root := NewNode(1)
    root.Left         = NewNode(2)
    root.Right        = NewNode(3)
    root.Left.Left    = NewNode(4)
    root.Left.Right   = NewNode(5)
    root.Right.Left   = NewNode(6)
    root.Right.Right  = NewNode(7)

    fmt.Println("前序遍历:", Preorder(root))   // [1 2 4 5 3 6 7]
    fmt.Println("中序遍历:", Inorder(root))    // [4 2 5 1 6 3 7]
    fmt.Println("后序遍历:", Postorder(root))  // [4 5 2 6 7 3 1]
}

<?php
// ========================================
// 二叉树遍历 - PHP 实现
// ========================================

class TreeNode
{
    public int        $val;
    public ?TreeNode $left  = null;
    public ?TreeNode $right = null;

    public function __construct(int $val)
    {
        $this->val = $val;
    }
}

class BinaryTree
{
    // ── 前序遍历：根 → 左 → 右 ──────────────────
    public function preorder(?TreeNode $root): array
    {
        if ($root === null) return [];
        return array_merge(
            [$root->val],
            $this->preorder($root->left),
            $this->preorder($root->right)
        );
    }

    // ── 前序遍历（迭代版）───────────────────────
    public function preorderIter(?TreeNode $root): array
    {
        if ($root === null) return [];
        $result = [];
        $stack  = [$root];
        while (!empty($stack)) {
            $node     = array_pop($stack);
            $result[] = $node->val;
            if ($node->right !== null) $stack[] = $node->right;
            if ($node->left  !== null) $stack[] = $node->left;
        }
        return $result;
    }

    // ── 中序遍历：左 → 根 → 右 ──────────────────
    public function inorder(?TreeNode $root): array
    {
        if ($root === null) return [];
        return array_merge(
            $this->inorder($root->left),
            [$root->val],
            $this->inorder($root->right)
        );
    }

    // ── 中序遍历（迭代版）───────────────────────
    public function inorderIter(?TreeNode $root): array
    {
        $result = [];
        $stack  = [];
        $curr   = $root;
        while ($curr !== null || !empty($stack)) {
            while ($curr !== null) {
                $stack[] = $curr;
                $curr    = $curr->left;
            }
            $curr     = array_pop($stack);
            $result[] = $curr->val;
            $curr     = $curr->right;
        }
        return $result;
    }

    // ── 后序遍历：左 → 右 → 根 ──────────────────
    public function postorder(?TreeNode $root): array
    {
        if ($root === null) return [];
        return array_merge(
            $this->postorder($root->left),
            $this->postorder($root->right),
            [$root->val]
        );
    }

    // ── 后序遍历（迭代版）───────────────────────
    public function postorderIter(?TreeNode $root): array
    {
        if ($root === null) return [];
        $result = [];
        $stack  = [$root];
        while (!empty($stack)) {
            $node     = array_pop($stack);
            $result[] = $node->val;
            if ($node->left  !== null) $stack[] = $node->left;
            if ($node->right !== null) $stack[] = $node->right;
        }
        return array_reverse($result);
    }
}

// ── 构建测试树 ───────────────────────────────
$root               = new TreeNode(1);
$root->left         = new TreeNode(2);
$root->right        = new TreeNode(3);
$root->left->left   = new TreeNode(4);
$root->left->right  = new TreeNode(5);
$root->right->left  = new TreeNode(6);
$root->right->right = new TreeNode(7);

$tree = new BinaryTree();

echo "前序遍历: " . implode(", ", $tree->preorder($root)) . "\n";  // 1,2,4,5,3,6,7
echo "中序遍历: " . implode(", ", $tree->inorder($root))  . "\n";  // 4,2,5,1,6,3,7
echo "后序遍历: " . implode(", ", $tree->postorder($root)) . "\n";  // 4,5,2,6,7,3,1

🌲 二叉树遍历 · 动态演示

🔴 前序遍历 (Pre-order)

🟢 中序遍历 (In-order)

🟠 后序遍历 (Post-order)

二叉树可视化

控制面板