二叉树 | 月空人

什么是二叉树？

二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树是一种非常基础且重要的数据结构，被广泛应用于计算机科学中的许多领域，包括算法、数据结构、数据库、编译器等。

二叉树的主要特性包括：

每个节点最多有两个子节点。
左子节点的值通常小于其父节点的值，而右子节点的值通常大于其父节点的值（这种二叉树称为二叉搜索树）。
二叉树的遍历通常有四种方式：前序遍历、中序遍历、后序遍历和层序遍历。

二叉树的表示方法有多种，其中一种常见的方法是使用节点对象，每个节点对象包含一个值和两个指向其左右子节点的引用。例如，在JavaScript中，可以使用以下代码定义一个二叉树节点：

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

在这个定义中，val是节点的值，left和right是指向左右子节点的引用。如果子节点不存在，则相应的引用为null。

前序遍历

二叉树的前序遍历是一种深度优先遍历方法，按照“根-左-右”的顺序访问节点。以下是前序遍历的两种实现方式：递归和迭代。

递归

function preorderTraversal(root) {
    if (!root)
        return [];

    const result = [];
    const traversal = (node) => {
        result.push(node.val);
        if (node.left)
            traversal(node.left);
        if (node.right)
            traversal(node.right);
    };

    traversal(root);
    return result;
}

迭代

function preorderTraversal(root) {
    if (!root)
        return [];

    const stack = [root];
    const result = [];

    while (stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);
        if (node.right)
            stack.push(node.right);
        if (node.left)
            stack.push(node.left);
    }

    return result;
}

中序遍历

二叉树的中序遍历是一种深度优先遍历方法，按照“左-根-右”的顺序访问节点。以下是中序遍历的两种实现方式：递归和迭代。

递归

function inorderTraversal(root) {
    if (!root)
        return [];

    const result = [];
    const traversal = (node) => {
        if (node.left)
            traversal(node.left);
        result.push(node.val);
        if (node.right)
            traversal(node.right);
    };

    traversal(root);
    return result;
}

迭代

function inorderTraversal(root) {
    if (!root)
        return [];

    const stack = [];
    let cur = root;
    const result = [];

    while (stack.length > 0 || cur) {
        if (cur) {
            stack.push(cur);
            cur = cur.left;
        }
        else {
            const node = stack.pop();
            result.push(node.val);
            cur = node.right;
        }
    }

    return result;
}

后序遍历

二叉树的后序遍历是一种深度优先遍历方法，按照“左-右-根”的顺序访问节点。以下是后序遍历的迭代实现：

递归

function inorderTraversal(root) {
    if (!root)
        return [];

    const result = [];
    const traversal = (node) => {
        if (node.left)
            traversal(node.left);
        if (node.right)
            traversal(node.right);
        result.push(node.val);
    };

    traversal(root);
    return result;
}

迭代

function postorderTraversal(root) {
    if (!root)
        return [];

    const stack = [root];
    const result = [];

    while (stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);
        if (node.left)
            stack.push(node.left);
        if (node.right)
            stack.push(node.right);
    }

    return result.reverse(); // 反转结果数组以获得正确的顺序
}

层序遍历

二叉树的层序遍历是一种广度优先遍历方法，按照“从上到下，从左到右”的顺序访问节点。以下是层序遍历的实现：

递归

function levelOrderTraversal(root) {
    const result = [];

    function traverse(node, level = 0) {
        if (!node)
            return;

        if (!result[level]) {
            result[level] = [];
        }

        result[level].push(node.val);

        traverse(node.left, level + 1);
        traverse(node.right, level + 1);
    }

    traverse(root);
    return result;
}

迭代

function levelOrderTraversal(root) {
    if (!root)
        return [];

    const queue = [root];
    const result = [];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const level = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            level.push(node.val);

            if (node.left)
                queue.push(node.left);
            if (node.right)
                queue.push(node.right);
        }

        result.push(level);
    }

    return result;
}

在这个实现中，我们使用一个队列来保存当前层的节点。在每次循环中，我们首先记录当前层的节点数量，然后遍历这些节点，将它们的值添加到当前层的数组中，并将它们的子节点添加到队列中。最后，我们将当前层的数组添加到结果数组中。这样，我们就可以按照从上到下，从左到右的顺序访问二叉树的节点了。