算法結構 - 樹(shù)形結構

樹(shù)形結構處理算法

1. 扁平數據轉樹(shù)形結構

// 菜單扁平轉樹(shù)形算法
export function menuFlatToTree(data) {
    if (!Array.isArray(data) || data.length === 0) {
        return [];
    }
    
    const tree = [];
    const map = {};

    // 創(chuàng  )建映射表
    for (const menu of data) {
        if (menu.zyDm && menu.zyDm.trim() !== '') {
            map[menu.zyDm] = { ...menu, children: [] };
        }
    }

    // 構建樹(shù)形結構
    for (const menu of data) {
        if (menu.zyDm && menu.zyDm.trim() !== '') {
            if (menu.fjdZyDm === 'root' || !menu.fjdZyDm) {
                // 根節點(diǎn)
                tree.push(map[menu.zyDm]);
            } else {
                // 子節點(diǎn)
                const parent = map[menu.fjdZyDm];
                if (parent) {
                    if (!parent.children) {
                        parent.children = [];
                    }
                    parent.children.push(map[menu.zyDm]);
                }
            }
        }
    }

    // 排序處理
    tree.sort((a, b) => (a.xh || 0) - (b.xh || 0));
    
    // 遞歸排序子節點(diǎn)
    const sortChildren = (nodes) => {
        if (!nodes || !Array.isArray(nodes)) return;
        
        nodes.sort((a, b) => (a.xh || 0) - (b.xh || 0));
        nodes.forEach(node => {
            if (node.children && node.children.length > 0) {
                sortChildren(node.children);
            }
        });
    };
    
    sortChildren(tree);
    return tree;
}

// 通用扁平轉樹(shù)形算法
export function flatToTree(data, idField = 'id', parentField = 'parentId', childrenField = 'children') {
    if (!Array.isArray(data)) return [];
    
    const tree = [];
    const map = {};
    
    // 創(chuàng  )建映射表
    data.forEach(item => {
        map[item[idField]] = { ...item, [childrenField]: [] };
    });
    
    // 構建樹(shù)形結構
    data.forEach(item => {
        const parentId = item[parentField];
        
        if (parentId === null || parentId === undefined || parentId === '' || !map[parentId]) {
            // 根節點(diǎn)
            tree.push(map[item[idField]]);
        } else {
            // 子節點(diǎn)
            if (!map[parentId][childrenField]) {
                map[parentId][childrenField] = [];
            }
            map[parentId][childrenField].push(map[item[idField]]);
        }
    });
    
    return tree;
}

2. 樹(shù)形結構轉扁平數據

// 樹(shù)形轉扁平算法（深度優(yōu)先）
export function treeToFlatDFS(tree, childrenField = 'children') {
    if (!Array.isArray(tree)) return [];
    
    const result = [];
    
    const traverse = (node, parentId = null) => {
        if (!node) return;
        
        // 復制節點(diǎn)，移除children字段
        const { [childrenField]: children, ...nodeData } = node;
        result.push({ ...nodeData, parentId });
        
        // 遞歸處理子節點(diǎn)
        if (children && Array.isArray(children)) {
            children.forEach(child => {
                traverse(child, node.id || node.zyDm);
            });
        }
    };
    
    tree.forEach(node => traverse(node));
    return result;
}

// 樹(shù)形轉扁平算法（廣度優(yōu)先）
export function treeToFlatBFS(tree, childrenField = 'children') {
    if (!Array.isArray(tree)) return [];
    
    const result = [];
    const queue = [...tree.map(node => ({ node, parentId: null }))];
    
    while (queue.length > 0) {
        const { node, parentId } = queue.shift();
        
        if (!node) continue;
        
        // 復制節點(diǎn)，移除children字段
        const { [childrenField]: children, ...nodeData } = node;
        result.push({ ...nodeData, parentId });
        
        // 將子節點(diǎn)加入隊列
        if (children && Array.isArray(children)) {
            children.forEach(child => {
                queue.push({
                    node: child,
                    parentId: node.id || node.zyDm
                });
            });
        }
    }
    
    return result;
}

樹(shù)形結構搜索算法

1. 深度優(yōu)先搜索

