How to trace back to the label of the root node and splice the path according to the last node value of the tree data?

Efficient backtracking of tree data: stitching from leaf node Value to root node Label path

When processing tree data, it is often necessary to trace back to the root node according to the last node value and splice the path. This article will provide an efficient algorithm without relying on specific UI components.

Question description:

Given a tree data structure, for example:

 const treeData = [
  { label: "Node1", value: "1", children: [
    { label: "Node 1-1", value: "1-1" },
    { label: "Node 1-2", value: "1-2" }
  ]},
  { label: "Node2", value: "2", children: [
    { label: "Node 2-1", value: "2-1" }
  ]}
];

Target: Based on value of the last node (for example "1-2"), backtrack and splice all label from the node to the root node, and generate a path string, such as "Node 1/Node 1-2".

Solution:

We use recursive search without relying on any UI components. The core of the algorithm is to traverse the tree structure in depth first and splice the paths during the backtracking process after finding the target value .

 function getPath(tree, targetValue) {
  function traverse(node, path) {
    path.push(node.label); // Add the current node label

    if (node.value === targetValue) {
      return path.join('/'); // Find the target node and return the path string}

    if (node.children) {
      for (const child of node.children) {
        const result = traverse(child, [...path]); // Recursively traverse child nodes if (result) return result; // If the target node is found, return the path}
    }

    path.pop(); // Backtracking: Remove the current node label and continue searching for other branches return null; // The current branch does not find the target node}

  for (const rootNode of tree) {
    const result = traverse(rootNode, []);
    if (result) return result; // If the target node is found, return the path}
  return null; // The target node is not found in the tree}

const path = getPath(treeData, "1-2");
console.log(path); // Output: Node 1/Node 1-2

path = getPath(treeData, "2-1");
console.log(path); // Output: Node 2/Node 2-1

path = getPath(treeData, "3-1"); // Test the non-existent node console.log(path); // Output: null

Code explanation:

• getPath(tree, targetValue) : main function, receiving tree data and target value .
• traverse(node, path) : a recursive function that performs depth-first traversal.
  • path.push(node.label) : Adds label of the current node to the path array.
  • if (node.value === targetValue) : Find the target node, stitch the path and return.
  • if (node.children) : Iterates over child nodes.
  • path.pop() : Backtracking, removing label of the current node.
• The function returns the found path string, or null means not found.

This method is efficient and versatile, suitable for various tree data structures, without relying on specific UI libraries, and is easy to reuse in various scenarios. It clearly demonstrates the powerful ability of recursion in processing tree data structures.

The above is the detailed content of How to trace back to the label of the root node and splice the path according to the last node value of the tree data?. For more information, please follow other related articles on the PHP Chinese website!