preface
Daily business front-end operations on the tree is to be handy, such as cascading boxes, tree controls, table trees and so on. This article organizes common tree operations for quick CV.
Array to tree structure
JSON data often returned by the back end requires the front end to convert it into tree data.
case
[{
id: 1.pid: 0.name: Nodes' 1 '}, {id: 2.pid: 1.name: '1-1 nodes'}, {id: 3.pid: 1.name: 'node 1-2'}, {id: 4.pid: 0.name: Nodes' 2 '}, {id: 5.pid: 4.name: 'node 2-1'
}]
Copy the codeimplementation
- Non-recursive implementation
function arrayToTree(data) {
let res = []
if(!Array.isArray(data)) return res
let treeMap = {}
data.forEach(item= > treeMap[item.id] = item)
data.forEach(item= > {
let parent = treeMap[item.pid]
if(parent) { parent.children = ! parent.children ? [] : parent.children parent.children.push(item) }else {
res.push(item)
}
})
return res
}
Copy the code- The recursive implementation
function arrayToTree(data, pid) {
let res = []
if(!Array.isArray(data)) return res
data.forEach(item= > {
if(item.pid === pid) {
let children = arrayToTree(data, item.id)
children.length && (item.children = children)
res.push(item)
}
})
return res
}
Copy the codeTree structure to array
case
[{id: 1.pid: 0.name: Nodes' 1 '.children: [{
id: 2.pid: 1.name: '1-1 nodes'}, {id: 3.pid: 1.name: 'node 1-2'}]}, {id: 4.pid: 0.name: Nodes' 2 '.children: [{
id: 5.pid: 4.name: 'node 2-1'}}]]Copy the codeimplementation
- Breadth traversal
function treeToArr(data) {
let res = []
while(data.length) {
let length = data.length
for(let i = 0; i < length; i++) {
let item = data.shift()
if(item.children && item.children.length) {
for(let j = 0; j < item.children.length; j++) {
data.push(item.children[j])
}
}
res.push({
id: item.id,
pid: item.pid,
name: item.name
})
}
}
return res
}
Copy the code- Depth traversal
function TreeToArr(data) {
let res = []
let stack = []
for(let i = data.length - 1; i >= 0; i--) {
stack.push(data[i])
}
while(stack.length) {
let item = stack.pop()
res.push({
id: item.id,
pid: item.pid,
name: item.name
})
let children = item.children
if(children && children.length) {
for(let i = children.length - 1; i >= 0; i--) {
stack.push(children[i])
}
}
}
return res
}
Copy the codeThe height of the tree
case
const data = [{
id: 1,
children: [{
id: 2,
children: [{
id: 3,
children: []
}]
},
{
id: 4,
children: []
}]
}]
Copy the codeimplementation
- Breadth traversal
function getTreeHeight(data) {
let queue = []
let height = 0
if(!Array.isArray(data)) return height
if(Array.isArray(data) && data.length > 0) queue[0] = data[0]
while(queue.length) {
let length = queue.length
height++
for(let i = 0; i < length; i++) {
let item = queue.shift()
if(item && item.children) {
for(let j = 0; j < item.children.length; j++) {
item.children[j] && queue.push(item.children[j])
}
}
}
}
return height
}
Copy the code- Depth traversal
Depth traversal obtains all paths, and then traverses the path array to obtain the longest path, i.e., the maximum height.
function getTreeHeight(data) {
const paths = []
let height = 0
function dfs(data, prefix) {
for(let i = 0; i < data.length; i++) {
if(data[i].children && data[i].children.length) {
const path = prefix + data[i].id + ', '
dfs(data[i].children, path)
} else {
paths.push(prefix + data[i].id)
}
}
}
dfs(data, "")
for(let i = 0; i < paths.length; i++) {
let pathArr = paths[i].split(', ')
height = Math.max(height, pathArr.length)
}
return height
}
Copy the codeFind the path of the node in the tree
case
[{id: 1.pid: 0.name: Nodes' 1 '.children: [{
id: 2.pid: 1.name: '1-1 nodes'}, {id: 3.pid: 1.name: 'node 1-2'}]}, {id: 4.pid: 0.name: Nodes' 2 '.children: [{
id: 5.pid: 4.name: 'node 2-1'}}]]Copy the codeimplementation
function getNodePath(data, id) {
if(!Array.isArray(data)) return []
let path = []
function findTreeNode(tree, id) {
for(let i = 0; i < tree.length; i++) {
path.push(tree[i].id)
if(tree[i].id === id) return path
let children = tree[i].children
if(children && children.length) {
let findChildrenPath = findTreeNode(children, id)
if(findChildrenPath && findChildrenPath.length) return findChildrenPath
}
path.pop()
}
return[]}return findTreeNode(data, id)
}
Copy the codeFind/edit/delete nodes
Search, edit, and delete operations are based on traversal to find the corresponding ID, and then perform related operations. Here, take search as an example.
case
[{id: 1.pid: 0.name: Nodes' 1 '.children: [{
id: 2.pid: 1.name: '1-1 nodes'}, {id: 3.pid: 1.name: 'node 1-2'}]}, {id: 4.pid: 0.name: Nodes' 2 '.children: [{
id: 5.pid: 4.name: 'node 2-1'}}]]Copy the codeimplementation
Depth-first traversal
function findTreeNode(tree, id) {
for(let i = 0; i < tree.length; i++) {
let node = tree[i]
if(node.id === id) {
return node
}
let children = node.children
if(children && children.length) {
let childrenNode = findTreeNode(children, id)
if(childrenNode) return childrenNode
}
}
return
}
Copy the codeGet all the leaf nodes
case
[{id: 1.pid: 0.name: Nodes' 1 '.children: [{
id: 2.pid: 1.name: '1-1 nodes'}, {id: 3.pid: 1.name: 'node 1-2'}]}, {id: 4.pid: 0.name: Nodes' 2 '.children: [{
id: 5.pid: 4.name: 'node 2-1'}}]]Copy the codeimplementation
function getLeafNode(data) {
let res = []
function dfs(tree) {
for(let i = 0; i < tree.length; i++) {
let children = tree[i].children
if(! children || children.length ===0) {
res.push({
id: tree[i].id,
pid: tree[i].pid,
name: tree[i].name
})
} else {
dfs(children)
}
}
}
dfs(data)
return res
}
Copy the code