二叉树基础知识

为什么前端开发要学习二叉树？

二叉树在前端开发中有广泛应用：

• DOM树的操作和遍历
• 组件树的管理
• 状态管理工具的数据结构
• 前端路由的实现
• 抽象语法树(AST)的处理

二叉树的核心概念

1. 基本特性

• 每个节点最多有两个子节点
• 第i层最大节点数：2^(i-1)
• 深度为k的最大节点总数：2^k - 1
• 叶节点数(n0)与度为2的节点数(n2)关系：n0 = n2 + 1

2. 二叉树节点的实现

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

二叉树的遍历方法

1. 深度优先遍历(DFS)

前序遍历(根->左->右)

// 递归实现
function preorder(root) {
    if (!root) return;
    console.log(root.val);    // 处理当前节点
    preorder(root.left);      // 遍历左子树
    preorder(root.right);     // 遍历右子树
}

// 迭代实现
function preorderIterative(root) {
    if (!root) return;
    const stack = [root];
    
    while (stack.length) {
        const node = stack.pop();
        console.log(node.val);
        // 注意：先压入右节点，再压入左节点
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
}

中序遍历(左->根->右)

// 迭代实现
function inorderIterative(root) {
    const stack = [];
    let current = root;
    
    while (stack.length || current) {
        // 遍历到最左节点
        while (current) {
            stack.push(current);
            current = current.left;
        }
        
        current = stack.pop();
        console.log(current.val);
        current = current.right;
    }
}

2. 广度优先遍历(BFS)

function levelOrder(root) {
    if (!root) return [];
    const queue = [root];
    const result = [];
    
    while (queue.length) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(currentLevel);
    }
    
    return result;
}

特殊的二叉树

1. 二叉搜索树(BST)

特点：

• 左子树所有节点值 < 根节点值
• 右子树所有节点值 > 根节点值
• 常用于快速查找和维护有序数据

class BST {
    constructor() {
        this.root = null;
    }
    
    insert(val) {
        const newNode = new TreeNode(val);
        
        if (!this.root) {
            this.root = newNode;
            return;
        }
        
        let current = this.root;
        while (true) {
            if (val < current.val) {
                if (!current.left) {
                    current.left = newNode;
                    break;
                }
                current = current.left;
            } else {
                if (!current.right) {
                    current.right = newNode;
                    break;
                }
                current = current.right;
            }
        }
    }
}

2. 平衡二叉树

特点：

• 任意节点的左右子树高度差不超过1
• 保证树的高度在logN级别，提供稳定的性能

实际应用示例

1. 组件树的遍历

function traverseComponentTree(component) {
    // 前序遍历处理组件
    console.log(component.name);
    
    // 遍历子组件
    component.children?.forEach(child => {
        traverseComponentTree(child);
    });
}

2. 虚拟DOM的diff算法

function diffTree(oldNode, newNode) {
    if (!oldNode) return { type: 'CREATE', node: newNode };
    if (!newNode) return { type: 'REMOVE' };
    if (oldNode.type !== newNode.type) return { type: 'REPLACE', node: newNode };
    
    // 递归比较子节点
    const childPatches = [];
    oldNode.children?.forEach((child, i) => {
        childPatches.push(diffTree(child, newNode.children[i]));
    });
    
    return { type: 'UPDATE', patches: childPatches };
}

性能优化技巧

1. 使用迭代替代递归避免栈溢出
2. 合理使用缓存减少重复计算
3. 注意平衡性，避免树的退化

常见面试题

1. 如何判断二叉树是否对称？
2. 如何求二叉树的最大深度？
3. 如何序列化和反序列化二叉树？

推荐练习

1. LeetCode 94: 二叉树的中序遍历
2. LeetCode 102: 二叉树的层序遍历
3. LeetCode 236: 二叉树的最近公共祖先