javascript - 比较javascript中的树数据

Question

我有两个树结构，一个是包含所有叶子的源树，另一个是 CALLED selected，这只是源树的副本并且缺少一些叶子，我需要比较源树并selected获得与源相同的输出，但只需更新叶子将其与selected. 就像任何源叶包含相同的孩子一样，我想用state: full. 如果没有孩子被选中状态是state: no，如果一些孩子被选中state: partial。

我尝试将选定的树扁平化为 id 数组，因此我可以将选定的树与 匹配source​​，但我陷入了更新输出树的逻辑中。请检查我的预期输出。

const recursCollectIds = ({tree}) => {
	return (tree || [])
  	.map(leaf => { return  (leaf.children && leaf.children.length) ? [leaf.id].concat(recursCollectIds({tree: leaf.children})) : [leaf.id] } )
    .flatMap(x => x)
}

const selected = [{
        id: 4,
        name: 'F',
        children: [{
            id: 8,
            name: 'V',
            children: []
        }, {
            id: 9,
            name: 'T',
            children: []
        }]
    },
    {
        id: 5,
        name: 'B',
        children: [{
            id: 17,
            name: 'R',
            children: []
        }]
    },
    {
        id: 7,
        name: 'O',
        children: [{
            id: 90,
            name: 'Y',
            children: [{
                id: 37,
                name: 'FU',
                children: []
            }]
        }]
    }
]

const source = [{
        id: 4,
        name: 'F',
        children: [{
            id: 8,
            name: 'V',
            children: [{
                id: 3,
                name: 'F',
                children: []
            }]
        }, {
            id: 9,
            name: 'T',
            children: []
        }]
    },
    {
        id: 5,
        name: 'B',
        children: [{
            id: 17,
            name: 'R',
            children: []
        }]
    },
    {
        id: 7,
        name: 'O',
        children: [{
            id: 90,
            name: 'Y',
            children: [{
                id: 37,
                name: 'FU',
                children: []
            }]
        }]
    }
]


const updateTree = ({source, selected}) => {
  const selectedIds = recursCollectIds({tree: selected})
  // need to check with ids of selected and source tree 
  
}

updateTree({source, selected})

预期产出

    const out = [{
        state: 'partial', // due to its children or grand children is selected partially
        id: 4,
        name: 'F',
        children: [{
            state: 'partial', // due to its children or grand children is selected partially
            id: 8,
            name: 'V',
            children: [{
                state: 'no', // due to non of its children selected
                id: 3,
                name: 'F',
                children: []
            }]
        }, {
            state: 'full', // no children so no need to match. 
            id: 9,
            name: 'T',
            children: []
        }]
    },
    {
        state: 'full',
        id: 5,
        name: 'B',
        children: [{
            state: 'full',
            id: 17,
            name: 'R',
            children: []
        }]
    },
    {
        state: 'full',
        id: 7,
        name: 'O',
        children: [{
            state: 'full',
            id: 90,
            name: 'Y',
            children: [{
                state: 'full',
                id: 37,
                name: 'FU',
                children: []
            }]
        }]
    }
]

标签： javascriptalgorithmdata-structurestree

Answer 1

const isUndefined = val => ((typeof val == "undefined") && (val == null));

const isArray = val => ((!isUndefined(val)) && (Array.isArray(val)));

const modifyObject = tree => {
    let respObject = {};
    (isArray(tree) ? tree : []).forEach(leaf => {
        respObject[leaf.id] = leaf;
        if(!isUndefined(leaf.children) && (leaf.children.length > 0)) {
            respObject[leaf.id]["children"] = modifyObject(leaf.children)
        }
    });
    return respObject;
}

const constructResp = (source,selected) => {
    return (isArray(source) ? source : []).map(currentElem=>{
        let currSourceChild = currentElem.children;
        currSourceChild = isUndefined(currSourceChild) ? [] : currSourceChild;
        let currElemSelectedChild = selected[currentElem.id];
        if(isUndefined(currElemSelectedChild)){
            currentElem['state'] = 'no';
            return currentElem;
        } else if(currSourceChild.length == 0){
            currentElem['state'] = 'full';
            return currentElem;
        } else{
            let currSourceUpdatedChild = constructResp(currSourceChild,currElemSelectedChild.children);
            let currIndex = 0;
            let childLen = currSourceUpdatedChild.length;
            for(;currIndex<childLen;currIndex++){
                if(currSourceUpdatedChild[currIndex].state != 'full'){
                    break;
                }
            }
            if(currIndex == childLen){
                currentElem['state'] = 'full';
            } else {
                currentElem['state'] = 'partial';
            }
            return currentElem;
        }
    })
}

const selected = [{
        id: 4,
        name: 'F',
        children: [{
            id: 8,
            name: 'V',
            children: []
        }, {
            id: 9,
            name: 'T',
            children: []
        }]
    },
    {
        id: 5,
        name: 'B',
        children: [{
            id: 17,
            name: 'R',
            children: []
        }]
    },
    {
        id: 7,
        name: 'O',
        children: [{
            id: 90,
            name: 'Y',
            children: [{
                id: 37,
                name: 'FU',
                children: []
            }]
        }]
    }
]

const source = [{
        id: 4,
        name: 'F',
        children: [{
            id: 8,
            name: 'V',
            children: [{
                id: 3,
                name: 'F',
                children: []
            }]
        }, {
            id: 9,
            name: 'T',
            children: []
        }]
    },
    {
        id: 5,
        name: 'B',
        children: [{
            id: 17,
            name: 'R',
            children: []
        }]
    },
    {
        id: 7,
        name: 'O',
        children: [{
            id: 90,
            name: 'Y',
            children: [{
                id: 37,
                name: 'FU',
                children: []
            }]
        }]
    }
]


const updateTree = ({source, selected}) => {
  let modifiedSelected = modifyObject(selected)
  let finalResp = constructResp(source,modifiedSelected);
  console.log(JSON.stringify(finalResp,null,4));
}

updateTree({source, selected})