// 深度優(yōu)先搜索樹(shù)節點(diǎn)
export function dfsTreeSearch(tree, predicate, path = []) {
    if (!tree || !Array.isArray(tree)) return null;
    
    for (const node of tree) {
        const currentPath = [...path, node];
        
        if (predicate(node)) {
            return {
                node: node,
                path: currentPath
            };
        }
        
        if (node.children && node.children.length > 0) {
            const result = dfsTreeSearch(node.children, predicate, currentPath);
            if (result) return result;
        }
    }
    
    return null;
}

// 深度優(yōu)先搜索所有匹配節點(diǎn)
export function dfsTreeSearchAll(tree, predicate, path = []) {
    if (!tree || !Array.isArray(tree)) return [];
    
    const results = [];
    
    for (const node of tree) {
        const currentPath = [...path, node];
        
        if (predicate(node)) {
            results.push({
                node: node,
                path: currentPath
            });
        }
        
        if (node.children && node.children.length > 0) {
            const childResults = dfsTreeSearchAll(node.children, predicate, currentPath);
            results.push(...childResults);
        }
    }
    
    return results;
}

2. 廣度優(yōu)先搜索

// 廣度優(yōu)先搜索樹(shù)節點(diǎn)
export function bfsTreeSearch(tree, predicate) {
    if (!tree || !Array.isArray(tree)) return null;
    
    const queue = [...tree.map(node => ({ node, path: [node] }))];
    
    while (queue.length > 0) {
        const { node, path } = queue.shift();
        
        if (predicate(node)) {
            return { node, path };
        }
        
        if (node.children && node.children.length > 0) {
            for (const child of node.children) {
                queue.push({
                    node: child,
                    path: [...path, child]
                });
            }
        }
    }
    
    return null;
}

// 廣度優(yōu)先搜索所有匹配節點(diǎn)
export function bfsTreeSearchAll(tree, predicate) {
    if (!tree || !Array.isArray(tree)) return [];
    
    const results = [];
    const queue = [...tree.map(node => ({ node, path: [node] }))];
    
    while (queue.length > 0) {
        const { node, path } = queue.shift();
        
        if (predicate(node)) {
            results.push({ node, path });
        }
        
        if (node.children && node.children.length > 0) {
            for (const child of node.children) {
                queue.push({
                    node: child,
                    path: [...path, child]
                });
            }
        }
    }
    
    return results;
}

樹(shù)形結構遍歷算法

1. 深度優(yōu)先遍歷

// 深度優(yōu)先前序遍歷
export function dfsPreOrder(tree, callback) {
    if (!tree || !Array.isArray(tree)) return;
    
    for (const node of tree) {
        callback(node);
        
        if (node.children && node.children.length > 0) {
            dfsPreOrder(node.children, callback);
        }
    }
}

// 深度優(yōu)先后序遍歷
export function dfsPostOrder(tree, callback) {
    if (!tree || !Array.isArray(tree)) return;
    
    for (const node of tree) {
        if (node.children && node.children.length > 0) {
            dfsPostOrder(node.children, callback);
        }
        
        callback(node);
    }
}

// 深度優(yōu)先中序遍歷（適用于二叉樹(shù)）
export function dfsInOrder(tree, callback) {
    if (!tree || !Array.isArray(tree)) return;
    
    // 假設每個(gè)節點(diǎn)最多有兩個(gè)子節點(diǎn)（左、右）
    for (const node of tree) {
        if (node.leftChildren) {
            dfsInOrder(node.leftChildren, callback);
        }
        
        callback(node);
        
        if (node.rightChildren) {
            dfsInOrder(node.rightChildren, callback);
        }
    }
}

2. 廣度優(yōu)先遍歷

// 廣度優(yōu)先遍歷
export function bfsTraverse(tree, callback) {
    if (!tree || !Array.isArray(tree)) return;
    
    const queue = [...tree];
    
    while (queue.length > 0) {
        const node = queue.shift();
        callback(node);
        
        if (node.children && node.children.length > 0) {
            queue.push(...node.children);
        }
    }
}

// 按層級遍歷
export function levelOrderTraverse(tree, callback) {
    if (!tree || !Array.isArray(tree)) return;
    
    let currentLevel = [...tree];
    let level = 0;
    
    while (currentLevel.length > 0) {
        const nextLevel = [];
        
        for (const node of currentLevel) {
            callback(node, level);
            
            if (node.children && node.children.length > 0) {
                nextLevel.push(...node.children);
            }
        }
        
        currentLevel = nextLevel;
        level++;
    }
}

樹(shù)形結構操作算法

1. 節點(diǎn)查找和操作

// 根據ID查找節點(diǎn)
export function findNodeById(tree, id, idField = 'id') {
    return dfsTreeSearch(tree, node => node[idField] === id);
}

// 根據條件查找節點(diǎn)
export function findNodeByCondition(tree, condition) {
    return dfsTreeSearch(tree, condition);
}

// 更新節點(diǎn)
export function updateNode(tree, id, updates, idField = 'id') {
    if (!tree || !Array.isArray(tree)) return tree;
    
    return tree.map(node => {
        if (node[idField] === id) {
            return { ...node, ...updates };
        }
        
        if (node.children && node.children.length > 0) {
            return {
                ...node,
                children: updateNode(node.children, id, updates, idField)
            };
        }
        
        return node;
    });
}

// 刪除節點(diǎn)
export function deleteNode(tree, id, idField = 'id') {
    if (!tree || !Array.isArray(tree)) return tree;
    
    return tree.filter(node => {
        if (node[idField] === id) {
            return false;
        }
        
        if (node.children && node.children.length > 0) {
            node.children = deleteNode(node.children, id, idField);
        }
        
        return true;
    });
}

2. 樹(shù)形結構統計

// 計算樹(shù)的高度
export function treeHeight(tree) {
    if (!tree || !Array.isArray(tree)) return 0;
    
    let maxHeight = 0;
    
    for (const node of tree) {
        let height = 1;
        
        if (node.children && node.children.length > 0) {
            height += treeHeight(node.children);
        }
        
        maxHeight = Math.max(maxHeight, height);
    }
    
    return maxHeight;
}

// 計算節點(diǎn)數量
export function treeNodeCount(tree) {
    if (!tree || !Array.isArray(tree)) return 0;
    
    let count = 0;
    
    for (const node of tree) {
        count += 1;
        
        if (node.children && node.children.length > 0) {
            count += treeNodeCount(node.children);
        }
    }
    
    return count;
}

// 計算葉子節點(diǎn)數量
export function treeLeafCount(tree) {
    if (!tree || !Array.isArray(tree)) return 0;
    
    let count = 0;
    
    for (const node of tree) {
        if (!node.children || node.children.length === 0) {
            count += 1;
        } else {
            count += treeLeafCount(node.children);
        }
    }
    
    return count;
}

樹(shù)形結構路徑算法

1. 路徑查找

// 查找節點(diǎn)路徑
export function findNodePath(tree, id, idField = 'id') {
    const result = dfsTreeSearch(tree, node => node[idField] === id);
    return result ? result.path : [];
}

// 獲取所有葉子節點(diǎn)路徑
export function getAllLeafPaths(tree, currentPath = []) {
    if (!tree || !Array.isArray(tree)) return [];
    
    const paths = [];
    
    for (const node of tree) {
        const path = [...currentPath, node];
        
        if (!node.children || node.children.length === 0) {
            paths.push(path);
        } else {
            const childPaths = getAllLeafPaths(node.children, path);
            paths.push(...childPaths);
        }
    }
    
    return paths;
}

// 獲取節點(diǎn)到根節點(diǎn)的路徑
export function getPathToRoot(tree, id, idField = 'id') {
    const path = findNodePath(tree, id, idField);
    return path ? path.reverse() : [];
}

2. 路徑操作

// 根據路徑獲取節點(diǎn)
export function getNodeByPath(tree, path, idField = 'id') {
    if (!path || path.length === 0) return null;
    
    let currentNode = tree.find(node => node[idField] === path[0][idField]);
    
    for (let i = 1; i < path.length && currentNode; i++) {
        const nextId = path[i][idField];
        currentNode = currentNode.children?.find(child => child[idField] === nextId);
    }
    
    return currentNode;
}

// 檢查路徑是否存在
export function validatePath(tree, path, idField = 'id') {
    if (!path || path.length === 0) return false;
    
    return getNodeByPath(tree, path, idField) !== null;
}

這些樹(shù)形結構處理算法為應用提供了強大的樹(shù)形數據操作能力，包括構建、搜索、遍歷和修改樹(shù)形結構。